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