Ограниченная триангуляция Делоне
В вычислительной геометрии ограниченная триангуляция Делоне — это обобщение триангуляции Делоне , которое включает в триангуляцию определенные необходимые сегменты в качестве ребер. [1] [2] в отличие от самой триангуляции Делоне, которая основана исключительно на положении заданного набора вершин без учета того, как они должны быть соединены ребрами. Его можно эффективно вычислять, и он находит применение в географических информационных системах и создании сеток.
Определение [ править ]
Входными данными для задачи триангуляции Делоне с ограничениями является плоский граф прямых линий , набор точек и непересекающихся отрезков прямой на плоскости.Ограниченная триангуляция Делоне этого входного сигнала представляет собой триангуляцию его выпуклой оболочки , включающую все входные сегменты в качестве ребер и использующую только вершины входных данных. За каждое дополнительное ребро добавленный к этим входным данным, чтобы превратить его в триангуляцию, должна существовать окружность, проходящая через конечные точки , так что любая вершина внутри круга заблокирована от видимости хотя бы из одной конечной точки по сегменту ввода. Это обобщает определяющее свойство двумерных триангуляций точек Делоне, заключающееся в том, что каждое ребро имеет окружность, проходящую через две его конечные точки, не содержащую других вершин. Триангуляция, удовлетворяющая этим свойствам, всегда существует. [1]
Джонатан Шевчук обобщил это определение на ограниченные триангуляции Делоне трехмерных входных данных, систем точек и непересекающихся сегментов и треугольников в трехмерном пространстве; однако не каждый вход этого типа имеет ограниченную триангуляцию Делоне согласно его обобщенному определению. [2]
Алгоритмы [ править ]
Несколько алгоритмов вычисления ограниченных во времени триангуляций Делоне плоских прямолинейных графов известны. [1] [3] Ограниченная триангуляция Делоне простого многоугольника может быть построена за линейное время . [4]
Приложения [ править ]
При топографической съемке триангуляцию строят по точкам, снятым на местности. Если край триангуляции пересекает реку, полученная поверхность неточно моделирует путь реки. рисуются Поэтому линии разрыва вдоль рек, краев дорог, горных хребтов и т.п. Линии разрыва используются в качестве ограничений при построении триангуляции.
Ограниченная триангуляция Делоне также может использоваться в уточнения Делоне методах для создания сетки как способ заставить сетку соответствовать границам доменов по мере ее уточнения.
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с Чу, Л. Пол (1989), «Ограниченные триангуляции Делоне», Algorithmica , 4 (1): 97–108, doi : 10.1007/BF01553881 , MR 0983658 , S2CID 189918468
- ↑ Перейти обратно: Перейти обратно: а б Шевчук, Джонатан Ричард (2008), «Общемерная ограниченная триангуляция Делоне и ограниченная регулярная триангуляция. I. Комбинаторные свойства», Discrete & Computational Geometry , 39 (1–3): 580–637, doi : 10.1007/s00454-008-9060 -3 , МР 2383774
- ^ Ван, Цао Ань; Шуберт, Ленхарт К. (1987), «Оптимальный алгоритм построения триангуляции Делоне набора отрезков прямой», в Соуле, Д. (ред.), Труды третьего ежегодного симпозиума по вычислительной геометрии, Ватерлоо, Онтарио, Канада, 8–10 июня 1987 г. , ACM, стр. 223–232, doi : 10.1145/41958.41982 , S2CID 18490297.
- ^ Чин, Фрэнсис; Ван, Цао Ан (1999), «Нахождение ограниченной триангуляции Делоне и ограниченной диаграммы Вороного простого многоугольника за линейное время», SIAM Journal on Computing , 28 (2): 471–486, doi : 10.1137/S0097539795285916 , hdl : 10722 /47094 , MR 1634357 , S2CID 28966377
Внешние ссылки [ править ]
- [1] Реализация с открытым исходным кодом.
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |