We are about to switch to a new forum software. Until then we have removed the registration on this forum.
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
1 instead of
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?