Получите очки, заключенные в 3D-многоугольник

Question

У меня есть многоугольник, который лежит на трехмерной плоскости. Я хочу, чтобы все точки были заключены в этот полигон. Кто-нибудь может мне помочь? Я могу создать алгоритм линий трехмерного сканирования, заменив линии сканирования плоскостями и получить пересечение плоскостей с моим многоугольником, но мне нужно более быстрое решение. Заранее спасибо.

Answer 1

Один из подходов, который я вижу сейчас, - это выстрелить случайный произвольный луч из каждой точки, которую вы хотите проверить, и подсчитать, сколько раз он пересекается с поверхностью вашей 3d-сетки. Если он нечетный - он внутри, если даже - снаружи.

Answer 2

Если ваш многоугольник выпуклый, то вы можете использовать следующий подход:

Каждая грань многоугольника является частью плоскости, заданной уравнением ax + by + cz = d. Найдите это уравнение для всех граней, измените их на < d или > d в зависимости от того, какое отношение описывает точки внутри многоугольника, затем решите эту систему линейных неравенств. Это должно дать вам набор отношений для x, y и z, которым удовлетворяют только точки внутри многоугольника.

Answer 3

Ответ CygnusX1 является стандартным тестом «точка-в-полигоне» и может быть изменен для различных систем (например, у меня есть версия, закодированная для работы на сфероиде). Главный трюк при его адаптации - это выбор направления луча. «Abitrary» - гораздо лучшее слово, чем «случайный». Для 2d евклидовой работы я бы снимал ее в направлении, параллельном одной из осей (и перпендикулярно другой). Для сферы вы используете один из полюсов. Для двумерного плоского многоугольника в 3d я бы хотел выбрать линию, перпендикулярную одной из осей.

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

Answer 4

"да, это выпуклый 3-мерный многоугольник, но все его точки лежат в одной плоскости"

В этом случае - просто конвертируйте многоугольник и все контрольные точки в двухмерные локальные координаты плоскости и используйте2D-алгоритм:

• Съемка 2D-лучей: Вы все еще можете использовать алгоритм, аналогичный моему 3D-предложению - снимать 2D-лучи, исходящие из вашей контрольной точки, и подсчитывать, сколько раз вы попали на границу вашегомногоугольник.

• Линейные неравенства: если ваш многоугольник выпуклый, вы можете следовать подходу Сузтерпатта, где ваш многоугольник определен как пересечение полуплоскостей ax+by<d

Дальнейшее чтение:

• http://en.wikipedia.org/wiki/Point_in_polygon
• http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
• http://paulbourke.net/geometry/insidepoly/

Answer 5

Я видел нечто подобное, реализованное с использованием одного из matplotlib / scipy / numpy.Однако я не могу точно запомнить алгоритм, посмотрите, поможет ли этот .

Answer 6

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