K-way треугольник пересечения и триангуляции

Если вы хотите что-то более прямолинейное, более быстрое в реализации и значительно меньше кода … Я бы рекомендовал сделать несколько простых обрезка полигонов как старые алгоритмы рендеринга программного обеспечения (особенно если учесть, что вы имеете дело только с треугольниками в качестве входных данных). Как кратко упомянули пара других людей, это включает в себя разбиение каждого треугольника в точке, где каждый другой сегмент пересекает это.

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

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

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

В любом случае, удачи!

Ваш пример является частным случаем того, что вычислительные геометры называют «расположением». Библиотека CGAL имеет обширные и эффективные процедуры обработки договоренностей. Если вы проверите эта часть документации, вы увидите, что можете объявить пустое расположение, а затем вставить треугольники, чтобы разделить 2-мерную плоскость на непересекающиеся грани. Как уже говорили другие, вам нужно будет триангулировать лица, которые еще не являются треугольниками. К счастью, CGAL также предоставляет процедуры для этого. Этот пример ограниченной триангуляции Делоне это хорошее место для начала.

CGAL пытается использовать наиболее эффективные алгоритмы, доступные на практике. В этом случае, похоже, вы можете достичь O ((n + k) log n) для расположения с n ребрами (в 3 раза больше, чем количество треугольников в вашем случае) с k пересечением. Алгоритм использует общую технику, называемую «линия развертки». Вертикальная линия проходит слева направо с вычислением и обработкой «событий». События являются конечными точками ребер и пересечениями. По мере обработки каждого события ячейка расположения обновляется.

Алгоритмы Делоне обычно O (n log n) для n вершин. Существует несколько распространенных алгоритмов, которые легко найти или найти в ссылках на CGAL.

Даже если вы не можете использовать CGAL в своей работе (например, по причинам лицензирования), документация полна источников базовых алгоритмов: схем и алгоритмов Делоне с ограничениями.

Однако следует помнить, что как расположения, так и триангуляции, как известно, трудно правильно реализовать из-за ошибки с плавающей запятой. Надежные версии часто зависят от рациональной арифметики (доступно в CGAL).

Чтобы немного расширить комментарий Теда Хоппа, это должно быть возможно, сначала вычислив плоское подразделение, в котором каждая ограниченная грань выхода связана с одним из наборов A ‘, B’, C ‘, AB, AC, BC , ABC или «нет». Второй этап состоит в триангуляции (возможно, невыпуклых) граней в каждом наборе.

Шаг 1 может быть выполнен за O ((N + K) log N) с использованием изменения Bentley-Ottmann Алгоритм развертки, в котором текущий набор поддерживается как часть состояния алгоритма. Это можно определить по отрезкам линии, которые уже были пересечены, и по их направлению.

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

Если вы еще этого не сделали, возьмите копию «Вычислительной геометрии: алгоритмы и приложения» де Берга и соавт.

Я могу думать о двух подходах.

Более общий подход заключается в том, что ваш ввод воспринимается как набор строк и разбивается на две части:

1. Обнаружение полигонов. Возьмите набор линий, которые делают ваши первоначальные треугольники, и получите набор непересекающихся многоугольников. Эта бумага предлагает подход O ((N + M) ^ 4), где N — это количество отрезков, а M — количество пересечений, что, к сожалению, кажется немного медленным …
2. Триангуляция полигонов. Возьмите каждый многоугольник с шага 1 и триангулируйте его. Для этого требуется O (n log * n), что практически равно O (n).

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

1. Нет точек треугольника ни в одном другом треугольнике.
   1. Нет пересечения
   2. Еврейская звезда
   3. Два перпендикулярных шипа
2. Одна точка одного треугольника содержится в другом
3. Каждый треугольник содержит одну точку другой
4. Две точки одного треугольника находятся в другом
5. Три точки одного находятся в другом — один полностью содержится

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