Жесткая сила сдержанная триангуляция Делоне?

Question

Мне нужно создать треугольную сетку из набора точек. Набор имеет очень мало очков, поэтому ему не нужно быть быстрым или оптимизированным (я буду иметь дело с 100 точками максимум). Сетка должна быть ограниченной триангуляцией delaunay. На изображении ниже я показал (слева) набор точек, из которых я начинаю (синие и красные точки). Я также знаю связи между этими точками (контур в черном). Сетка должна выглядеть как пример справа (включая края в сером, которые образуют внешний и внутренний треугольники).

Я не могу использовать библиотеки.

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

Answer 1

Спасибо за все ответы.

Я прошел процесс разработки решения этой проблемы, поэтому я решил поделиться своим опытом, надеясь, что люди, столкнувшиеся с проблемой, найдут полезную информацию.

Так из собственного опыта реализации алгоритма я пришел к выводу:

1. Существует не очень быстрый путь к этой проблеме. Неразумно думать, что это может быть достигнуто всего за 50 строк кода. На самом деле процедура, которую я написал (C++), составляет от 400 до 500 строк (сложно сказать с комментариями). Настолько разумно компактный, но сложный, и мне потребовалось от 2 до 3 дней, чтобы логика была правильной (это может быть сложно).

2. Я нашел алгоритм, предлагаемый Sloan в "A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS", чтобы быть полностью подходящим для проблемы. Реальность, когда дело касается триангуляции Делоне, которая была для меня новой темой, заключается в том, что, похоже, существует много разных алгоритмов, и это исследование довольно старое. Так что для нового зрителя действительно сложно узнать, с чего начать.

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

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

   2.3 Я нашел документ от Слоана понятным, очень хорошо объясненным. Если вы следуете логике и инструкциям, тогда любой может реально реализовать ограниченную триангуляцию Делоне.

Итак, в заключение:

1. Я рекомендую бумагу Sloan, потому что она включает в себя объяснение о том, как создать триангуляции Делоне с последующим сдавленным триангуляции при необходимости.

2. Чтобы ответить на мой собственный вопрос, на самом деле нет переборной силы. Внедрение этого метода просто требует реализации полной логики, и большая часть реализации должна требовать более или менее того же объема работы.

3. С нюансом я не заботился о многих оптимизациях, потому что мои наборы точек очень малы. Поэтому я уверен, что многие алгоритмы лучше, чем описанные Sloan; они, вероятно, предлагают оптимизированные структуры данных и алгоритмы, оптимизированные для минимизации шаги, такие вставки точки в триангуляции и т.д.

Так или иначе Слоан работал. Небольшое изображение, чтобы проиллюстрировать ответ и сделать его более привлекательным ;-)

EDIT

Это код продукции так HELAS я не могу поделиться тем, что ... Я мог бы привести меня быть уволена. Однако процесс очень прост. Вы ищете пересечение между сегментом (вашим ограничением) и всеми ребрами в модели. Затем для каждого пересекаемого ребра вы меняете диагональ между двумя треугольниками, к которым относятся эти ребра. Если новая диагональ все еще пересекает сегмент, добавьте новую диагональ обратно в стек пересеченных ребер для этого сегмента. Если новая диагональ не пересекает сегмент, то добавьте его в стек вновь созданных ребер. Продолжайте обрабатывать стек пересекающихся краев, пока он не станет пустым.

Затем, как только это будет завершено, вам необходимо обработать список новых добавленных ребер. Для каждого из них проверьте, соблюден ли критерий триангуляции Деланея. Если не поменять диагональ треугольника, к которому принадлежит это ребро. Простой ...

Это только бумага ...

Набор точек

26.9375 10.6875 
32.75 9.96875 
31.375 4.875 
27.6562 2.0625 
23.9375 -0.75 
18.1562 -0.75 
10.875 -0.75 
6.60938 3.73438 
2.34375 8.21875 
2.34375 16.3125 
2.34375 24.6875 
6.65627 29.3125 
10.9688 33.9375 
17.8438 33.9375 
24.5 33.9375 
28.7188 29.4062 
32.9375 24.875 
32.9375 16.6562 
32.9375 16.1562 
32.9062 15.1562 
8.15625 15.1562 
8.46875 9.6875 
11.25 6.78125 
14.0312 3.875 
18.1875 3.875 
21.2812 3.875 
23.4687 5.5 
25.6562 7.125 
8.46875 19.7812 
27 19.7812 
26.625 23.9688 
24.875 26.0625 
22.1875 29.3125 
17.9062 29.3125 
14.0312 29.3125 
11.3906 26.7188 
8.75 24.125 

Эти х/Y/Z координаты (Z = 0)

Сегменты:

0 1 
1 3 
3 5 
5 7 
7 9 
9 11 
11 13 
13 15 
15 17 
17 19 
19 20 
20 22 
22 24 
24 26 
26 0 
28 29 
29 31 
31 33 
33 35 
35 28 

Индексы начинаются с 0 (0 -> первой вершины в список вершин)

Answer 2

Я попробовал его с альфа-формой с хорошими результатами в течение нескольких форм https://concavehull.codeplex.com/, но это не далеко от оригинальной стесненной триангуляции Делоне.

Вот мой алгоритм альфа-формы: https://alphashape.codeplex.com.

Answer 3

Простой подход заключается в реализации алгоритма ear clipping. Без оптимизации, как в хэш-сетках, или quad trees. Для отсечения уха вы просто проверяете каждые три последовательные вершины a, b и c. Если b выпукло, и никакая другая вершина многоугольника лежит внутри треугольника abc, вы можете закрепить этот треугольник, уменьшая границу многоугольника на одну вершину, b.

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

Когда триангуляция закончена, вы преобразовываете ее в ограниченную триангуляцию Делоне (CDT). Это можно сделать с помощью edge flipping. Поэтому вам нужно проверить каждый треугольник на окружности. Если вершина соседнего треугольника лежит внутри треугольника, она соответствует CDT, иначе переверните край треугольника, где происходит нарушение.

Редактировать из-за @Betterdev в комментариях: Возможные отверстия во входном многоугольнике могут быть добавлены к начальной границе путем добавления моста. В качестве предварительной обработки можно соединить вершину отверстия с вершиной границы «двойным» ребром. Это всегда возможно и делает каждую дырочную часть главной границы полигона; и хорошо работает с ухе. Однако сохранение соседства через эти мосты жизненно важно для перевертывания.