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

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

Например:

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» (точка в многоугольнике).

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

Я знаю, что в основном мне нужно решить простую задачу «точка в многоугольнике» (PiP). Однако существует ли пакет, который включает такую ​​функцию напрямую? Или как я могу преобразовать все точки для применения алгоритмов PiP, предоставляемых shapely или аналогичными пакетами?


python 3d geometry point-in-polygon
person trippeljojo    schedule 27.06.2019    source источник
comment
Разве многоугольник не выпуклый по определению?   -  person BlueRine S    schedule 27.06.2019
comment
@BlueRineS Нет. en.wikipedia.org/wiki/Concave_polygon   -  person cdrom    schedule 27.06.2019
comment
Этот многоугольник плоский? В противном случае внутри него не может быть никаких точек.   -  person Tiendung    schedule 27.06.2019
comment
Многоугольники плоские.   -  person trippeljojo    schedule 27.06.2019
comment
Если бы сегменты были квадратными, вы могли бы использовать AABB (ограничивающая рамка с выравниванием по оси)   -  person BlueRine S    schedule 27.06.2019
comment
google: hit test и perpendicular distance between point and plane ...   -  person Spektre    schedule 27.06.2019
comment
Возможный дубликат Определение того, находится ли точка в 3D-поли в Python   -  person Georgy    schedule 17.07.2019

Ответы (1)


arrow_upward
3
arrow_downward

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

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

person MBo    schedule 27.06.2019
comment
Спасибо за подсказку и особенно за ссылку. После проецирования в 2D я мог просто использовать point.within(polygon) из пакета shapely. - person trippeljojo; 28.06.2019