在numpy中找到两个多边形之间的距离

问题描述

我有两个多边形P和Q，其中多边形的外部线性环由两个封闭的点集(存储为numpy数组)定义，它们以逆时针方向连接. P和Q的格式如下:

I have two polygons, P and Q, where the exterior linear ring of a polygon is defined by two closed sets of points, stored as numpy arrays, connected in a counterclockwise direction. P and Q are in the following format:

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]等形成的.每个数组的最后一个坐标与第一个数组相同，表示形状在拓扑上是封闭的.

The exterior ring of P is formed by joining P['x_coords'][0], P['y_coords'][0] -> P['x_coords'][1], P['y_coords'][1] etc. The last coordinate of each array is the same as the first, indicating that the shape is topologically closed.

是否可以使用numpy计算出P和Q的外圈之间的简单最小距离?我在SO方面进行了严格的搜索，没有找到任何明确的内容，因此我怀疑这可能是对一个非常复杂的问题的过分简化.我知道可以使用GDAL或Shapely等现成的空间库来完成距离计算，但是我很想通过在numpy中从头开始构建一些东西来了解它们的工作原理.

Is it possible to calculate a simple minimum distance between the exterior rings of P and Q geometrically using numpy? I have searched high and low on SO without finding anything explicit, so I suspect this may be a drastic oversimplification of a very complex problem. I am aware that distance calculations can be done with out-of-the-box spatial libraries such as GDAL or Shapely, but I'm keen to understand how these work by building something from scratch in numpy.

我已经考虑或尝试过的一些事情:

Some things I have considered or tried:

• 计算两个数组中每个点之间的距离.这不起作用，因为P和Q之间的最接近点可以是边顶点对.使用scipy.spatial计算的每种形状的凸包都存在相同的问题.
• 一种低效的蛮力方法，计算每对点之间以及每个边点对组合之间的距离

• Calculate the distance between each point in both arrays. This doesn't work as the closest point between P and Q can be an edge-vertex pair. Using the convex hull of each shape, calculated using scipy.spatial has the same problem.
• An inefficient brute force approach calculating the distance between every pair of points, and every combination of edge-point pairs

是否有更好的方法来解决此问题?

Is there a better way to go about this problem?

推荐答案

有很多 k上的href ="http://www.montefiore.ulg.ac.be/~poirrier/download/particle/poirrier-kdtree-pp1.pdf" rel ="nofollow noreferrer">变体 - d 树，用于存储具有范围的对象，例如多边形的边.我最熟悉(但没有链接)的方法涉及将轴对齐的边界框与每个节点相关联.叶子与对象相对应，内部节点的框是包围两个子节点的框(通常重叠)的最小框.通常的中位数切割方法适用于对象框的中点(对于线段，这是它们的中点).

There are many variations on a k-d tree for storing objects with extent, like the edges of your polygons. The approach with which I am most familiar (but have no link for) involves associating an axis-aligned bounding box with each node; the leaves correspond to the objects, and an internal node’s box is the smallest enclosing both of its children’s (which in general overlap). The usual median-cut approach is applied to the midpoints of the object’s boxes (for line segments, this is their midpoint).

为每个多边形构建了这些方法之后，下面的双重递归找到了最接近的方法:

Having built these for each polygon, the following dual recursion finds the closest approach:

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.

• The closest approach true_dist between two non-intersecting line segments must involve at least one endpoint.
• The distance between a point and a segment can be greater than that between the point and the line containing the segment.
• No point-point checks are needed: such a pair will be found (four times) via the adjacent edges.
• The bounding-box arguments to min_dist may be overlapping, in which case it must return 0.

这篇关于在numpy中找到两个多边形之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！