Ошибка в формуле проверки условия Делоне

[@Mrrl]

Действительно, величина x1*y2-y1*x2 равна ориентированной площади параллелограмма, построенного на векторах (x1,y1) и (x2,y2), то есть, его знак зависит от взаимной ориентации векторов. В этом смысле лучше действительно брать модули разности. Кстати, в написанной у вас формуле одна из разностей всегда будет положительной, а другая отрицательной — в одной паре векторы идут по часовой стрелке, а в другой — против.
Если ориентация треугольников заранее известна (а во многих алгоритмах это так), можно подобрать знаки заранее, они останутся верными.

Два умножения в формуле (точнее, в алгоритме её вычисления) можно сократить:
Сначала сосчитали
p1=(x0-x1)*(x0-x3)
p2=(y0-y1)*(y0-y3)
Проверили знак суммы (для оптимизированного алгоритма).
Теперь величина (x0-x1+y0-y1)*(y0-y3-x0+x3)+p1-p2 будет как раз равна (x0-x1)*(y0-y3)-(y0-y1)*(x0-x3). И нам хватило трёх умножений вместо четырёх.
То же можно сделать со второй парой векторов.

Задача подробно разбиралась здесь: habrahabr.ru/post/149911/

А в чём польза проверки двумерного условия Делоне для решения задачи триангуляции трёхмерного облака? Разве там не нужно строить альфа-сеть по трёхмерному аналогу триангуляции?

[@maxim_0_o]

Если ориентация треугольников заранее известна (а во многих алгоритмах это так), можно подобрать знаки заранее, они останутся верными.

Проблема в том, что мы не знаем заранее, какой треугольник слева, а какой справа. При этом в зависимости от положения треугольника знак синуса меняется, а знак косинуса нет. Получается, что в зависимости от того, какой угол мы обозначим за альфа, меняется результат всего выражения, что не очень хорошо)

По поводу оптимизации вы правы, я почему-то об этом не задумывался.

А в чём польза проверки двумерного условия Делоне для решения задачи триангуляции трёхмерного облака? Разве там не нужно строить альфа-сеть по трёхмерному аналогу триангуляции?

Я создавал модель поверхности, а эта задача сводится к двухмерной триангуляции т.к. глубину точки на время триангуляции можно опустить.

[@Mrrl]

То есть, у вас есть проекция, в которой образы всех точек поверхности различны? Тогда понятно. Правда, обычно в таких случаях скан имеет более-менее регулярную структуру, позволяющую построить поверхность быстрее.

[@maxim_0_o]

Вы правильно меня поняли. Подскажите пожалуйста, каким способом можно сделать это быстрее? Буду признателен.

[@Mrrl]

Сначала скажите, откуда скан (с какого типа сканеров) и в каком он формате.

[@Mrrl]

Если вершины обоих треугольников записаны в порядке «против часовой стрелки» (на вашем чертеже — P1,P0,P3 и P3,P2,P1), то после определения общего ребра формула получается единой, ни от чего больше она не зависит.

[@HomoLuden]

Тоже хотел написать про это. Если решается задача треангуляции поверхности в 3D графике, то порядок следования вертексов определяет или определяется ориентацией треугольника. И тут все зависит от гладкости поверхности.

[@maxim_0_o]

Да, тут я ошибся. Не могу вспомнить что заставило меня так думать.

[@HomoLuden]

Я предполагаю, теоретически, если в поверхности имеются глубокие вогнутости, то найдутся части поверхности, нормали которых противоположны. Но такие части не могут быть видны одновременно для 3D-сканера, как мне кажется.
Потому без четкого представления предмета и я не уверен, что порядок следования вертексов всегда заведомо известен.

[@Mrrl]

Если это какой-нибудь ручной сканер (например, Faro ScanArm), то в скан легко могут попасть области с самой разной ориентацией. Но там двумерной триангуляцией уже не обойдёшься.

[@Bas1l]

А если не секрет, почему вам не подходит, в общем-то, стандартная реализация тесселяции Делоне, qhull? Быстрый, надежный, справляется со всеми подводными камнями, ошибками округления и т.п. Матлаб, к примеру, использует именно эту библиотеку под капотом.

[@maxim_0_o]

