How to split a general closed polygon by a line segment

Question

I need a good (robust) algorithm for splitting a polygon into two sets(left/right) by a line segment. My polygon representation is simply a list of integer coordinates(ordered clock wise, never self intersecting) and the line segment is represented by a start and end point. The line always starts and ends outside the polygon, i.e. intersects the polygon an even number of times.

Here is an example:

The output of the algorithm should be the two sets(travelling clock wise):

• Left: HABCH, FGDEF
• Right: HCDGH, BAB, FEF

I can identify the points A-H by iterating the polygon and checking if a polygon segment crosses the line, taking care to respect border cases. I can also determine which side each multi-line belongs to. I cannot though, for the life of me, decide how to string these segment together.

Before you suggest a general purpose clipping library: I am using boost polygon which is very good at clipping polygons against each other, but I haven't found any library which let's you clip a polygon against a line segment and it is not possible in general to turn the line segment into a polygon which I could clip with.

EDIT: I had missed FEF and the fact that a polygon can have parts on both sides of the line segment.

Ringe

I'm fascinated by this problem. I'm also curious about the statement: it is not possible in general to turn the line segment into a polygon. Why not? Isn't a line segment just a rectangle with 0 width? Maybe there's a minimum non-zero width that would clip at all the same places as an ideal line segment? – Aspirate

You could turn the line segment into a rectangle with zero width, but would it be useful? I'm not sure what would happen if you'd XOR that polygon with the original. I'll try it with boost polygon and let you know what happens. – Ringe

In which way is this different than half-plane clipping? The line splits the plane into two halves and you want the part of the polygon in the left and the polygon in the right plane. – Missus

Imagine that the line segment would begin between C and F. – Ringe

Why is FEF not a polygon in the Right set? [and why are the Left polygons on the right side of the picture?] – Sharkskin

FEF should be in there. That was an oversight. Left and right is relative to the line orientation. – Ringe

Answer 1

Ok, here is a rather simple recipe of how to arrive at the answer:

Start with the set of intersection points ordered by traveling the contour clockwise:

• ABCDEFGH

Sort them according to distance from the start of line:

• HCFEDGBA

We also need to remember for each point if it is a left-to-right or right-to-left intersection.

• Start with any point. Let's say G. Follow the contour clockwise and add GH to the current polygon.
• Now we need to travel along the line. The direction depends on which side of the line we are. We are on the right side, so we need to pick the value to the right of H in the sorted set: C. Add HC to the current polygon.
• Follow the contour clockwise and add CD to the current polygon.
• We are on the right side, so we need to pick the value to the right of D in the sorted set: G. Add DG to the current polygon.
• We have now reached the starting point, so let's save the polygon(GHCDG) and remove used points from the list.
• Start over with another point.

Ringe

Answer 2

For each intersection of the polygon border with the line segment:
    Add a new point to the polygon.
    Remember the new points in a new-point set.

Add the original polygon to the polygon set.

For each pair of points in the new-point set:
    For each polygon in the current polygon set:
        If the line segment between the points is completely inside the polygon.
           Replace the polygon in the polygon set with two polygons 
           generated by dividing the original polygon along the line 
           segment between the points.

For each polygon in the polygon set:
    Add it to the Left result set or the Right result set.
    (Note this may not be possible.  
        Consider your example of the segment starting between C and F: 
        You will end up with a polygon (GABCFG) that touches both 
        sides of the dividing segment.  Is that a Left or a Right?

Sharkskin

You are absolutely right about polygons not being left or right(or being both). So the partitioning into two sets is not possible. The rest of the algorithm sounds about right. I would have to sort the points A-H by increasing distance from the start of the line to get the lines HC, FE, DG and BA into “For each pair of points in the new-point set”. Then I would have to rely that my polygon::contains(point) function always recognizes points lying on the border. I’ll try this out. – Ringe

This probably would have worked, but the step "If the line segment between the points is completely inside the polygon." is rather expensive for non-convex polygons. I've added an answer which only needs to compare each polygon segment with the line once. – Ringe

Answer 3

I've solved something similar once and I gave up trying to be clever.

1. Run round all the vertices making them into connected line segments, starting a new segment with a new point every time you intersect the cutting line.
2. Find all segments which share an end point and join them back up into one longer one.
3. Connect all the open ends.

Colunga

But how do I know that the GH segment needs to be connected to the CD segment to form HCDGH, for instance? – Ringe

Really good question - not sure why I never hit that.I would follow the cutting line and link pairs of intersections - so long as your polygon never self intersects the cutter has to get enter.leave.enter.leave.enter.leave as it passes through, and each of those is a line segment. – Colunga

Ok, I figured this out and added it as a separate answer. – Ringe