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

Если у нас есть K наборов потенциально перекрывающихся треугольников, каков вычислительно эффективный способ вычисления нового, не перекрывающегося набора треугольников?

Например, рассмотрим эту проблему:

Tesselation

Здесь у нас есть 3 набора треугольников A, B, C, с некоторым взаимным перекрытием, и мы хотим получить неперекрывающиеся наборы A ‘, B’, C ‘, AB, AC, BC, ABC, где, например, треугольники в AC будет содержать поверхности, где есть исключительное перекрытие между A и C; и A ‘будет содержать поверхности A, которые не перекрывают любой другой набор.

15

Решение

Я (также) предлагаю двухэтапный подход.

1. Найдите точки пересечения всех сторон треугольника.

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

2. Триангуляция с ограниченным Делоне.

Я думаю, что полигональная триангуляция, предложенная @Claudiu, не может решить вашу проблему, поскольку она не может гарантировать, что включены все исходные ребра. Поэтому я предлагаю вам взглянуть на Ограниченные триангуляции Делоне. Это позволяет вам указать ребра, которые должен быть включенным в вашу триангуляцию, даже если они не будут включены в триангуляцию Делоне или полигона без ограничений. Кроме того, есть реализации, которые позволяют вам указать невыпуклую границу вашей триангуляции, вне которой треугольники не генерируются. Это также кажется обязательным требованием в вашем случае.

Реализация ограниченного Делоне нетривиальна. Есть, однако, несколько устаревший, но очень хорошая реализация C доступный от исследователя CMU (включая инструмент командной строки). Увидеть Вот для теории этого конкретного алгоритма. Этот алгоритм также поддерживает указание границы. Обратите внимание, что связанный алгоритм может делать больше, чем просто Constrained Delaunay (а именно, создание качественной сетки), но он может быть настроен так, чтобы не добавлять новые точки, что составляет Constrained Delaunay.

редактировать Смотрите комментарии для другой реализации.

3

Другие решения

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

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

введите описание изображения здесь

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

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

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

2

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

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

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

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

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

1

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

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

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

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

0

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

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

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

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

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

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

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector