How To Slice a Simple Polygon with a Line

Question

I have a simple polygon (convex or concave, but no holes) that I need to slice into parts with a line segment. I'm not sure how to actually determine how many polygons result after the slice, or how to group the vertices.

Basic convex cases the always results in 2 sub-polygons are easy, but how would I deal with a complicated concave shape? Take an "E" shape polygon for example. A vertical slice can yield 4 polygons. How can I determine which vertices make up each one of those sub-polygons?

Defining the Polygon: I have two options here. My polygon can be an ordered list of vertices, or it can be an array of triangles. I would prefer a solution that uses the array of triangles. It should be pretty easy to loop through every triangle and slice it with the line if they intersect. But then I have no idea how to group those triangles into the sub-polygons that result.

Pseudo-code or even general advice is good; a C# implementation is ideal.

Answer 1

A while back I gave this answer to a somewhat different question.

That answer gives a way of establishing an outline of a shape, given a triangular decomposition of that shape.

The basic idea is to consider the edges of all the triangles as directed vectors, and then cancel out equal but opposite edges.

In your case, you would have a bunch of triangles representing the original shape. You would slice the individual triangles with the line. You would then regather the triangles into shapes using the method outlined above, with the proviso that sliced edges would not cancel.

There are details and pictures in the answer referred to above. But to summarize the steps would be

1. Perform the triangle splits

2. For each resulting triangle, add the three directed edges to a set. To determine clockwise order, check out the the answers to this question.

3. Go through the edge set removing pairs of edges that are are equal but opposite (unless they are slice edges)

4. Pick an edge in the set, then find the edge whose tail matches the head of the first edge. Then repeat for that edge, until you get to the beginning edge. Remove each edge from the edge set as you get to it. Whenever you get to the beginning edge you have a closed loop representing one of the result polygons.

5. Perform Step 4 until there are no edges left.

All of this accommodates your wish to start from a triangulation of your polygon. But as one of the commenters to your original question has pointed out, you may want to consider the alternatives given at http://stackoverflow.com/questions/1775457/generate-new-polygons-from-a-cut-polygon-2d.