Погрешность формулы проверки условия Делоне

Погрешность формулы проверки условия Делоне

357
ПОДЕЛИТЬСЯ

Итог должен объединить точки в непересекающихся полигонов, создавая тем самым модель поверхности. Детали под катом. Видимо, ошибка была спрятана в нем. При детализированном анализе оказалось, что формулы, указанной в большом количестве книжек о триангуляции Делоне не постоянно дает верный итог. Введение
Ранешным воскресным днем я был уже 3-ий день посиживал на отладку программы для триангуляции лазерного сканирования. Лазерное сканирование-это набор трехмерных точек. Функция функция, я подсчитал на листке бумаги и, в конце концов, добрались до теста функция выполнения условия Делоне.

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