Работаю на аутсорсе, поступила такая задача. По каким-то не известным мне причинам компания всячески старается избегать использования сторонних библиотек.

[@Mrrl]

У сторонних библиотек может неожиданно прекратиться поддержка, или у них может не оказаться версии для новой платформы. Мы так раза три попадались.

[@Mrrl]

В тех случаях исходного кода не было.
Если бы нам захотелось использовать qhull, то первой проблемой было бы, что мы стараемся избегать кода на C/C++ (весь проект написан на C#). Сохранится ли на новой платформе совместимость C# и C++ (без изменения кода) — уже не очень понятно.
Свой код переносить, конечно, понадобится. И возможно, что понадобится отлавливать платформенно-зависимые места кода. Конечно, есть шанс, что сторонняя библиотека является абсолютно платформенно- и компиляторно-независимой, но стоит ли на это закладываться? А отлаживать ещё и её будет заметно сложнее.
И про лицензию я не понял: означает ли она, что весь код, включающий эту библиотеку, должен распространяться на таких же условиях?

[@Bas1l]

Мне кажется, писать тесселяцию (особенно больших мешей) на C#—довольно рискованно само по себе. Хотя, конечно, С++ трудностей добавит.

Лицензия, наоборот, пермиссивная—вы можете делать с кодом, по сути, что угодно, только указывать в дистрибутиве и рекламе, что внутри используется qhull.

[@Mrrl]

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
…
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

Считается ли включение их кода в мою программу за «redistribution»? Если да, то получается, что я должен включить полный текст их лицензии в лицензию к своей программе… и к чему тогда будет относиться это «Redistribution… are permitted»? Уж не ко всей ли программе?
А как вообще выполнить пункт про рекламу? Действует ли он, если в рекламе какого-то чужого проекта указывается, что использовался наш софт? Должен ли наш клиент перечислять все открытые библиотеки, используемые в нашем коде?

[@encyclopedist]

Считается ли включение их кода в мою программу за «redistribution»?

— Да, если вы распространяете вашу программу.

Если да, то получается, что я должен включить полный текст их лицензии в лицензию к своей программе…

— Нет, достаточно включить текст в документацию или справку. Во многих программах (эппла, гугла и т.д.) в справке есть пункт, где перечислены лицензии всех используемых библиотек (которые этого требуют).

и к чему тогда будет относиться это «Redistribution… are permitted»? Уж не ко всей ли программе?

— Нет. Только к этой библиотеке.

[@Bas1l]

Мне кажется, это не та задача, которую вы быстро решите сами. Вроде как там очень много подводных камней, например, со случаями, когда несколько точек находятся в одной плоскости или близко к ней (и начинают влиять ошибки округления). Я понимаю ваши ограничения, но это не тот случай, мне кажется. Этот код открыт, он работает с 1996 года, у научной статьи, в которой описана идея быстрой реализации тесселяции, более 2000 цитат. Поддержка там, в общем-то, не требуется. Именно этот код используется, как я сказал (судя по их сайту), в R, Mathematica, Matlab, Octave, так что сомневаться в нем не приходится. В конце концов, вы можете просто включить исходники в проект. Это выглядит как реклама, но, опять же, мне кажется, вы просто потеряете очень много времени совершенно напрасно.

[@igor_suhorukov]

Ладно, это мы с вами знаем что такое opensource) Пусть заказчики оплачивают очередные велосипеды!!!

[@gbg]

Одним из наиболее численно устойчивых вариантов отыскания координат центра и радиуса описанной около симплекса произвольной размерности (отрезок, треугольник, тетраэдр, ...) сферы является вычисление определителя Кэли-Мэнгера.
Я вообще предпочитаю выкидывать всю тригонометрию и сводить все к матричным операциям.

[@JagaJaga]

Если интересно, то вот отличный конспект от моей одногруппницы про триангуляцию Делоне.

[@GraD_Kh]

В свое время немало времени потратил на поиск ошибок при построении триангуляции, периодически она зацикливалась. Оказалось, что если использовать для координат числа с плавающей точкой, то даже для чисел двойной точности можно подобрать пример, когда в практически вырожденном треугольнике результат вычислений будет зависеть от порядка вершин. Другого решения кроме как использования целочисленных координат я не нашел, и сомневаюсь, что оно в принципе существует.