importance especially when various robots are considered. The line-of-sight method and
thus, the shadow area method had to be revisited for further optimization.
Line Segment Intersection Method
A method was devised that accounts for the line segments that comprise the obstacles
contained within the map. Therefore, a file containing all of the obstacle line segments
was created. Using the obstacle line segments, the current robot position, and another
arbitrary point or robot position it could be determined if there was an unobstructed path
between the robot and the point in question. At this point, it was necessary to write a
function that could determine if two lines intersect.
Further research revealed a function written by Mukesh Prasad [1] that determines if
two line segments intersect. A total of four (x,y) pairs are passed into the linesintersect
function. The first two pairs (xl, yi, x2, y2) represent the first line segment and the second
two pairs represent the second line segment (x3, y3, X4, Y4). The following line equation is
used in the function:
axx +bly +c,= 0 (2.1)
The function proceeds to calculate the coefficients of the line equation, ai, bi, and ci.
al=y2-yl (2.2)
b,=x, -x2 (2.3)
c,=x2xy1-x xy2 (2.4)
The function then performs a calculation that determines if the endpoints of the second
line segment, (x3,y3) and (x4,y4), lie on the same side of the first line segment. If this is
true, the line segments do not intersect. If this is false, a calculation is performed which
determines if the endpoints of the first line segment, (xi,yi) and (x2,y2), lie on the same