триангуляция Делоне
Метод триангуляции
Триангуляция Делоне на плоскости с изображенными описанными окружностями

В вычислительной геометрии триангуляция Делоне или триангуляция Делоне множества точек на плоскости подразделяет их выпуклую оболочку [1] на треугольники, описанные окружности которых не содержат ни одной из точек. Это максимизирует размер наименьшего угла в любом из треугольников и имеет тенденцию избегать узких треугольников .

Триангуляция названа в честь Бориса Делоне за его работу над ней с 1934 года. [2]

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

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

Связь с диаграммой Вороного

Триангуляция Делоне дискретного множества точек P в общем положении соответствует двойственному графу диаграммы Вороного для P. Центры описанных окружностей треугольников Делоне являются вершинами диаграммы Вороного. В двумерном случае вершины Вороного соединены ребрами, которые можно вывести из отношений смежности треугольников Делоне: если два треугольника имеют общее ребро в триангуляции Делоне, их центры описанных окружностей должны быть соединены с ребром в мозаике Вороного.

Особые случаи, когда эта связь не соблюдается или является неоднозначной, включают в себя следующие случаи:

  • Три или более коллинеарных точек, где описанные окружности имеют бесконечные радиусы .
  • Четыре или более точек на идеальной окружности, где триангуляция неоднозначна и все центры описанных окружностей тривиально идентичны.
  • Ребра диаграммы Вороного, уходящие в бесконечность, не определяются этим соотношением в случае конечного множества P. Если триангуляция Делоне вычисляется с помощью алгоритма Боуера–Уотсона , то центры описанных окружностей треугольников, имеющих общую вершину с «супер»-треугольником, следует игнорировать. Ребра, уходящие в бесконечность, начинаются из центра описанной окружности и перпендикулярны общему ребру между сохраняемым и игнорируемым треугольниками.

г-мерный Делоне

Для множества P точек в ( d -мерном) евклидовом пространстве триангуляция Делоне — это триангуляция DT( P ) такая, что ни одна точка в P не находится внутри описанной гиперсферы любого d - симплекса в DT( P ) . Известно [2] , что существует единственная триангуляция Делоне для P, если P — множество точек в общем положении ; то есть аффинная оболочка P является d -мерной и ни одно множество из d + 2 точек в P не лежит на границе шара, внутренняя часть которого не пересекает P .

Задача нахождения триангуляции Делоне набора точек в d -мерном евклидовом пространстве может быть преобразована в задачу нахождения выпуклой оболочки набора точек в ( d + 1 )-мерном пространстве. Это можно сделать, присвоив каждой точке p дополнительную координату, равную | p | 2 , тем самым превратив ее в гиперпараболоид (это называется «подъемом»); взяв нижнюю сторону выпуклой оболочки (поскольку верхняя торцевая крышка обращена вверх от начала координат и должна быть отброшена); и отобразив обратно в d -мерное пространство, удалив последнюю координату. Поскольку выпуклая оболочка уникальна, то и триангуляция является уникальной, предполагая, что все грани выпуклой оболочки являются симплексами . Несимплициальные грани возникают только тогда, когда d + 2 исходных точек лежат на одной и той же d - гиперсфере , т. е. точки не находятся в общем положении. [3]

Характеристики

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

