Расщепление вектора STL

Question

Допустим, у меня есть (выпуклый) многоугольник с вершинами 0..n-1. Я хочу разбить этот многоугольник пополам, скажем, между вершинами i и j. Вершины i и j должны появляться в обоих многоугольниках.

Насколько я могу судить, есть только два случая. Тот, где я J. я никогда не равен j (и при этом они никогда не смежны).

Я храню свои вершины как vector<Point> poly. Можно предположить, что Point - это просто базовая структура с двумя двойными числами x и y с точками, последовательно проиндексированными в порядке CCW.

Если i

Вот код, который я использую, но, похоже, он не работает правильно (пусть 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

Я думаю, что есть еще одно ограничение, которое вам нужно включить, в дополнение к тому, что я никогда не равен j.

Вы также должны убедиться, что если я - отправная точка, которую вы не разделяете ни на i-1, ни на i + 1. Если стороны линейные, разделение в последовательных точках означает, что разделительная линия - это просто ребро, поэтому вы возвращаете исходный многоугольник и линию ребра, что не кажется очень интересным.

Вместо двух массивов x и y я бы порекомендовал один массив двумерных точек с последовательными нумерациями вершин в направлении против часовой стрелки вокруг многоугольника.

Итак, два полигона будут:

Полигон 1: начать с i, выполнить итерацию до конечной точки j и закончить с ребром от j до i;

Полигон 2: начать с i до конечной точки j, а затем через j + 1, j + 2 и обратно до i.

Answer 2

В качестве примечания:

У вас нет 2 случаев. Если я> j, то просто поменяйте местами i и j. Тогда вы всегда в случае, когда я

Я бы, вероятно, закодировал это следующим образом:

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);

Answer 3

Мой плохой. Код выше в порядке, была проблема с моей программой отображения. Я помещал слишком много полигонов в стек, поэтому это выглядело неправильно Должно было быть очевидно, но я этого не заметил. Спасибо за помощь, duffymo.