Как правильно выполнить Триангуляцию Делоне для прямоугольника?
Исходя из определения триангуляции Делоне:
триангуляция для заданного множества точек S на плоскости, при которой для любого треугольника все точки из S за исключением точек, являющихся его вершинами, лежат вне окружности, описанной вокруг треугольника
правильно ли, что верная триангуляция (Делоне!) для подобного полигона: {{1, 1}, {1, 100}, {2, 100}, {2, 1}}
невозможна? Ведь окружность, проводимая из любого полученного треугольника будет содержать все точки полигона (прямоугольника).
Ответы (1 шт):
Подытожим то, что @user7860670 сказал (не корысти ради, а токмо ясности для ;)
1) Предложение в вики математически некорректно.
Должно быть - внутри описанной около него окружности не находится точек из исходного множества.
2) Проведём диагональ и построим окружность.
Можно видеть, что четвертая вершина прямоугольника тоже лежит на этой окружности, т.е. это случай, относящийся ко второму свойству из вики
Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.
Эта фраза тоже не фонтан, из английской более ясен смысл:
Four or more points on a perfect circle, where the triangulation is ambiguous and all circumcenters are trivially identical.
Действительно, можно провести другую диагональ, это тоже будет валидная триангуляция.
Триангуляция будет не единственной также в случае наличия четырехугольников с суммой противоположных углов, равной 180 градусов (вокруг которых можно описать окружность)