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.