Какой самый эффективный способ выбрать точки внутри траектории

Question

Имея путь, например:

, состоящий из набора точек 'p'

У меня есть набор случайно расположенных точек, как внутри, так и снаружи.называется 'n'

Таким образом, сравнение всех точек внутри с точками на пути к случайным точкам, вероятно, будет экспоненциально сложным.Что-то вроде O (n) = n ^ p, если я не ошибаюсь Это O (n) = n * p

Так что для решения проблемы я думаю, что вы могли бы подразделитьпуть в минимальной области, которая полностью снаружи, и другая, которая полностью внутри.как на рисунке

Зеленый набор будет внутри, черный снаружи и оранжевый будет повторяться несколько раз

Возможно ли это, а главное, эффективно ли оно?

Answer 1

Подумайте о том, чтобы взглянуть на литературу по тестированию точек на полигонах.

Имея такое большое количество точек, я могу представить разумный и эффективный подход. Гораздо больше, чем эта итерация, которую вы пытаетесь сделать.

Answer 2

Каково оригинальное представление вашего пути?неявная функция?Параметрический?битовая карта?ломаная? ... ответ сильно зависит от этого

Answer 3

Подобный (т. Е. Геометрический, а не пространственный) подход может заключаться в том, чтобы сначала использовать выпуклую оболочку, чтобы исключить точки, которые определенно находятся вне траектории.

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

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

Answer 4

Лучшим вариантом может быть подход на основе выборки.Не фильтр частиц, но такая же идея.Последовательный метод Монте-Карло также стоит рассмотреть,Повторите пример метода несколько раз, пока у вас не получится достаточно хорошая карта.Вы можете настроить количество выборок и количество повторов, чтобы сбалансировать как эффективность, так и результат.

Answer 5

Конечно, это возможно.Но без какого-либо представления о том, как дорого это НАЙТИ в этих регионах, и как дорого это - разделить точки внутри и снаружи, невозможно оценить его эффективность.