Splitting an STL vector

Question

Let's say I have a (convex) polygon with vertices 0..n-1. I want to split this polygon in half, say, between verticies i and j. Vertices i and j should appear in both polygons.

As far as I can tell, there are only two cases. One where i < j, or when i > j. i is never equal to j (nor are they ever adjacent).

I'm storing my vertices like vector<Point> poly. You can assume Point is just a basic struct with two doubles x and y, with points indexed sequentially in CCW order.

If i < j, then I just need to copy the vertices from i to j (inclusive) into one vector, and then from j to n-1 plus 0 to i into another. Or vice versa for the other case, right?

Here's the code I'm using, but it doesn't seem to work right (let j == closestIndex):

if (i < closestIndex) {
 lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.begin() + closestIndex + 1);
 upperPoly.insert(upperPoly.end(), poly.begin() + closestIndex, poly.end());
 upperPoly.insert(upperPoly.end(), poly.begin(), poly.begin() + i + 1);
} else {
 lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.end());
 lowerPoly.insert(lowerPoly.end(), poly.begin(), poly.begin() + closestIndex + 1);
 upperPoly.insert(upperPoly.end(), poly.begin() + closestIndex, poly.begin() + i + 1);
}

Answer 1

I think there's another restriction you need to include, in addition to i never equal to j.

You also need to ensure that if i is the starting point that you aren't splitting at either i-1 or i+1. If the sides are linear, splitting at consecutive points means that the dividing line is simply an edge, so you get back the original polygon and an edge line, which doesn't seem very interesting.

Instead of two arrays x and y, I'd recommend a single array of 2D points, with verticies numbered consecutively in a counterclockwise direction around the polygon.

So the two polygons will be:

Polygon 1 : start with i, iterate to the ending point j, and finish with the edge from j back to i;

Polygon 2: start with i, to the ending point j, and then over j+1, j+2, back to i.

Answer 2

My bad. The code above is fine, there was a problem with my display routine. I was pushing too many polygons onto the stack, so it only looked incorrect. Should have been obvious, but I didn't spot it. Thanks for the help duffymo.

Answer 3

As a side note:

You don't really have 2 cases. If i > j then just swap i and j. Then you are always in the case where i < j, assuming i != j.

I would probably code it like follows:

if (i > closestIndex) 
    std::swap (i, closestIndex);
assert(closestIndex - i > 1); 
// make sure i != closestIndex and i is not adjacent to closestIndex

lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.begin() + closestIndex + 1);
upperPoly.insert(upperPoly.end(), poly.begin() + closestIndex, poly.end());
upperPoly.insert(upperPoly.end(), poly.begin(), poly.begin() + i + 1);