Точка в многоугольнике для большого количества точек

Question

Мне интересно, что может быть наиболее эффективным способом определения того, находится ли большое количество точек (O (1 миллион) внутри или снаружи набора (O (10)) многоугольников? Последние не обязательно выпуклые,но в них нет дыр. В настоящее время я сокращаю количество точек, сравнивая их положения с ограничивающими прямоугольниками, а затем использую этот метод пересечения чисел в оставшихся точках. Но, возможно, быстрееметод?

Answer 1

Для этого есть эффективная функция matplotlib: matplotlib.nxutils.points_inside_poly () .Алгоритм задокументирован на этой странице .

Answer 2

Предполагая, что у вас есть выровненные по оси ограничивающие блоки, вы можете отсортировать список точек по их координате x, найти места в точках списка, находящиеся внутри или снаружи ограничивающих рамок, с помощью бинарного поиска и потенциально отбросить большое количество точек в один раз. Повторите для координаты y. Затем продолжайте, как и раньше, с остальными точками. Вы можете выполнить полигональную триангуляцию, чтобы ускорить тестирование внутри ограничительной рамки.

Лучше всего будет работать, если площадь плоскости намного больше площади многоугольников, а многоугольники достаточно компактны (то есть не длинные и не тонкие, что может дать вам много ложных срабатываний).

Answer 3

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

Каждый поиск - это O (log n), что будет примерно так быстро, как вы сможете получить.Для точек, которые лежат в ячейке квадродерева, которая помечена как «содержит ребро», вам придется выполнить традиционный тест точка-полигон.