Пусть n — число точек, а d — число измерений.

  • Объединение всех симплексов в триангуляции представляет собой выпуклую оболочку точек.
  • Триангуляция Делоне содержит ⁠ ⁠ О ( н ⌈ г / 2 ⌉ ) {\displaystyle \textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr)}} симплексы. [4]
  • На плоскости ( d = 2 ), если на выпуклой оболочке имеется b вершин, то любая триангуляция точек имеет не более 2 n – 2 – b треугольников плюс одну внешнюю грань (см. Эйлерову характеристику ).
  • Если точки распределены в соответствии с процессом Пуассона на плоскости с постоянной интенсивностью, то каждая вершина имеет в среднем шесть окружающих треугольников. В более общем случае для того же процесса в d измерениях среднее число соседей является константой, зависящей только от d . [5]
  • На плоскости триангуляция Делоне максимизирует минимальный угол. По сравнению с любой другой триангуляцией точек, наименьший угол в триангуляции Делоне по крайней мере такой же большой, как наименьший угол в любой другой. Однако триангуляция Делоне не обязательно минимизирует максимальный угол. [6] Триангуляция Делоне также не обязательно минимизирует длину ребер.
  • Окружность, описывающая любой треугольник Делоне, не содержит внутри себя никаких других входных точек.
  • Если окружность, проходящая через две входные точки, не содержит внутри себя никаких других входных точек, то отрезок, соединяющий эти две точки, является ребром триангуляции Делоне данных точек.
  • Каждый треугольник триангуляции Делоне набора точек в d -мерных пространствах соответствует грани выпуклой оболочки проекции точек на ( d + 1 )-мерный параболоид , и наоборот.
  • Ближайший сосед b к любой точке p находится на ребре bp в триангуляции Делоне, поскольку граф ближайших соседей является подграфом триангуляции Делоне.
  • Триангуляция Делоне — это геометрический остов : на плоскости ( d = 2 ) кратчайший путь между двумя вершинами по ребрам Делоне, как известно, не превышает 1,998 евклидова расстояния между ними. [7]

Визуальное определение Делоне: Переворачивание

Из приведенных выше свойств вытекает важная особенность: если рассмотреть два треугольника △ ABD , △ BCD с общим ребром BD (см. рисунки), то если сумма углов α + γ ≤ 180° , то треугольники удовлетворяют условию Делоне.

Это важное свойство, поскольку оно позволяет использовать технику переворачивания . Если два треугольника не удовлетворяют условию Делоне, то замена общего ребра BD на общее ребро AC дает два треугольника, которые удовлетворяют условию Делоне:

  • Данная триангуляция не удовлетворяет условию Делоне (сумма α и γ больше 180°).
    Данная триангуляция не удовлетворяет условию Делоне (сумма α и γ больше 180°).
  • Эта пара треугольников не удовлетворяет условию Делоне (внутри описанной окружности находится точка).
    Эта пара треугольников не удовлетворяет условию Делоне (внутри описанной окружности находится точка).
  • Переворачивание общего ребра дает действительную триангуляцию Делоне для четырех точек.
    Переворачивание общего ребра дает действительную триангуляцию Делоне для четырех точек.

Эта операция называется переворотом и может быть обобщена до трех и более измерений. [8]

Алгоритмы

Нам нужен надежный и быстрый способ определить, лежит ли точка D в описанной окружности точек A, B, C.

Многие алгоритмы для вычисления триангуляции Делоне полагаются на быстрые операции для определения того, находится ли точка внутри описанной окружности треугольника, и эффективную структуру данных для хранения треугольников и ребер. В двух измерениях один из способов определить, лежит ли точка D в описанной окружности A, B, C, заключается в оценке определителя : [9]

| А х А у А х 2 + А у 2 1 Б х Б у Б х 2 + Б у 2 1 С х С у С х 2 + С у 2 1 Д х Д у Д х 2 + Д у 2 1 | = | А х − Д х А у − Д у ( А х − Д х ) 2 + ( А у − Д у ) 2 Б х − Д х Б у − Д у ( Б х − Д х ) 2 + ( Б у − Д у ) 2 С х − Д х С у − Д у ( С х − Д х ) 2 + ( С у − Д у ) 2 | > 0 {\displaystyle {\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{ y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\ D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix} А_{x}-Д_{x}&А_{y}-Д_{y}&(А_{x}-Д_{x})^{2}+(А_{y}-Д_{y})^{2} \\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{ 2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y}) ^{2}\end{vmatrix}}>0\end{aligned}}}

Если A, B, C отсортированы против часовой стрелки, этот определитель будет положительным только в том случае, если D лежит внутри описанной окружности.

Алгоритмы переворота

