algorithm - Generate new polygons from a cut polygon (2D)

Question

I'm stuck with this little problem and my algorithm to solve this doesn't hold for all cases. Does anybody has an idea how to solve this?

Here's an example polygon:

example http://img148.imageshack.us/img148/8804/poly.png

Formal description

We have a list of points in CW order defining the polygon. We also can query whether a point is a cutting point with is_cut(p), where p is a given point. Now we want to compute new polygons caused by this "cut".

The algorithm should do this:

Input: {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

Output: {a, c1, c2}, {b, c4, c3, f, c2, c1}, {d, c6, c5}, {e, c3, c4, c, c5, c6}

Here my current algorithm:

follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point 
    and not part of the current poly, follow it
--- else keep searching
else
-> continue until you hit your starting point.
that's a poly
do this for every non-cut-point

This algorithm doesn't hold if you'd start at c or f.

Answer 1

First you should calculate what segments of the cutting line belong to internals of your original polygon. That's a classical problem, and its solution is simple. Given that your points c1, c2, c3 ... c6 are laid out along the line in exactly this order, then segments c1-c2, c3-c4 etc will always belong to polygon internals (*).

Now we can construct simple recursive algorithm for cutting polygons. Given your big input array, {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}, start from any polygon point, for example, b; add it to array result. Traverse the input array forward. If you encounter

• usual polygon node, push it to array result.
• ck node, where k is odd, look for c(k+1) and keep traversing from its position.
• ck node, where k is even, look for c(k-1), jump to its position and keep nevertheless traversing forward.

For last two cases, add these nodes in the order you encountered them to result array. Add ck node to set cut, and add another node (c(k+1) or c(k-1), whichever you've got) into a global set done.

If you'll have to go beyond the last element, circuit to the first element in the input array.

Sooner or later you'll encounter the initial node you were traversing from. Now in the result array you have a polygon you've cut. Remember it. Repeat the procedure recursively, starting from position of each node that belongs to cut set and doesn't belong to the global done set.

That's the solution as I see it. But it's computational geomentry, so it may turn a bit more complex than it seems.

---

For our example, start from b:

1. done={}, start from b. After first pass, you'll get result=[b,c4,c3,f,c2,c1], cut={c4,c2}, done={c3,c1}; Recurse to c4 and c2 nodes.
2. done={c3;c1}, start from c4 (recursion from 1). After this pass, you'll get result=[c4,c,c5,c6,e,c3,c4], cut={c5,c3}, done+={c6,c4}; Recurse to c5.
3. done={c3;c1;c4;c6}, start from c2 (recursion from 1). After this pass, you'll get result=[c2,a,c1], cut={c1}, done+={c2}; Don't recurse to c1, since it's in done set;
4. done={c3;c1;c4;c6;c2}, start from c5 (recursion from 2). After this pass, you'll get result=[c5,d,c6], cut={c5}, done+={c6}; Don't recurse to c5, since it's in done set;

Voila - you get 4 polygons you've needed.

---

(*) Note that it requires more "mathematical" representation of the line. For example, if one of the polygon vertexes is on the line, the vertex should be doubled, i.e. if c point was a bit closer to the right side and on the red line, the line would have [c1, c2, c3, c, c, c6] points on it, and the polygon array would be [a, c1, b, c, c, c, d, c6, e, c3, f, c2].

Sometimes (not in this example), it may lead to cutting "empty" polygons, such as [a, a, a]. If you don't need them, you can eliminate them at late stages. Anyway, it's computational geometry with an immense number of border cases. I can't include them all in one answer...