#### Howdy, Stranger!

We are about to switch to a new forum software. Until then we have removed the registration on this forum.

# Program doesn’t know when two line segments intersect (SOLVED)

edited May 2016

I would delete this post but it appears there isn’t a way to do that.

The original post:

I am trying to make a function that determines whether two line segments intersect. (I’m creating a program that involves figuring out whether a given point is inside a polygon.) The function is a method of the `LineSegment` class that inputs another `LineSegment l`, (that’s a lowercase L, not a 1) and figures out whether they intersect. It outputs `0` or `1` instead of `False` or `True` for reasons that are unimportant here. Here it is:

``````def intersects( self, l ):
lx1 = l.get_x1() # The x-coordinate of the first endpoint of l
lx2 = l.get_x2() # The x-coordinate of the second endpoint of l
ly1 = l.get_y1() # The y-coordinate of the first endpoint of l
ly2 = l.get_y2() # The y-coordinate of the second endpoint of l
lm = l.get_m() # The slope of l
lb = l.get_b() # The y-intercept of l
'''self.m is the slope of this line, self.b is the y-intercept of this line, self.x1 is the x-coordinate of the first
endpoint of this line, etc.

if self.m == lm: # If the slopes are the same — i.e. the lines are parallel — they don’t intersect
return 0
else: # If the lines aren’t parallel:
ix = iy = 0 # ix will be the x coordinate of the intersection point; iy will be the y coordinate
if self.m == 'vertical': # If this line (self) is vertical (we need this condition because slope-intercept form doesn’t
work with vertical lines)
ix = self.x1 # The x-coordinate of the intersection point is just the x coordinate of this line, because it’s vertical
iy = lm * ix + lb # Plug that into the other equation to find the y coordinate
elif lm == 'vertical': # The reverse — if l is vertical
ix = lx1
iy = self.m * ix + self.b
else: # Otherwise, solve for the intersection point
ix = ( lb - self.b ) / ( self.m - lm )
iy = self.m * ix + self.b

# I have tested this and everything up to here works — it always finds the correct intersection point. However, we
still have to make sure the intersection point isn’t outside either segment. We do this by seeing whether the
x-coordinate of the intersection, ix, is between self.x1 and self.x2 and also between lx1 and lx2, and whether
the y-coordinate of the intersection, iy, is between self.y1 and self.y2 and also between ly1 and ly2.

if ( self.x1 <= ix <= self.x2 or self.x2 <= ix <= self.x1 ) and \
( lx1 <= ix <= lx2 or lx2 <= ix <= lx1 ) and \
( self.y1 <= iy <= self.y2 or self.y2 <= iy <= self.y1 ) and \
( ly1 <= iy <= ly2 or ly2 <= iy <= ly1 ):
return 1
else:
return 0
``````

This works. However, I then realized that I wanted to go into more detail — I want method to output 0 if they don’t intersect and 1 if they do, but if the intersection point lies on the endpoint of one (or both) of the segments — i.e. they intersect in a T or L shape — it should output 0.5. I thought I would go about this by first testing whether they “strictly intersect” — i.e. they intersect in an X, not a T or an L — and if they do, output 1; if they don’t, then proceed from there. Here’s how I thought to test for “strict intersection” — just make all the inequalities strict:

``````if ( self.x1 < ix < self.x2 or self.x2 < ix < self.x1 ) and \
( lx1 < ix < lx2 or lx2 < ix < lx1 ) and \
( self.y1 < iy < self.y2 or self.y2 < iy < self.y1 ) and \
( ly1 < iy < ly2 or ly2 < iy < ly1 ):
...
``````

For some reason, this is never true — I’ve tested this by putting something like `print( 'hi' )` after this `if` statement and the program prints nothing (even when the intersection point is obviously not an endpoint of a line). Why is this?