Comments 23
Действительно, величина 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/
А в чём польза проверки двумерного условия Делоне для решения задачи триангуляции трёхмерного облака? Разве там не нужно строить альфа-сеть по трёхмерному аналогу триангуляции?
Если ориентация треугольников заранее известна (а во многих алгоритмах это так), можно подобрать знаки заранее, они останутся верными.
Два умножения в формуле (точнее, в алгоритме её вычисления) можно сократить:
Сначала сосчитали
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/
А в чём польза проверки двумерного условия Делоне для решения задачи триангуляции трёхмерного облака? Разве там не нужно строить альфа-сеть по трёхмерному аналогу триангуляции?
+4
Если ориентация треугольников заранее известна (а во многих алгоритмах это так), можно подобрать знаки заранее, они останутся верными.Проблема в том, что мы не знаем заранее, какой треугольник слева, а какой справа. При этом в зависимости от положения треугольника знак синуса меняется, а знак косинуса нет. Получается, что в зависимости от того, какой угол мы обозначим за альфа, меняется результат всего выражения, что не очень хорошо)
По поводу оптимизации вы правы, я почему-то об этом не задумывался.
А в чём польза проверки двумерного условия Делоне для решения задачи триангуляции трёхмерного облака? Разве там не нужно строить альфа-сеть по трёхмерному аналогу триангуляции?Я создавал модель поверхности, а эта задача сводится к двухмерной триангуляции т.к. глубину точки на время триангуляции можно опустить.
0
То есть, у вас есть проекция, в которой образы всех точек поверхности различны? Тогда понятно. Правда, обычно в таких случаях скан имеет более-менее регулярную структуру, позволяющую построить поверхность быстрее.
0
Если вершины обоих треугольников записаны в порядке «против часовой стрелки» (на вашем чертеже — P1,P0,P3 и P3,P2,P1), то после определения общего ребра формула получается единой, ни от чего больше она не зависит.
+1
Тоже хотел написать про это. Если решается задача треангуляции поверхности в 3D графике, то порядок следования вертексов определяет или определяется ориентацией треугольника. И тут все зависит от гладкости поверхности.
0
Да, тут я ошибся. Не могу вспомнить что заставило меня так думать.
0
Я предполагаю, теоретически, если в поверхности имеются глубокие вогнутости, то найдутся части поверхности, нормали которых противоположны. Но такие части не могут быть видны одновременно для 3D-сканера, как мне кажется.
Потому без четкого представления предмета и я не уверен, что порядок следования вертексов всегда заведомо известен.
Потому без четкого представления предмета и я не уверен, что порядок следования вертексов всегда заведомо известен.
0
Если это какой-нибудь ручной сканер (например, Faro ScanArm), то в скан легко могут попасть области с самой разной ориентацией. Но там двумерной триангуляцией уже не обойдёшься.
0
Работаю на аутсорсе, поступила такая задача. По каким-то не известным мне причинам компания всячески старается избегать использования сторонних библиотек.
0
У сторонних библиотек может неожиданно прекратиться поддержка, или у них может не оказаться версии для новой платформы. Мы так раза три попадались.
0
UFO just landed and posted this here
В тех случаях исходного кода не было.
Если бы нам захотелось использовать qhull, то первой проблемой было бы, что мы стараемся избегать кода на C/C++ (весь проект написан на C#). Сохранится ли на новой платформе совместимость C# и C++ (без изменения кода) — уже не очень понятно.
Свой код переносить, конечно, понадобится. И возможно, что понадобится отлавливать платформенно-зависимые места кода. Конечно, есть шанс, что сторонняя библиотека является абсолютно платформенно- и компиляторно-независимой, но стоит ли на это закладываться? А отлаживать ещё и её будет заметно сложнее.
И про лицензию я не понял: означает ли она, что весь код, включающий эту библиотеку, должен распространяться на таких же условиях?
Если бы нам захотелось использовать qhull, то первой проблемой было бы, что мы стараемся избегать кода на C/C++ (весь проект написан на C#). Сохранится ли на новой платформе совместимость C# и C++ (без изменения кода) — уже не очень понятно.
Свой код переносить, конечно, понадобится. И возможно, что понадобится отлавливать платформенно-зависимые места кода. Конечно, есть шанс, что сторонняя библиотека является абсолютно платформенно- и компиляторно-независимой, но стоит ли на это закладываться? А отлаживать ещё и её будет заметно сложнее.
И про лицензию я не понял: означает ли она, что весь код, включающий эту библиотеку, должен распространяться на таких же условиях?
0
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»? Уж не ко всей ли программе?
А как вообще выполнить пункт про рекламу? Действует ли он, если в рекламе какого-то чужого проекта указывается, что использовался наш софт? Должен ли наш клиент перечислять все открытые библиотеки, используемые в нашем коде?
0
Считается ли включение их кода в мою программу за «redistribution»?— Да, если вы распространяете вашу программу.
Если да, то получается, что я должен включить полный текст их лицензии в лицензию к своей программе…— Нет, достаточно включить текст в документацию или справку. Во многих программах (эппла, гугла и т.д.) в справке есть пункт, где перечислены лицензии всех используемых библиотек (которые этого требуют).
и к чему тогда будет относиться это «Redistribution… are permitted»? Уж не ко всей ли программе?— Нет. Только к этой библиотеке.
0
Мне кажется, это не та задача, которую вы быстро решите сами. Вроде как там очень много подводных камней, например, со случаями, когда несколько точек находятся в одной плоскости или близко к ней (и начинают влиять ошибки округления). Я понимаю ваши ограничения, но это не тот случай, мне кажется. Этот код открыт, он работает с 1996 года, у научной статьи, в которой описана идея быстрой реализации тесселяции, более 2000 цитат. Поддержка там, в общем-то, не требуется. Именно этот код используется, как я сказал (судя по их сайту), в R, Mathematica, Matlab, Octave, так что сомневаться в нем не приходится. В конце концов, вы можете просто включить исходники в проект. Это выглядит как реклама, но, опять же, мне кажется, вы просто потеряете очень много времени совершенно напрасно.
+3
Одним из наиболее численно устойчивых вариантов отыскания координат центра и радиуса описанной около симплекса произвольной размерности (отрезок, треугольник, тетраэдр, ...) сферы является вычисление определителя Кэли-Мэнгера.
Я вообще предпочитаю выкидывать всю тригонометрию и сводить все к матричным операциям.
Я вообще предпочитаю выкидывать всю тригонометрию и сводить все к матричным операциям.
0
В свое время немало времени потратил на поиск ошибок при построении триангуляции, периодически она зацикливалась. Оказалось, что если использовать для координат числа с плавающей точкой, то даже для чисел двойной точности можно подобрать пример, когда в практически вырожденном треугольнике результат вычислений будет зависеть от порядка вершин. Другого решения кроме как использования целочисленных координат я не нашел, и сомневаюсь, что оно в принципе существует.
+1
Sign up to leave a comment.
Ошибка в формуле проверки условия Делоне