Как определить, находится ли точка внутри многоугольника в трехмерном пространстве?

Question

У меня есть 3D-точка P (x, y, z) и многоугольник S, определяемый произвольным количеством 3D-точек. Полигон необязательно выпуклый (поэтому, на мой взгляд, приведенные решения здесь не отвечают на мой вопрос), но P находится в той же плоскости, что и S. Теперь мне нужно определить, находится ли P внутри С.

Например:

polygon = np.array([[6173.953125  , 9689.90136719,  298.03326416],
       [6173.95410156, 9689.90136719,  298.09350586],
       [6173.89355469, 9689.86621094,  298.23690796],
       [6173.89355469, 9689.86621094,  298.23690796],
       [6173.83496094, 9689.83398438,  298.5083313 ],
       [6173.89453125, 9689.86816406,  298.38320923],
       [6173.89697266, 9689.87011719,  298.44348145],
       [6173.89697266, 9689.87011719,  298.44348145],
       [6173.953125  , 9689.90136719,  298.03326416],
       [6173.89355469, 9689.86621094,  298.23690796],
       ...
       ])

point = np.array([6171.37079656, 9688.35796064,  309.00229108])

Пример изображения: точка вне полигона:

В этом примере очевидно, что результатом должно быть «Ложь» (точка находится вне).

Используя точку:

point2 = np.array([6173.83496094, 9689.83398438, 297.72579346])

результат должен быть "True" (точка в многоугольнике).

Пример изображения: точка внутри многоугольника:

Я знаю, что в основном мне нужно решить простую задачу Point-in-Polygon (PiP). Тем не менее, есть ли пакет, который включает такую ​​функцию напрямую? Или как я могу преобразовать все точки, чтобы применить алгоритмы PiP, предоставляемые в форме или аналогичных пакетах?

Answer 1

Когда гарантируется P is in the same plane as S, сделайте (виртуальную) проекцию многоугольника и укажите на любую координатную плоскость (не перпендикулярную плоскости многоугольника). Например, чтобы проецировать на OXZ (подходит для второго примера), просто игнорируйте Y-компоненты.

Затем используйте любой алгоритм, предназначенный для 2D ( pnpoly )