Clamp LineString to Polygon

Question

I'm trying to constrain a LineString to a Polygon. Here's an example of what I'm looking for:

In the left figure (the input), the green LineString travels beyond the border of the Polygon for a bit before returning and continuing inside. In the right figure (the output), the part of the LineString that was beyond the Polygon border is removed, and in its place, the LineString hugs the Polygon boundary.

This output would also be acceptable:

How can I do this in a way that is not terribly slow and/or with code that is not terribly complex and ugly?

The LineString can be an arbitrary meandering path, and as seen in the example, it might have self-intersections. It is not necessarily possible to convert it to a Polygon and use Polygon/Polygon intersection. One example would be a Hilbert curve which has no interior or exterior.

I can imagine a brute-force approach that involves splitting the Polygon exterior and the LineString with each other (perhaps using complex_split()) then piecing things together. I think this will involve a lot of project() and interpolate() which can become quite computationally expensive. And it starts to get even more painful when you consider a LineString with multiple overlapping excursions outside of the Polygon. Got any better ideas? Or maybe you can implement the brute-force approach elegantly?

What's this for? I want to use this algorithm in Ink/Stitch, an open source machine embroidery design platform. The LineString is a stitch path that should be inside a fill region, but may occasionally wander out. The excursions are undesirable and we need to eliminate them. One might also imagine a GPS trace that should be constrained inside a boundary area.

Answer 1

I've found a solution! I'd still love to hear if anyone has a faster/better way of doing it. Here's what it looks like clamping a hilbert curve to a circle:

Here's the code, probably too long to include here: gist.

It works by considering the LineString one segment at a time. It builds a new path as it goes, adding segments if they're inside the Polygon.

If the segment intersects the Polygon border, it breaks the segment at the intersection point then pushes the pieces back on the list to reconsider later. This is easier than handling the intersection right then and there, because one segment might intersect the Polygon boundary multiple times, or the intersection might occur at one of the LineString's corners, or a segment might only touch the polygon boundary but remain inside, etc. This way, everything looks the same: transitions always happens between segments.

If we transition from inside to outside between segments, it keeps track of the first segment that was outside. If it later transitions back inside from outside, it notes that second segment. It then uses those two segments (extended a bit to ensure intersection) to cut the Polygon border into two pieces. It picks the smallest of the two (the shorter way around) and adds that to the path.

There's also some special-casing to handle the case that part of the LineString overlaps part of the Polygon border.

To handle holes, I'll do the process again (one per hole), and reverse the sense of "inside" and "outside".

This works, and reasonably fast. I'd still love to see an easier way, because this did get a bit long.

Answer 2

I found a much easier solution! I'm just gonna keep talking to myself here, because someone's gonna find this useful some day.

The new solution is way simpler. It turns out that if you take a LineString and subtract the polygon border, you end up with a list of LineStrings in the same order as the original LineString, broken at points where it crosses the border.

From there, you just need to track when you transition from the inside to the outside and back again. Easy peasy, and it runs faster!