Найти расстояние между двумя полигонами в NumPy

Question

У меня есть два многоугольника, P и Q, где внешнее линейное кольцо многоугольника определяется двумя закрытыми наборами точек, которые хранятся в виде массивов, соединенных в направлении против часовой стрелки. P и Q имеют следующий формат:

P['x_coords'] = [299398.56 299402.16 299410.25 299419.7  299434.97 299443.75 299454.1 299465.3  299477.   299488.25 299496.8  299499.5  299501.28 299504. 299511.62 299520.62 299527.8  299530.06 299530.06 299525.12 299520.2 299513.88 299508.5  299500.84 299487.34 299474.78 299458.6  299444.66 299429.8  299415.4  299404.84 299399.47 299398.56 299398.56] 
P['y_coords'] = [822975.2  822989.56 823001.25 823005.3  823006.7  823005.06 823001.06 822993.4  822977.2  822961.   822943.94 822933.6  822925.06 822919.7 822916.94 822912.94 822906.6  822897.6  822886.8  822869.75 822860.75 822855.8  822855.4  822857.2  822863.44 822866.6  822870.6  822876.94 822886.8  822903.   822920.3  822937.44 822954.94 822975.2]

Q['x_coords'] = [292316.94 292317.94 292319.44 292322.47 292327.47 292337.72 292345.75 292350.   292352.75 292353.5  292352.25 292348.75 292345.75 292342.5 292338.97 292335.97 292333.22 292331.22 292329.72 292324.72 292319.44 292317.2  292316.2  292316.94]
Q['y_coords'] = [663781.   663788.25 663794.   663798.06 663800.06 663799.3  663796.56 663792.75 663788.5  663782.   663773.25 663766.   663762.   663758.25 663756.5  663756.25 663757.5  663761.   663763.75 663767.5  663769.5 663772.25 663777.5  663781.  ]

## SIMPLIFIED AND FORMATTED FOR EASY TESTING:
import numpy as np

px_coords = np.array([299398,299402,299410.25,299419.7,299398])
py_coords = np.array([822975.2,822920.3,822937.44,822954.94,822975.2])

qx_coords = np.array([292316,292331.22,292329.72,292324.72,292319.44,292317.2,292316])
qy_coords = np.array([663781,663788.25,663794,663798.06,663800.06,663799.3,663781])

Внешнее кольцо P формируется путем соединения P['x_coords'][0], P['y_coords'][0] -> P['x_coords'][1], P['y_coords'][1] и т. Д. Последняя координата каждого массива такая же, как и первая, что указывает на то, что форма имеет видтопологически замкнутый.

Можно ли рассчитать простое минимальное расстояние между внешними кольцами P и Q, геометрически используя numpy? Я искал максимум и минимум SO, но не нашел ничего явного, поэтому я подозреваю, что это может быть радикальным упрощением очень сложной проблемы. Мне известно, что вычисления расстояний можно выполнять с помощью готовых пространственных библиотек, таких как GDAL или Shapely, но мне интересно понять, как они работают, создавая что-то с нуля.

Некоторыевещи, которые я рассмотрел или попробовал:

• Рассчитайте расстояние между каждой точкой в ​​обоих массивах. Это не работает, так как ближайшая точка между P и Q может быть парой ребро-вершина. Использование выпуклой оболочки каждой формы, рассчитанной с использованием scipy.spatial, имеет ту же проблему.
• Неэффективный метод грубой силы, вычисляющий расстояние между каждой парой точек и каждой комбинацией пар ребер-точек

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

Answer 1

Существует много вариантов в дереве k - d для хранения объектов с экстентом, например, ребер ваших полигонов. Подход, с которым я наиболее знаком (но не имею ссылки), включает в себя привязку ограничивающего прямоугольника к каждому узлу;листья соответствуют объектам, и коробка внутреннего узла является наименьшей, охватывающей обоих его дочерних элементов (которые в общем перекрываются). Обычный подход с медианным разрезом применяется к средним точкам ящиков объекта (для отрезков это их средняя точка).

Построив их для каждого многоугольника, следующая двойная рекурсия находитближайший подход:

def closest(k1,k2,true_dist):
  return _closest(k1,0,k2,0,true_dist,float("inf"))

def _closest(k1,i1,k2,i2,true_dist,lim):
  b1=k1.bbox[i1]
  b2=k2.bbox[i2]
  # Call leaves their own single children:
  cc1=k1.child[i1] or (i1,)
  cc2=k2.child[i2] or (i2,)
  if len(cc1)==1 and len(cc2)==1:
    return min(lim,true_dist(i1,i2))
  # Consider 2 or 4 pairs of children, possibly-closest first:
  for md,c1,c2 in sorted((min_dist(k1.bbox[c1],k2.bbox[c2]),c1,c2)
                         for c1 in cc1 for c2 in cc2):
    if md>=lim: break
    lim=min(lim,_closest(k1,c1,k2,c2,true_dist,lim)
  return lim

Примечания:

• Ближайший подход true_dist между двумя непересекающимися отрезками линии должен включать хотя бы одну конечную точку.
• Расстояние между точкой и отрезком может быть больше, чем расстояние между точкой и линией, содержащей отрезок.
• Проверка точечной точки не требуется: такая пара будет найдена (четыре раза) через соседниеребра.
• Аргументы ограничивающего прямоугольника для min_dist могут перекрываться, и в этом случае он должен возвращать 0.