Comments 19
В условиях говорилось про отсутствие точек в окружности, но не одной картинки с окружностями я не увидел
Жалко, что код не опубликовали.
А не думали об похожем алгоритме, но для точек в трёх измерениях с тетраэдрами?
Вообще про три измерения следующие мысли: если сортировать вдоль прямой, то последняя добавленная точка останется видимой, от нее можно будет легко найти видимые грани, как в алгоритме заворачивания подарка для выпуклой оболочки 3D, рекурсивно и без проверки всех граней, а только смежных (и то, сразу не очевидно, может быть даже этот шаг уже будет выполняться в худшем случае суммарно за O(N^2)). Далее нужна стереометрия, чтобы понять, верны ли аналоги утверждений из 2D случая. Если это так, то алгоритм вполне переносится на большую размерность
Еще стоит упомянуть, что триангуляция Делоне — двойственный объект к диаграмме Вороного. Соответсвенно, одно из другого можно довольно просто построить. Диаграмма Вороного очень полезная конструкция и позволяет находить ближайшую из заданных точек для любой точки на плоскости. Так что одно из применений данного алгоритма — построение диаграммы, т.к. приведенный в статье метод гораздо проще, хоть и медленнее, оптимального алгоритма построения диаграммы Вороного.
Соответственно предлагается хранить ребро с двумя вершинами в множестве и выполнять поиск по ребру (упорядоченной паре вершин).
Это вариация на тему которая обычно называется half-edge или doubly-connected edge list (DCEL).
А вообще по названию я подумал что речь идет о Fortune's algorithm. Он строит дуальную диаграмму Вороного и работает за гарантированные nlog(n). В правильно выбранной структуре данных типа DCEL дуальный граф строится тривиально за (n) шагов. Он тоже сравнительно простой. Более сложные варианты строят Делоне за n log(log(n)) в среднем (и nlog(n) в худшем) случае.
1. Для большинства реальных задач (численных методов и инженерных расчетов), помимо списка ребер, нужен список элементов (треугольник --> индексы трех вершин), а также матрица жесткости (треугольник --> соседние треугольники с общими ребрами).
2. Далее, на практике нужно стремиться, чтобы триангуляция была как можно однороднее, т.е. размер (площадь) и форма (углы) треугольников была бы примерно одинаковы. Критично избегать элементы с острыми углами (<30 град).
3. Будет ли работать алгоритм для структурированного множества точек, например, для матрицы NxN?
Будет ли работать алгоритм для структурированного множества точек, например, для матрицы NxN?
Там много групп из 4-х точек на одной окружности, поэтому ответ будет не единственным, так что какие диагонали в квадратах будут взяты зависит от реализации. Но ответ будет корректным. Однако, для такого набора точек нет смысла гонять общий алгоритм, можно триангуляцию захардкодить и построить вообще за O(n).
1. Да, описанный в статье метод хранения триангуляции не самый удобный в использовании, но он однозначно задает триангуляцию. За один проход по множеству из ребер с «противолежащими» точками можно без проблем преобразовать триангуляцию в удобный вид, что работает O(N). Лишь бы памяти хватило во время перестроения.
2. Если смотреть на конечный результат, то он, конечно, единственный и не зависит от алгоритма. А вот по ходу построения действительно в алгоритме из статьи строятся длинные узкие треугольники, которые быстро перестраиваются. Это важное замечание, потому что точность может пострадать.
3. Не очень понял, что подразумевается под структурированным множеством точек
Алгоритм триангуляции Делоне методом заметающей прямой