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