Вычислительная геометрия, четырехгранник подписал объем
Я не уверен - ли это правильное место для выяснения, но здесь идет...
Короткая версия: я пытаюсь вычислить ориентацию треугольника на плоскости, сформированной пересечением 3 краев, явно не вычисляя точки пересечения.
Долгая версия: Я должен триангулировать PSLG на треугольнике в 3D. Вершины PSLG определяются пересечениями линейных сегментов с плоскостью через треугольник и, как гарантируют, лягут в треугольнике. Принятие меня имело точки пересечения, я мог спроектировать к 2D и использовать сторону строки точки (или треугольник подписал область), тест для определения ориентации треугольника между любыми 3 точками пересечения.
Проблема, я не могу явно вычислить точки пересечения из-за ошибки с плавающей точкой, которая накапливается, когда я нахожу плоское строкой пересечение. Чтобы выяснить, ударяют ли линейные сегменты треугольник во-первых, я использую некоторые устойчивые геометрические предикаты в свободном доступе, которые дают знак объема четырехгранника, или эквивалентно на какой стороне плоскости точка находится. Я могу определить, находятся ли конечные точки линейного сегмента на противоположных сторонах плоскости через треугольник, то формируют tetrahedra между линейным сегментом и каждым краем треугольника, чтобы определить, находится ли точка пересечения в треугольнике.
Так как я не могу явно вычислить точки пересечения, я задаюсь вопросом, существует ли способ выразить тот же 2D восток вычисление в 3D использовании только исходные точки. Если существует 3 края, ударяющие треугольник, который дает мне 9 точек всего для проигрывания с. Принятие, что я спрашиваю, даже возможно (использование только 3D востока тесты), затем я предполагаю, что должен буду сформировать некоторое подмножество всего возможного tetrahedra между теми 9 точками. У меня есть трудно даже визуализация этого, уже не говоря о дистилляции его в формулу или код. Я не могу даже погуглить это, потому что я не знаю то, чем терминология промышленного стандарта могла бы быть для этого типа проблемы.
Какие-либо идеи, как возобновить это?Спасибо. Возможно, я должен спросить MathOverflow также...
Править: После чтения некоторых комментариев, одна вещь, которая происходит со мной... Возможно, если я мог бы соответствовать неналожению tetrahedra между этими 3 линейными сегментами, затем ориентация любого из тех, которые пересекли плоскость, будет ответом, который я ищу. Кроме того, когда края включают простую треугольную призму, я не уверен, что эта подпроблема разрешима также.
Править: Требуемое изображение. 
4 ответа
Я отвечаю на этот вопрос как на MO, так и на SO, расширяя комментарии, которые я сделал на MO.
Мне кажется, что никакие вычислительные приемы с подписанными объемами тетраэдров не позволят избежать проблем с точностью, которые вас больше всего беспокоят. Это происходит потому, что если у вас есть плотно скрученные сегменты, ориентация треугольника зависит от точного позиционирования плоскости разреза.
[изображение удалено; см. ниже]
.
В приведенном примере верхняя плоскость пересекает сегменты в порядке (a,b,c) [ccw сверху]: (red,blue,green), а нижняя плоскость пересекает в обратном порядке (c,b,a): (green,blue,red). Высота
режущей плоскости может быть определена с последней точностью.
Следовательно, я думаю, имеет смысл просто продолжить и вычислить точки пересечения в плоскости разреза, используя достаточную точность, чтобы вычисления были точными. Если координаты конечных точек отрезка и коэффициенты плоскости имеют L бит точности, то необходимо лишь небольшое увеличение постоянного коэффициента. Хотя я не знаю точно, каков этот коэффициент, он невелик - возможно, 4. Вам не понадобится, например, L2 бит, потому что вычисления сводятся к решению линейных уравнений. Поэтому не произойдет взрывного роста точности, необходимой для точного вычисления.
Удачи!
(Мне не позволили разместить уточняющее изображение, потому что у меня нет репутации. См. ответ МО вместо этого.)
Правка: Смотрите ответ MO, но вот изображение:
Насколько я понимаю, у вас есть три линии, пересекающие плоскость, и вы хотите рассчитать ориентацию треугольника, образованного точками пересечения, без вычисление самих точек пересечения?
Если так: у вас есть плоскость
N·(x - x0) = 0
и шесть точек ...
l1a, l1b, l2a, l2b, l3a, l3b
...формирование трех линий
l1 = l1a + t(l1b - l1a) l2 = l2a + u(l2b - l2a) l3 = l3a + v(l3b - l3a)
Точки пересечения этих линий с плоскостью происходят при определенных значениях t, u, v, которые я назову t i , u i , v i
N·(l1a + ti(l1b - l1a) - x0) = 0
N·(x0 - l1a)
ti = ----------------
N·(l1b - l1a)
(similarly for ui, vi)
Тогда конкретные точки пересечения равны
intersect1 = l1a + ti(l1b - l1a) intersect2 = l2a + ui(l2b - l2a) intersect3 = l3a + vi(l3b - l3a)
Наконец, ориентация вашего треугольника равна
orientation = direction of (intersect2 - intersect1)x(intersect3 - intersect1)
(x - кросс-произведение) Работайте в обратном направлении, вставляя значения, и вы получите уравнение для ориентации основано только на N, x 0 и ваших шести точках.
Назовем вершины вашего треугольника T [0] , T [1] , T [2] , а конечные точки первого отрезка линии - ] L [0] и L [1] , второй - L [2] и L [3] , а третий - L [4] и L [5] . Я полагаю, вам нужна функция
int Orient(Pt3 T[3], Pt3 L[6]); // index L by L[2*i+j], i=0..2, j=0..1
, которая возвращает 1, если пересечения имеют ту же ориентацию, что и треугольник, и -1 в противном случае.
Результат должен быть симметричным при перестановке значений j , антисимметричным при перестановке значений i и индексов T . Пока вы можете вычислить величину с помощью этих симметрий, это все, что вам нужно.
Давайте попробуем
Sign(Product( Orient3D(T[i],T[i+1],L[2*i+0],L[2*i+1]) * -Orient3D(T[i],T[i+1],L[2*i+1],L[2*i+0]) ), i=0..2))
, где произведение должно быть взято на циклические перестановки индексов (по модулю 3). Я считаю, что у него есть все необходимые свойства симметрии. Orient3D - это четырехточечный тест ориентации плоскости Шевчука, который, как я полагаю, вы используете.
Я бы написал символические векторные уравнения, знаете, с точечными и перекрестными произведениями, чтобы найти нормаль треугольника пересечения. Затем, знак точечного произведения этой нормали и исходного треугольника дает ориентацию. В итоге это можно выразить в виде sign(F(p1,...,p9)), где p1 - p9 - ваши точки, а F() - уродливая формула, включающая точечные и перекрестные произведения разностей (pi-pj). Не знаю, можно ли сделать это проще, но этот общий подход делает свою работу.