Линейный сегмент Пересечение 3D-выпуклого непланарного многоугольника

Question

Я пытаюсь найти достаточно оптимальный алгоритм для определения того, пересекает ли отрезок линии трехмерный выпуклый непланарный многоугольник. Лучшее, что я могу сейчас увидеть, это нарисовать линию, которая разбивает непланарный многоугольник пополам, определяет, лежит ли отрезок линии справа или слева от линии расщепления, а затем продолжайте разделение, пока не смогу определить пересечение. Причина этого заключается в том, что я могу определить, в какой области 3d сферической диаграммы воронной точки находится данная точка. Тем не менее, время найти решение может стать зависящим от поплавкового разрешения моих разделов строк.

Диаграмма

неплоский многоугольники Пример

В этом примере, я бы рисовать отрезок между голубыми точками и центром блока сферы (добавленной после вычисления voronoi, они не являются точками, используемыми для вычисления диаграммы). Затем мне нужно выяснить, какой полигон пересекает этот сегмент линии, чтобы определить, в какой области он находится.

Answer 1

Это можно решить с помощью геометрии координат.

Сначала разделите многоугольник на треугольники. Например, если многоугольник ABCDE рассматривает треугольники ABC, ACD и ADE. В вашей проблеме сегмент линии пересекает многоугольник тогда и только тогда, когда он пересекает хотя бы один треугольник. Мы проверим, пересекает ли этот отрезок треугольник следующим образом.

Пусть треугольник KLM, а отрезок линии - УФ. Уравнение плоскости, содержащей KLM, будет иметь вид ax + на + cz + d = 0, а уравнение линии, содержащее UV, будет иметь вид (x-x_0)/e = (y-y_0)/f = (г-z_0)/г. Решая эти уравнения одновременно, мы можем найти координаты P = (x, y, z) пересечения прямой и плоскости.

После того, как P найден, мы должны убедиться, что он лежит как на УФ, так и на KLM. Первое верно, если сумма расстояний от P до U и V равна длине УФ. Для последнего проверьте, добавляются ли области треугольников, образованных P и краями KLM (то есть PKL, PLM и PMK), к области KLM.