Введение
Ранним воскресным утром я уже третий день сидел за отладкой программы для триангуляции результата лазерного сканирования. Лазерный скан представляет из себя набор трехмерных точек. В результате работы программы нужно объединить точки в непересекающиеся полигоны, таким образом создав модель поверхности. Функцию за функцией я пересчитывал на листочке и, наконец, добрался до функции проверки выполнения условия Делоне. По всей видимости, ошибка затаилась где-то в ней. При детальном разборе оказалось, что формула, указанная в огромном количестве книг про триангуляцию Делоне, не всегда дает верный результат. Подробности под катом.
Условие Делоне
Расскажу кратко о самом условии Делоне. К слову, всю информацию я черпал из замечательной книги А.В. Скворцова «Триангуляция Делоне и её применение». Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции. Выполнение этого условия нужно для того, что бы максимизировать сумму минимальных углов всех треугольников триангуляции. Проще говоря, чтобы треугольники не были сплюснутыми.
Автор предлагает 2 способа проверки условия Делоне с возможностью оптимизации для каждого из них.
Первый способ наиболее очевидный. Он предлагает вычислить центр и радиус описанной окружности и напрямую проверить принадлежность вершин соседних треугольников. В качестве оптимизации предлагается хранить вычисленные описанные окружности в классе треугольника. Не оптимизированная проверка требует 29 операций умножения и деления и 24 операции сложения и вычитания. Сложность оптимизированной проверки зависит от алгоритма триангуляции.
Второй способ уже интереснее. Он утверждает, что для проверки условия достаточно, чтобы для любого соседнего треугольника сумма противолежащих вершин не превышает ПИ (
), что эквивалентно условию: 
.
Далее после приведений и преобразований получается довольно страшная формула: 
Формула соответствует синусу суммы: 
, где косинусы и синусы выражены через формулу скалярного и псевдоскалярного произведения соответственно. В формулах опущено произведение длин векторов (видимо потому что оно не влияет на знак выражения).
В качестве оптимизации предлагается сначала вычислить знаки косинусов. Если 
и 
, значит 
и 
т.е. условие Делоне выполняется. Если 
и 
, значит 
и 
, условие не выполняется. В противном случае следует выполнять проверку по полной формуле.
Проверки по полному условию требует 10 операций умножения/деления и 13 операций сложения/вычитания. Оптимизированная проверка, по утверждениям автора книги, требует примерно 7 операций умножения/деления и 9 операций сложения/вычитания.
После ознакомления с этой информацией я сделал логичный вывод, что последний способ оптимальнее остальных и стал использовать его. Как говорится, ничто не предвещало беды.
Подводные камни
В ходе отладки я стал замечать неадекватное поведение функции проверки условия Делоне. Проблема оказалась в том, что от порядка перечисления вершин зависит знак синуса. Таким образом, из-за знака синуса меняется знак всего выражения. Может быть, я чего-то не понимаю, буду рад, если кто-то меня поправит.
Первый и единственный способ исправить ситуацию, который пришел мне в голову — это взять выражение синуса по модулю. Таким образом, синус показывает только величину угла, а не направление развертки, что нам и на руку.
Заключение
Для меня очень удивительно, что в огромном количестве книг указывается эта формула. При чем речь идет не только о русскоязычной литературе, вот здесь публикация, в которой указывается та же самая информация.
Я не большой специалист в математике, поэтому жду от сообщества адекватной критики и предложений. Готов к обсуждению.
Спасибо за внимание.
Автор: maxim_0_o
