Поиск точек в 2D-области

Question

У меня очень большой набор данных, состоящий из (x, y) координат. Мне нужно знать, какая из этих точек находится в определенных областях 2D-пространства. Эти области ограничены 4 линиями в 2D-области (некоторые стороны слегка изогнуты).

Для меньших наборов данных я использовал громоздкий цикл для проверки каждой отдельной точки для членства в каждом регионе. Это больше не похоже на хороший вариант из-за размера набора данных.

Есть ли лучший способ сделать это?

Например:

Если у меня есть множество точек: (0,1) (1,2) (3,7) (1,4) (7,5)

и область, ограниченная линиями:

y=2 
y=5 
y=5*sqrt(x) +1 
x=2 

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

Спасибо.

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

point_list = [] 
for i in range(num_po): 
    a=5*sqrt(points[i,0]) +1 
    b=2 
    c=2 
    d=5 

    if (points[i,1]<a) && (points[i,0]<b) && (points[i,1]>c) && (points[i,1]<d): 
     point_list.append(points[i]) 

Это не точный код, но должен дать представление о том, что я пытался.

Answer 1

Это называется range searching problem и является очень изученной проблемой в вычислительной геометрии. Тема довольно связана (с вашим квадратным корнем, что делает вещи нелинейными, следовательно, более сложными). Here - хорошая запись в блоге об использовании SciPy для выполнения вычислительной геометрии в Python.

Answer 2

Если у вас есть одно (или небольшое число) регионов, тогда будет трудно сделать намного лучше, чем проверять каждую точку. Проверка на точку может быть быстрой, особенно если вы сначала выбираете самую быструю или наиболее дискриминирующую проверку (например, в вашем примере, возможно, x> 2).

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

Я использую пакет pton Rtree для пространственной индексации и нахожу его очень эффективным.

Answer 3

Длинный комментарий:

Вы не говорите нам всю историю.

Если у вас есть этот большой набор точек (скажем, N из них) и один набор из этих криволинейных четырехугольников (скажем, M из них), и вам нужно решить проблему один раз, вы не можете избежать исчерпывающего тестирования всех пунктов против принятия площадь.

В любом случае, вы можете, вероятно, предварительно обработать области M таким образом, чтобы при тестировании точки против области принятия принималось меньше, чем M операций (ближе к Log (M)). Но из-за небольшой величины M большие сбережения маловероятны.

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

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

Вы должны рассказать нам еще и показать примерный случай.