2

我有一组两组二维点。我想根据欧几里得坐标查看集合 B 是否完全或部分包含在集合 A 的凸包中。

为了解释包含以下示例可能会有所帮助

让我们考虑以下集合

   A={(5,5),(10,10),(5,10),(0,5)}

   B={(3,3),(5,8)} partially included in convex hull of A

   C={(1,5),(5,8)} fully included in convex hull of A

   D={(1,1),(3,3)} is not included in convex hull of A

非常感谢

4

2 回答 2

2

在 Python 中找到一组点的凸包的一种方法是Delaunay使用scipy.spatial. 给定一组点，它返回一个具有convex_hull属性的对象 - 这是一个数组，由原始点集的索引对组成，这些索引对应于多边形上的边。恼人的是，这些没有排序，因此需要重建包含这些点的多边形（例如，如下所示）：

import numpy as np
import matplotlib.nxutils
import scipy.spatial

def find_convex_hull(points):
  triangulation = scipy.spatial.Delaunay(points)
  unordered = list(triangulation.convex_hull)
  ordered = list(unordered.pop(0))
  while len(unordered) > 0:
    next = (i for i, seg in enumerate(unordered) if ordered[-1] in seg).next()
    ordered += [point for point in unordered.pop(next) if point != ordered[-1]]
  return points[ordered]

正如@user1443118 所建议的那样，points_inside_poly函数 inmatplotlib.nxutils然后可用于测试点是否位于生成的多边形中，该多边形对应于凸包。这导致了以下用于计算相交度的函数。

def inclusion(points_a, points_b):
  ch_a = find_convex_hull(points_a)
  return (1.0 * matplotlib.nxutils.points_inside_poly(points_b, ch_a)).mean()

因此，给定一些点集（具有原始示例中的属性），如下所示：

A = np.random.randn(100, 2)
B = np.array([2,0]) + 0.5 * np.random.randn(100, 2)
C = 0.5 * np.random.randn(100, 2)
D = np.array([5,0]) + 0.5 * np.random.randn(100, 2)

在此处输入图像描述

包含程度可以计算如下：

>>> inclusion(A, B)
0.44

>>> inclusion(A, C)
1.0

>>> inclusion(A, D)
0.0

然而，最后值得注意的是，该points_in_poly函数并不总是将多边形边界上的点表示为在内部（请参阅此处了解为什么底层函数会以这种方式运行）。由于这个原因，您原始示例中的集合 C 将仅被部分包含，因为点 (1,5) 位于 A 的凸包上并且不被计算在内。

于 2012-07-25T08:44:08.693 回答
2

Matplotlib 有一个非常快的 point_in_poly 函数。这直接取自 matplotlib 文档：nxutils

在 [25] 中：将 numpy 导入为 np
在 [26] 中：将 matplotlib.nxutils 导入为 nx
在 [27] 中：verts = np.array([ [0,0], [0, 1], [1, 1], [1,0]], float)
在 [28] 中：nx.pnpoly(0.5, 0.5, verts)
出[28]：1
在 [29] 中：nx.pnpoly(0.5, 1.5, verts)
输出[29]：0
在 [30] 中：点 = np.random.rand(10,2)*2
在[31]中：点
输出[31]：
数组([[ 1.03597426, 0.61029911],
       [1.94061056, 0.65233947],
       [1.08593748, 1.16010789],
       [0.9255139，1.79098751]，
       [1.54564936, 1.15604046],
       [1.71514397, 1.26147554],
       [1.19133536, 0.56787764],
       [0.40939549，0.35190339]，
       [1.8944715，0.61785408]，
       [0.03128518, 0.48144145]])
在 [32] 中：nx.points_inside_poly(points, verts)
Out[32]: array([False, False, False, False, False, False, False, True, False, True], dtype=bool)

之后，只需测试集合中的每个点并确定两个、一个或都不在顶点内。

于 2012-07-24T13:46:08.293 回答