Как я могу сложить и вычесть выпуклые многоугольники?

У меня есть два 2D выпуклых многоугольника, перекрывающих друг друга . Я ищу алгоритм вычитать и складывать их. Результатом должен быть один вогнутый многоугольник или (еще лучше) набор самых больших выпуклых многоугольников, образующих вогнутый результат (например, треугольники).

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

Как я могу это сделать?

TL; DR Вам необходимо реализовать логические операции с использованием BSP-деревьев.

Ну, кажется, мы говорим о Конструктивной Твердой Геометрии здесь. Я внедрил CSG на коммерческом уровне, поэтому знаю кое-что об этом.

Классическая статья о CSG называется « Объединение деревьев BSP и приводит к многогранным операциям над множествами» , если честно, здесь слишком много объяснений, но вкратце говоря, алгоритм имеет дело с многоугольниками, которые лежат в одной плоскости с разбиением двоичного пространства, в основном конструируя дерево BSP из каждой многоугольной сетки. Второй шаг - объединить эти деревья BSP; Вы просто берете одно дерево и вставляете его в другое. Затем алгоритм переходит к объяснению того, как обращаться с каждым конечным узлом для разделения и вычитания узлов, узлы, которые не нужны в окончательной форме, будут удалены, другим будут назначены соответствующие родительские узлы.

Но ждать! Эта статья в основном говорит о полигональных сетках и трехмерных плоскостях, НЕТ?

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

Обратите внимание, что этот алгоритм и CSG в целом не имеют дело с рендерингом и сеткой граней напрямую, и на самом деле они не готовы, поэтому вам нужно извлечь грани конечных деревьев BSP. Я также считаю , трассировка лучей проще подхода к визуализации результата CSG, вам нужно только лучи , чтобы перемещаться по дереву вместо извлечения и фактически разделив лицо (помните , мы имеем дело только с бинарными перегородками).

Относительно числовой надежности. Хорошо отметить, что есть два типа геометрических вычислений,

• Те, которые основаны на построении, вы строите фигуру на основе результата предыдущей операции. Например, y = sqrt(x)а затем использовать yв новой операции. Это называется конструкцией; проблема в том, что числовые ошибки будут быстро накапливаться.
• В качестве альтернативы есть операции, в которых вместо этого используются предикаты. По сути, вместо использования конструкции вы просто спрашиваете, является ли условие истинным / ложным, и используете одно и то же значение в другой операции. Классические тесты включают в себя круг и тест на ориентацию; это также может привести к ошибкам числового типа, особенно если вы используете одинарную или двойную точность, но обычно дает гораздо лучшие результаты. Существуют другие решения, которые различаются по скорости и точности. Вот одна из недавних работ, которые избегают конструирования, используя плоскую геометрию для получения точных результатов. Я также процитирую из бумаги:

Концепция плоского представления многоугольных сеток была впервые описана Сугихарой ​​и Ири [SI89]. Этот вид представления обеспечивает одно важное преимущество, когда речь идет о задачах, которые включают изменение топологии твердых тел, представленных сетками, таких как вычисление булевых выражений: для получения результирующего многогранника не требуется создавать новую информацию о первичной геометрии.

И, наконец, я хотел бы добавить, что если вы хотите начать реализацию BSP CSG, я бы рекомендовал начать с BSP Faqs .

Исходя из вашего примера:

Выберите начальную вершину на многоугольнике A, а затем начните проверку на предмет пересечения ребер по часовой стрелке (или против часовой стрелки). Если пересечения нет, добавьте предыдущую вершину к полученному многоугольнику. Если есть пересечение, добавьте точку, в которой они пересеклись, к полученному многоугольнику, а затем начните итерацию по многоугольнику B в том же порядке намотки. Сделайте то же самое, снова поменяв местами А, если произойдет пересечение.

После того, как вы собрали все вершины для нового многоугольника, выполните для него алгоритм триангуляции. Метод ушной клипсы прост в реализации, но есть более быстрые варианты.

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

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

Если вам нужен вогнутый многоугольник, просто выберите ближайший край между двумя входными многоугольниками и добавьте два новых ребра:

Выпуклость становится немного сложнее:

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

В принципе:

• Итерация по вершинам второго многоугольника.
• Для каждой вершины V итерируйте ребра первого многоугольника:
• Найдите «диапазон» ребер, которые обращены к вершине
• возьмите внешнюю пару вершин, которые определяют этот диапазон, и удалите все ребра в диапазоне, который их соединяет
• Нарисуйте два новых сегмента от этих внешних вершин до новой вершины (от второго многоугольника), убедившись, что новые ребра направлены в правильном направлении.
• Перейдите к следующей вершине из второго многоугольника

Вот схема, иллюстрирующая процесс для первой вершины:

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

Возможно, кто-то другой может посоветовать вам какой-нибудь совет вычитания.