Проверка того, лежит ли тетраэдр внутри многогранника

У меня есть тетраэдр и многогранник . ограничен так, что он всегда разделяет все свои вершины с . Я хочу определить, находится ли внутри .п т п т $t$ $p$$t$$p$$t$ $p$

Я хотел бы добавить одну деталь к проблеме в случае, если она может внести вклад в решение: - тетраэдр Делоне, а грани p треугольные и сильно Делоне, как по отношению к вершинам p . Тетраэдр - это Делоне, если в окружности его вершин нет другой вершины. Грани сильно Делоне, если на ее поверхности существует окружность, содержащая вершины этой грани, но нет другой вершины на ней или внутри нее.$t$$p$$p$

Эти цифры показывают ту же проблему в пространстве: $2D$

Исходный многоугольник $p$ :

Триангуляция Делоне вершин $p$ :

Результат внутреннего / внешнего теста по треугольникам $t$ (заштрихованные треугольники находятся внутри а остальные снаружи ):$p$

Желаемый результат (обрезка за пределами треугольников) :

Моя первоначальная проблема заключается в трехмерном пространстве, поэтому треугольники на приведенных выше рисунках переводятся в тетраэдры, а многоугольник p - в произвольный многогранник p . Я выяснил некоторые формулировки этой проблемы:$t$$p$$p$

Формулировка 1
Единственные части $t$ которые могут быть вне являются его ребра и треугольные грани, но в целом может существовать p, у которого есть ребра всех внешних t на его поверхности, поэтому в качестве альтернативы, эта проблема также может быть сформулирована так: проверить, существует ли для тетраэдра t грань, лежащая вне p ?$p$$p$ $t$$t$ $p$

Формулировка 2 У
меня есть другая возможная точка зрения на эту проблему, но у нее нет формальной идеи:
геометрически, если находится снаружи, он всегда будет прилипать к внешней поверхности p . Так что, если мы можем вычислить контуры (неофициально, внешнюю границу) C V и C V p так , что V = V t$t$$p$$C_{V}$$C_{V_{p}}$ и V t , V p были множествами вершин в t , p соответственно, то$V=V_{t}\cup V_{p}$$V_t,V_p$$t,p$ еслиtлежит внутриp. $C_{V}=C_{V_p}$ $t$$p$

Я бы хотел знать:

• Как я могу решить Формула 1 или Формула 2 ?
• Или есть какой-то совершенно иной подход к решению этой проблемы?

$t$$p$ $p$$t$ $p$

$p$

Исходя из вышеизложенного, моя основная проблема теперь, кажется, такова (пожалуйста, предложите, если это нужно задать как отдельный вопрос):
есть ли численно надежный алгоритм для задачи точки в многоугольнике ?

Недавно я нашел одно решение этой проблемы в статье Алекса Якобсона и др . «Прочная внутренняя и внешняя сегментация с использованием обобщенных чисел обмоток», здесь . Это решает проблему определения местоположения, если точка находится внутри (или снаружи) произвольной (с самопересечениями, немногообразием, открытыми поверхностями и т. Д.) Полигональной сетки, используя понятие обобщенного числа обмоток .

$t$$p$ .