Ограниченная триангуляция Делоне
-
Определение ограниченной триангуляции Делоне
- Ограниченная триангуляция Делоне расширяет триангуляцию Делоне, добавляя сегменты в качестве ребер.
- Применяется в географических информационных системах и для создания сеток.
-
Входные данные и свойства
- Входные данные включают плоский прямолинейный график, точки и непересекающиеся отрезки.
- Ограниченная триангуляция включает все сегменты в качестве ребер и использует только вершины.
- Каждое дополнительное ребро должно содержать окружность, недоступную для вершин внутри.
-
Обобщение на трехмерные данные
- Джонатан Шевчук расширил определение на трехмерные данные.
- Не все трехмерные данные имеют ограниченную триангуляцию по обобщенному определению.
-
Алгоритмы и приложения
- Существуют алгоритмы для вычисления ограниченных триангуляций Делоне с временной сложностью O(n log n).
- Триангуляция используется для топографической съемки и моделирования границ, например, рек.
- Ограниченная триангуляция применяется в методах уточнения Делоне для создания точных сеток.
-
Рекомендации и ссылки
- Статья содержит ссылки на реализацию с открытым исходным кодом и призыв к расширению.
- Статья связана с алгоритмами и структурами данных, но является заглушкой.