Триангуляция Делоне и диаграмма Вороного
9.3 Вопросы и упражнения
1. Что означает понятие : вычислительная сложность алгоритма?
2. Опишите алгоритм бинарного поиска.
3. Дайте определение выпуклого множества в пространстве En
4. Доказать что пересечение любой совокупности выпуклых множеств является выпуклым.
5. Привести пример многоугольника на плоскости, который не является простым.
6. Доказать что для любого множества на плоскости существует выпуклая оболочка.
7. Предложить алгоритм разбиения простого многоугольника на треугольники
10. Триангуляция Делоне и диаграмма Вороного
10.1 Введение
Задача построения триангуляции является одной из базовых в вычислительной геометрии. К ней сводятся многие практические задачи. Например, задачи, связанные с определением топологических свойств объектов или восстановлением поверхностей, заданных нерегулярными наборами отсчётов. Наконец, практически все системы визуализации основаны на подобных геометрических моделях.
Разбиение плоскости на треугольники или пространства на тетраэдры по заданным точкам позволяет получить представление о связях между точками, интерполировать различные значения на плоскости и в пространстве, строить другие структуры.
Разработка эффективных алгоритмов триангуляции была и остаётся очень актуальной задачей. И, несмотря на всё разнообразие математических, графических пакетов и вычислительных средств бывает необходимо использовать независимый, легко настраиваемый, быстрый, надёжный алгоритм триангуляции.
Приведем формальное определение триангуляции.
Триангуляцией (тетраэдеризацией, в трёхмерном случае) конечного множества точек N называется такое разбиение выпуклой оболочки N на треугольники (тетраэдры), что выполняются следующие требования:
1. каждая точка выпуклой оболочки N принадлежит какому-то треугольнику (тетраэдру)
2. треугольники (тетраэдры) не имеют общих внутренних точек
3. вершинами треугольников (тетраэдров) являются точки из N
4. каждая точка N является вершиной какого-то треугольника (тетраэдра)
Среди нескольких известных видов триангуляций на практике обычно применяется триангуляция Делоне, которая должна удовлетворять простому локальному условию: никакая точка не может лежать внутри сферы, описанной вокруг тетраэдра Делоне (для плоского случая – внутри окружности, описанной вокруг треугольника Делоне). Условие Делоне относительно просто проверить. Кроме этого, из всех возможных триангуляций, триангуляция Делоне (на плоскости) имеет самый большой минимальный угол среди минимальных углов всех других триангуляций, поэтому полученные треугольники наиболее близки к равносторонним, что повышает точность возможной последующей интерполяции.
|
