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

edited May 2016 in Python Mode

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
            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?

Sign In or Register to comment.