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