Intersection between Segment and Interior of Polygon in SymPy

Question

I would like to find the length of a line segment covered by a polygon. For that, I use the following sympy code. Unfortunately, it considers the polygon a set of lines, rather than a region, so I only get the points of intersection.

>>> import sympy
>>> t = sympy.geometry.Polygon((0,0), (0,1), (1,0))
>>> l = sympy.geometry.Segment((1/3,1/3), (2,2))
>>> t.intersect(l)
{Point2D(1/2, 1/2)}

I tried to use the closure propety of the polygon, unfortunately that does not seem to be implemented.

>>> t.closure
NotImplementedError                       Traceback (most recent call last)

I could perhaps try to calculate the resulting segment myself, using the points returned by sympy, however, there seem to be many corner cases, and I'd quite like to have the library do this for me.

Am I overlooking something?

Answer 1

The Polygon class could be called PolygonalCurve; it is not currently meant to describe filled-in planar shapes.

Polygons are treated as closed paths rather than 2D areas

For convex polygons the following method works:

def intersection_length(l, t):
    endpoints = [p for p in [l.p1, l.p2] if t.encloses(p)]
    endpoints.extend(iter(t.intersect(l)))
    if len(endpoints) < 2:
        return 0
    else: 
        intersection = sympy.geometry.Segment(*endpoints)
    return intersection.length

It returns sqrt(2)/6 in your example. The idea is that if the intersection is a nontrivial line segment, its endpoints will come from (a) intersections of l with the boundary of t; (b) the endpoints of l enclosed by t. So all candidates are collected and if we have two of them, then find the distance between them.

(Although the distance could be computed without forming a Segment object, I thought it'd be nice to have one anyway).

For non-convex polygons we could have more complex intersection, with several pieces. I wrote a solution for this case too, but you will need the GitHub version of SymPy for it, because it uses parameter_value method that was only added recently (it will be in SymPy 1.2).

The method here is to find all endpoints as before (there may be more than 2), sort them according to the direction of the line segment, and then test for each piece whether it should be included (by considering whether the midpoint of the piece is enclosed).

import sympy

def intersection_length(segment, polygon):
    endpoints = [p for p in [segment.p1, segment.p2] if polygon.encloses(p)]
    endpoints.extend(iter(polygon.intersect(segment)))
    u = sympy.Symbol('u')
    endpoints.sort(key=lambda p: segment.parameter_value(p, u)[u])
    total_length = 0
    for a, b in zip(endpoints[:-1], endpoints[1:]):
        piece = sympy.geometry.Segment(a, b)
        if polygon.encloses(piece.midpoint):
            total_length += piece.length
    return total_length

t = sympy.geometry.Polygon((0, 0), (5, 0), (1, 1), (0, 5))
l = sympy.geometry.Segment((-1, 5), (5, -1))
print(intersection_length(l, t))