Generate new polygons from a cut polygon (2D)

I'm stuck with this little problem and my algorithm to solve this doesn't hold for all cases. Does anybody has an id开发者_运维百科ea 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.

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...

You could apply Weiler Atherton clipping (effectively what Pavel is suggesting), but there is a huge caveat.

Due to floating point errors, the W/A clipping algorithm is extremely difficult to get working well - In cases such as the clipping line passing through a vertex, or precisely along an edge of the polygon, the algorithm can become confused about which "path" around the perimiter of the polygon it should follow and it then outputs incorrect results.

1 find side each point is

pick one pont that is not on cut (a for instance) and set that it is on left side (it does not metter actaly)

when you go over points on cut, side of point you reach change. So you find left/right points.

Problem is that you should also consider that order of points should be in predifined way. (clockwise for instance)

2 start at each midsection of cx and go once clockwise and counterclockwise.

For each polygon you hit midsection in one direction only once.

If you "overflow" c that mean that you reach outer polynom. You might solve this problem if you define c0 and cmax which lies on polgon and you have than

input =  {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}

The simplest to implement is Sutherland-Hodgman. The one problem with it is that it leaves little zero area slivers connecting the polys on one side of the line. In your example, this would give you something like :

{a c2 c3 e c6 c5 c c4 c1} and {b c1 c2 f c3 c6 d c5 c4}

If you could live with this or figure out how to break them up into the pieces you want, then you would find that the code which did the actual clipping would be about as simple as possible.

The implementation simply requires two stacks and a single pass through the vertices of your polygon. At each vertex you check to see if you've crossed the line since the previous vertex. If so, compute the crossing point and push it on one of the stacks. Then push the new vertex onto one of the stacks. Really easy.