#### Введение

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

[1]: https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%94%D0%B5%D0%BB%D0%BE%D0%BD%D0%B5
[2]: http://www.pandia.ru/wp-content/uploads/2010/12/wpid-image0183.jpg
[3]: http://habrahabr.ru/post/252925/#habracut