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

I have this algorithm in my library PolyK. Here is the demo. If you understand Javascript, I am sure it will be easy to rewrite it into your programming language.