Как упоминалось выше, если треугольник не является треугольником Делоне, мы можем перевернуть одно из его ребер. Это приводит к простому алгоритму: построить любую триангуляцию точек, а затем переворачивать ребра до тех пор, пока ни один треугольник не будет не-Делоне. К сожалению, это может потребовать Ω( n 2 ) переворотов ребер. [10] Хотя этот алгоритм можно обобщить на три и более измерений, его сходимость в этих случаях не гарантируется, поскольку она обусловлена ​​связностью базового перевернутого графа : этот граф связен для двумерных наборов точек, но может быть несвязным в более высоких измерениях. [8]

Инкрементный

Самый простой способ эффективного вычисления триангуляции Делоне — многократно добавлять по одной вершине за раз, повторно триангулируя затронутые части графа. Когда добавляется вершина v , мы разделяем на три треугольника, содержащие v , затем применяем алгоритм переворота. Если сделать это наивно, это займет O( n ) времени: мы просматриваем все треугольники, чтобы найти тот, который содержит v , затем мы потенциально переворачиваем каждый треугольник. Тогда общее время выполнения составит O( n 2 ) .

Если мы вставляем вершины в случайном порядке, то оказывается (с помощью довольно сложного доказательства), что каждая вставка перевернет, в среднем, только O(1) треугольников – хотя иногда она перевернет гораздо больше. [11] Это все еще оставляет время определения местоположения точки для улучшения. Мы можем хранить историю выполненных разделений и переворотов: каждый треугольник хранит указатель на два или три треугольника, которые его заменили. Чтобы найти треугольник, содержащий v , мы начинаем с корневого треугольника и следуем указателю, который указывает на треугольник, содержащий v , пока не найдем треугольник, который еще не был заменен. В среднем это также займет O(log n ) времени. Таким образом, по всем вершинам это займет O( n log n ) времени. [12] Хотя метод распространяется на более высокие размерности (как доказали Эдельсбруннер и Шах [13] ), время выполнения может быть экспоненциальным в размерности, даже если конечная триангуляция Делоне мала.

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

К сожалению, алгоритмы, основанные на переворачивании, обычно трудно распараллелить, поскольку добавление некоторой определенной точки (например, центральной точки колеса повозки) может привести к O( n ) последовательным переворачиваниям. Блеллох и др. [14] предложили другую версию инкрементального алгоритма, основанного на rip-and-tent, которая практична и высокопараллельна с полилогарифмическим диапазоном .

Разделяй и властвуй

Алгоритм «разделяй и властвуй» для триангуляции в двух измерениях был разработан Ли и Шехтером и улучшен Гибасом и Столфи [9] [15] и позже Дуайером. [16] В этом алгоритме рекурсивно рисуется линия, разделяющая вершины на два набора. Триангуляция Делоне вычисляется для каждого набора, а затем два набора объединяются вдоль линии разделения. Используя некоторые хитрые трюки, операция слияния может быть выполнена за время O( n ) , поэтому общее время выполнения составляет O( n log n ) . [17]

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

Парадигма «разделяй и властвуй» для выполнения триангуляции в d -мерном пространстве представлена ​​в работе «DeWall: Быстрый алгоритм триангуляции Делоне «разделяй и властвуй» в пространстве E d » авторов П. Чигнони, К. Монтани, Р. Скопиньо. [18]

Было показано, что алгоритм «разделяй и властвуй» является самым быстрым методом последовательной генерации DT. [19] [20]

Sweephull

Sweephull [21] — это гибридный метод для 2D-триангуляции Делоне, который использует радиально распространяющуюся оболочку Sweep-hull и алгоритм переворота. Оболочка Sweep-hull создается последовательно путем итерации радиально отсортированного набора 2D-точек и соединения треугольников с видимой частью выпуклой оболочки, что дает неперекрывающуюся триангуляцию. Можно построить выпуклую оболочку таким образом, пока порядок точек гарантирует, что ни одна точка не попадет в треугольник. Но радиальная сортировка должна минимизировать переворот, будучи изначально высоко Делоне. Затем это сочетается с финальным итеративным шагом переворота треугольника.

