How to split a common closed polygon into a segment

Question

I need a good (reliable) algorithm for splitting a polygon into two sets (left / right) into a line segment. My polygonal view is just a list of integer coordinates (ordered clocks that never self-intersect), and the line segment is represented by the start and end points. The line always starts and ends outside the polygon, i.e. Crosses the polygon an even number of times.

Here is an example:

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

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

I can determine the AH points by iterating the polygon and checking if the polygon section intersects the line, taking care to observe the boundary cases. I can also determine which side each multi-line line belongs to. I cannot, though, for the life of me, decide how to sew this segment together.

Before offering a general-purpose clipping library, I use the boost polygon, which is very good at trimming polygons against each other, but I did not find any library that would allow you to crop the polygon relative to the line segment, and it is not possible, in general, to turn the segment lines into a polygon, which I could fix with.

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

Answer 1

Ok, here is a pretty simple recipe for how to get the answer:

Start with a set of intersection points ordered by moving the outline clockwise:

• ABCDEFGH

Sort them according to the distance from the beginning of the line:

• HCFEDGBA

We also need to remember for each point if this intersection is from left to right or from right to left.

• Start from anywhere. Let them say G. Follow the outline 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 on. We are on the right side, so we need to select the value to the right of H in the Sorted set: C. Add HC to the current polygon.
• Follow the path in a clockwise direction and add a CD to the current polygon.
• We are on the right side, so we need to select the value to the right of D in the sorted set: G. Add DG to the current polygon.
• Now we have reached send the point, so save the polygon (GHCDG) and delete the used items from the list.
• Start from a different point.

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? 

Answer 3

I decided something like this once, and I gave up trying to be smart.

• Run all the vertices, turning them into connected line segments, starting a new segment with a new point every time you cross the cutting line.
• Find all the segments that divide the endpoint and attach them to one longer.
• Connect all open ends.