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