Test if polylines intersects using Python

Question

Is there a simple solution to test if two polylines intersect, not using any libraries?

such as

PL1 = ((-1, -1), (1, -1), (1, 2)), PL2 = ((0, 1), (2, 1))

PL1.intersect(PL2)

I'm only able to find solutions for lines with two points.

I agree with @tnkneppp. Btw you code isn't working because you are comparing if there are tuples in `PL1` and `PL2` that are exactly similar, plus you would need a `set` for the `intersect` method. — , Jan 02 '15 at 17:33
Your polylines are just series of multiple lines with two points. Why not just check for intersections of all the segments using the same technique you are using for two point lines? Unless your polylines are actually curves. — Rick, Jan 02 '15 at 17:41
check out this post http://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect you might find it helpful. — Kai Xiao, Jan 02 '15 at 17:47

score 1 · Accepted Answer · edited May 23 '17 at 12:21

As mentioned in the comments, you can apply the traditional algorithm of the intersection of lines (this for example) between all the component lines of the polygons. For example:

def line_intersection(line1, line2):
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
    ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1])

    def det(a, b):
        return a[0] * b[1] - a[1] * b[0]

    div = det(xdiff, ydiff)
    if div == 0:
       return None

    d = (det(*line1), det(*line2))
    x = det(d, xdiff) / div
    y = det(d, ydiff) / div
    return x, y

def poly_intersection(poly1, poly2):

    for i, p1_first_point in enumerate(poly1[:-1]):
        p1_second_point = poly1[i + 1]

        for j, p2_first_point in enumerate(poly2[:-1]):
            p2_second_point = poly2[j + 1]

            if line_intersection((p1_first_point, p1_second_point), (p2_first_point, p2_second_point)):
                return True

    return False

PL1 = ((-1, -1), (1, -1), (1, 2))
PL2 = ((0, 1), (2, 1))

print poly_intersection(PL1, PL2)

Thanks. I was unsure of the, very simple, last part of the code. I just needed to loop through the lines. — Sebastian Hylander, Jan 02 '15 at 18:29

Test if polylines intersects using Python

1 Answers1