Приложения

Евклидово минимальное остовное дерево набора точек является подмножеством триангуляции Делоне тех же точек [22] , и это можно использовать для его эффективного вычисления.

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

Триангуляции Делоне можно использовать для определения плотности или интенсивности выборок точек с помощью оценщика поля тесселяции Делоне (DTFE) .

Триангуляция Делоне случайного набора из 100 точек на плоскости.

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

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

Ограниченная триангуляция Делоне нашла применение в планировании пути в автоматизированном вождении и топографической съемке. [23]

Смотрите также

Ссылки

  1. ^ Грубо говоря, это область, которую можно охватить резинкой, натянутой на точки.
  2. ^ аб Делоне, Борис (1934). «Sur la sphere vide» [О пустой сфере]. Бюллетень Академии наук URSS, Classe des Sciences Mathématiques et Naturelles (на французском языке). 6 : 793–800.
  3. ^ Фукуда, Комей . «Часто задаваемые вопросы по многогранным вычислениям». www.cs.mcgill.ca . Получено 29 октября 2018 г.
  4. ^ Seidel, Raimund (1995). «Теорема о верхней границе для многогранников: простое доказательство ее асимптотической версии». Computational Geometry . 5 (2): 115–116. doi :10.1016/0925-7721(95)00013-Y.
  5. ^ Мейеринг, Дж. Л. (1953). «Площадь интерфейса, длина ребра и число вершин в кристаллических агрегатах со случайным зародышеобразованием» (PDF) . Philips Research Reports . 8 : 270–290. Архивировано из оригинала (PDF) 2017-03-08.Как цитируется Дуайером, Рексом А. (1991). «Диаграммы Вороного большего размера в линейном ожидаемом времени». Дискретная и вычислительная геометрия . 6 (4): 343–367. doi : 10.1007/BF02574694 . MR  1098813.
  6. ^ Эдельсбруннер, Герберт ; Тан, Тиов Сенг; Ваупотич, Роман (1992). "Алгоритм времени O(n2 log n) для триангуляции угла minmax" (PDF) . Журнал SIAM по научным и статистическим вычислениям . 13 (4): 994–1008. CiteSeerX 10.1.1.66.2895 . doi :10.1137/0913058. MR  1166172. Архивировано из оригинала (PDF) 2017-02-09 . Получено 2017-10-24 . .
  7. ^ Ся, Ге (2013). «Коэффициент растяжения триангуляции Делоне меньше 1,998». SIAM Journal on Computing . 42 (4): 1620–1659. arXiv : 1103.4361 . doi : 10.1137/110832458. MR  3082502. S2CID  6646528.
  8. ^ ab De Loera, Jesús A .; Rambau, Jörg; Santos, Francisco (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Т. 25. Springer.
  9. ^ ab Guibas, Leonidas ; Stolfi, Jorge (1985). «Примитивы для манипулирования общими подразделениями и вычисления Вороного». ACM Transactions on Graphics . 4 (2): 74–123. doi : 10.1145/282918.282923 . S2CID  52852815.
  10. ^ Уртадо, Ф .; Ной, М.; Уррутия, Дж. (1999). «Переворачивание рёбер в триангуляциях». Дискретная и вычислительная геометрия . 22 (3): 333–346. doi : 10.1007/PL00009464 .
  11. ^ Guibas, Leonidas J. ; Knuth, Donald E. ; Sharir, Micha (1992). «Рандомизированное инкрементное построение диаграмм Делоне и Вороного». Algorithmica . 7 (1–6): 381–413. doi :10.1007/BF01758770. S2CID  3770886.
  12. ^ де Берг, Марк; Отфрид Чеонг ; Марк ван Кревелд; Марк Овермарс (2008). Вычислительная геометрия: алгоритмы и приложения (PDF) . Спрингер-Верлаг. ISBN 978-3-540-77973-5. Архивировано из оригинала (PDF) 2009-10-28 . Получено 2010-02-23 .
  13. ^ Эдельсбруннер, Герберт ; Шах, Нимиш (1996). «Инкрементальное топологическое переворачивание работает для регулярных триангуляций». Algorithmica . 15 (3): 223–241. doi :10.1007/BF01975867. S2CID  12976796.
  14. ^ Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Параллелизм в рандомизированных инкрементальных алгоритмах. Архивировано 25 апреля 2018 г. в Wayback Machine . SPAA 2016. doi:10.1145/2935764.2935766.
  15. ^ Петерсон, Сэмюэл. «ВЫЧИСЛЕНИЕ ОГРАНИЧЕННЫХ ТРИАНГУЛЯЦИЙ ДЕЛОНЕ НА ПЛОСКОСТИ». www.geom.uiuc.edu . Архивировано из оригинала 22 сентября 2017 г. . Получено 25 апреля 2018 г. .
  16. ^ Дуайер, Рекс А. (ноябрь 1987 г.). «Быстрый алгоритм «разделяй и властвуй» для построения триангуляции Делоне». Algorithmica . 2 (1–4): 137–151. doi :10.1007/BF01840356. S2CID  10828441.
  17. ^ Лич, Г. (июнь 1992 г.). «Улучшение алгоритмов триангуляции Делоне в худшем случае». 4-я Канадская конференция по вычислительной геометрии . CiteSeerX 10.1.1.56.2323 . 
  18. ^ Cignoni, P.; C. Montani; R. Scopigno (1998). "DeWall: Быстрый алгоритм триангуляции Делоне "разделяй и властвуй" в E d ". Computer-Aided Design . 30 (5): 333–341. doi :10.1016/S0010-4485(97)00082-1.
  19. ^ Сравнение последовательных алгоритмов триангуляции Делоне "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2012-03-08 . Получено 2010-08-18 .{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )
  20. ^ "Triangulation Algorithms and Data Structures". www.cs.cmu.edu . Архивировано из оригинала 10 октября 2017 г. Получено 25 апреля 2018 г.
  21. ^ "S-hull" (PDF) . s-hull.org . Архивировано (PDF) из оригинала 2013-10-27 . Получено 25 апреля 2018 .
  22. ^ Франц Ауренхаммер; Рольф Кляйн; Дер-цай Ли (26 июня 2013 г.). Диаграммы Вороного и триангуляции Делоне. World Scientific Publishing Company. стр. 197–. ISBN 978-981-4447-65-2.
  23. ^ Sterling J Anderson; Sisir B. Karumanchi; Karl Iagnemma (5 июля 2012 г.). «Планирование и управление на основе ограничений для безопасной полуавтономной эксплуатации транспортных средств» (PDF) . Симпозиум IEEE по интеллектуальным транспортным средствам 2012 г. . IEEE. doi :10.1109/IVS.2012.6232153. Архивировано из оригинала (PDF) 28 февраля 2019 г. . Получено 27 февраля 2019 г. .
  • Триангуляция Делоне в CGAL , библиотеке алгоритмов вычислительной геометрии:
    • Мариетт Ивинек . 2D-триангуляция. Получено в апреле 2010 г.
    • Пион, Сильвен; Тейо, Моник . 3D-триангуляции. Получено в апреле 2010 г.
    • Хорнус, Самуэль; Девиллерс, Оливье; Жамен, Клеман. dD Триангуляции.
    • Hert, Susan; Seel, Michael. dD Convex Hulls and Delaunay Triangulations. Получено в апреле 2010 г.
  • «Poly2Tri: Инкрементная ограниченная триангуляция Делоне. Реализация на C++ с открытым исходным кодом. Получено в апреле 2019 г.
  • «Построение триангуляции Делоне методом «Разделяй и властвуй». Реализация C99 с открытым исходным кодом. Получено в апреле 2019 г.
  • "CDT: Ограниченная триангуляция Делоне в C++". Реализация с открытым исходным кодом C++. Получено в августе 2022 г.
Взято с "https://en.wikipedia.org/w/index.php?title=Триангуляция_Делоне&oldid=1223834829"