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.

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.