side of the second line segment. If this is true, the line segments do not intersect and if


this is false, the line segments do intersect. This is achieved with a simple sign check.


The x and y values of point three (x3,y3) are placed into the line equation (eqn. 2.1)


joining points one and two. The same is done for the fourth point. The equations below


are used:


 alx3+by3 +c=r3 (2.5)


 ax4+b y4 +c1=r4 (2.6)


For example, if the signs of r3 and r4 are the same then the two line segments in question


do not intersect. This means that point three and point four lie on the same side of the


first line segment. The original function returns the actual point of intersection.


Modifications were made to the function to return a value of' 1' if the segments do


intersect and a '0' if they do not intersect.

 robot 1
 Yr") Obstacle Line Segment List
 Sx, y, x2, Y2 Xl, yi, x2, Y2
 intersection X2, y2, X4, Y4
 4 Y4, X3, 3
 SX3, Y3, X1, Y
 x3,y3 X4, Y4


 -- '. robot 2 xn1, Yn-1, xn, Yn
 \ (Xr2, Yr2)
 Obstacle line
 segment





 Figure 2.9: Illustration of the 'linesintersect' method A file contains a list of all line segments
 that make up each obstacle in the map.

Line-of-Sight Determination

 For this particular problem the line-of-sight criteria is defined as a single robot being


able to see at least one other robot. Line-of-sight among a pair of robots can be


determined using the linesintersect function explained previously. Assuming that the