Как разбить многоугольник вдоль n заданных диагоналей?

Question

Скажем, у меня есть многоугольник, представленный в виде списка вершин в порядке CCW (не DCEL), и у меня есть заданный список диагоналей этого многоугольника. Как я могу разбить многоугольник вдоль всех этих диагоналей в список из n + 1 многоугольников?

У меня нет проблем с разделением списка по диагонали одна . Проблема состоит в том, чтобы быстро определить, к какому из двух оставшихся полигонов принадлежат мои другие диагонали. Оттуда я могу разбить список диагоналей на два списка и рекурсивно оперировать двумя расщепленными полигонами.

Предпочтительно, я хотел бы сделать это за O (n log (n)), в отличие от очевидного алгоритма простого обхода двух расщепленных полиномов, чтобы определить, какие диагонали лежат в каком из подполигонов. *

Answer 1

Вот схема того, что я считаю решением.

1. Предположим, вы уже убедились, что диагонали не пересекаются и полностью содержатся внутри многоугольника.

2. Тогда (утверждение 1) вы можете считать задачу полностью комбинаторной и забыть о реальных геометрических деталях расположения многоугольника и диагонали.Давайте подумаем о задаче, поскольку вам дан правильный многоугольник с вершинами [0,1, .., N-1], и вы разрежете его с помощью набора диагоналей [i_k, j_k], 0 <= k </li>

3. Для любых вершин i и j назовем arc_length(i, j) := min(max(i,j) - min(i,j), N - max(i,j) + min(i,j)) - наименьшее количество шагов от i до j или от j до i по циклу [0,1, .., N-1].

4. Давайте назовем sortedDiagonals контейнером (vector>, list> или аналогичным) всех ваших диагоналей, отсортированных по arc_length (i, j), что похоже на

   struct LessPredicate {
     bool operator(pair<int,int> diag1, pair<int,int> diag2) const {
        return arc_length(diag1) < arc_length(diag2);
     }
   };
   

5. Теперь давайте сократим наш правильный многоугольник вдоль диагоналей от отсортированных диагоналей, начиная с «кратчайшего» до «самого длинного».Представьте себе изображение обычного N-гонщика, вписанного в круг с несколькими первыми диагоналями из отсортированных диагоналей.Очевидно, что на рисунке мы видим, что наш правильный многоугольник разбит на более мелкие многоугольники, один из которых содержит центр круга (случай, когда диагональ пересекает центр, может произойти только один раз и на самом последнем шаге из-за сортировки, так что это легкоразобраться как в особом случае).(Утверждение 2) Каждый раз, когда мы рисуем следующую диагональ из sortedDiagonals, диагональ принадлежит многоугольнику, содержащему центр.

Теперь, каждый раз, когда вы берете следующую диагональ из sortedDiagonals, вы знаете, что многоугольник содержитцентр (скажем, вы помните индекс многоугольника или указатель на его структуру и т. д.), поэтому вы знаете, что полигону принадлежит диагональ.Вы разрежете многоугольник с диагональю на две части и запомните, какая из них содержит центр, чтобы узнать его на следующем шаге.

Если вам нужны доказательства утверждений 1 и 2, вот эскиз.

Утверждение 1 верно, потому что если диагонали полностью находятся внутри данного многоугольника и могут пересекаться друг с другом только в своих конечных точках, то этот многоугольник со всеми этими диагоналями и правильный многоугольник с одинаковым количеством вершин и диагоналей, соединяющих вершины с одинаковыми индексамитак как в данном полигоне те же, что и графики, в том смысле, что их данные о заболеваемости одинаковы.Таким образом, мы сводим задачу к случаю правильного многоугольника, который нам нужен, чтобы упростить объяснение того, какой многоугольник мы знаем как содержащий следующую диагональ из нашего списка.

Утверждение 2. Предположим, что мы вырезали правильный многоугольник с некоторойпересекая центр.В результате получается два многоугольника, один из которых не содержит центра - назовем его «маленький многоугольник».Что мы можем сказать о arc_length (diag) для любого diag, полностью содержащегося в «маленьком многоугольнике»?Он не может быть больше, чем arc_length (someDiagonal), и единственный случай, когда

 arc_length(diag) == arc_length(someDiagonal)

- это когда diag == someDiagonal.

Теперь предположим, что мы нарисовали в нашем обычном многоугольнике k первых диагоналей из sortedDiagonals,Каждый из них вырезает свой собственный «маленький многоугольник» из всего правильного многоугольника (и, возможно, некоторые из этих «маленьких многоугольников» содержат некоторые другие «маленькие многоугольники» из других диагоналей, это нормально).Теперь мы рисуем k-1-ю диагональ из sortedDiagonals и замечаем, что из-за нашей сортировки все ранее нарисованные диагонали d_i были не больше d_ (k + 1) в смысле arc_length.Следовательно, их «маленькие полигоны» не имеют внутренних диагоналей arc_length, больших или равных arc_length (d_ (k + 1)).Следовательно, d_ (k + 1) не может принадлежать никаким «маленьким многоугольникам» диагоналей, предшествующих ему в sortedDiagonals, и он может принадлежать только многоугольнику, содержащему центральную точку.

hth