2D多边形的交集

Question

2D多边形的交集

6

我有两个numpy数组，它们是OpenCV的凸包(convex hulls)，我想检查它们是否相交，而不需要创建循环或创建图像并在上面执行numpy.bitwise_and，这两种方法在Python中非常慢。这些数组看起来像这样：

[[[x1 y1]]
 [[x2 y2]]
 [[x3 y3]]
...
 [[xn yn]]]

假设[[x1 y1]]为一个单独的元素，我想在两个numpy ndarrays之间执行交集。我该怎么做？我找到了一些类似的问题，但是我无法从中找到解决方案。

- Subhamoy S.

4个回答

4

您可以使用http://pypi.python.org/pypi/Polygon/2.0.4，这里有一个示例：

>>> import Polygon
>>> a = Polygon.Polygon([(0,0),(1,0),(0,1)])
>>> b = Polygon.Polygon([(0.3,0.3), (0.3, 0.6), (0.6, 0.3)])
>>> a & b
Polygon:
  <0:Contour: [0:0.60, 0.30] [1:0.30, 0.30] [2:0.30, 0.60]>

将cv2.findContours的结果转换为多边形点格式，可以采取以下方法：

points1 = contours[0].reshape(-1,2)

这将把形状从(N, 1, 2)转换为(N, 2)

以下是完整的示例:

import Polygon
import cv2
import numpy as np
from scipy.misc import bytescale

y, x = np.ogrid[-2:2:100j, -2:2:100j]

f1 = bytescale(np.exp(-x**2 - y**2), low=0, high=255)
f2 = bytescale(np.exp(-(x+1)**2 - y**2), low=0, high=255)


c1, hierarchy = cv2.findContours((f1>120).astype(np.uint8), 
                                       cv2.cv.CV_RETR_EXTERNAL, 
                                       cv2.CHAIN_APPROX_SIMPLE)

c2, hierarchy = cv2.findContours((f2>120).astype(np.uint8), 
                                       cv2.cv.CV_RETR_EXTERNAL, 
                                       cv2.CHAIN_APPROX_SIMPLE)


points1 = c1[0].reshape(-1,2) # convert shape (n, 1, 2) to (n, 2)
points2 = c2[0].reshape(-1,2)

import pylab as pl
poly1 = pl.Polygon(points1, color="blue", alpha=0.5)
poly2 = pl.Polygon(points2, color="red", alpha=0.5)
pl.figure(figsize=(8,3))
ax = pl.subplot(121)
ax.add_artist(poly1)
ax.add_artist(poly2)
pl.xlim(0, 100)
pl.ylim(0, 100)

a = Polygon.Polygon(points1)
b = Polygon.Polygon(points2)
intersect = a&b # calculate the intersect polygon

poly3 = pl.Polygon(intersect[0], color="green") # intersect[0] are the points of the polygon
ax = pl.subplot(122)
ax.add_artist(poly3)
pl.xlim(0, 100)
pl.ylim(0, 100)
pl.show()

输出:

在此输入图片描述

- HYRY

这个方法真的很快吗？由于我需要在每一帧捕捉时不断检查交叉，而系统资源并不是很高。 - Subhamoy S.

当我尝试从OpenCV轮廓或凸包创建多边形时，会出现以下错误：cPolygon.Error: Invalid polygon or contour for operation您指定的格式不是我原始帖子中所示的格式。我认为可能需要进行一些修改，但无法想象如何完成。 - Subhamoy S.

请提供一些样本数据。 - HYRY

这是我制作轮廓的方法：contours，hierarchy = cv2.findContours(sourceimage, cv2.cv.CV_RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)。之后，当我执行 for contour in contours: print contour.dtype, contour.shape, contour 时，我会得到以下结果：`int32 (84, 1, 2) [[[23 1]] [[23 4]] [[22 5]] [[23 5]]...... [[28 5]] [[24 1]]]。如果我使用 cv2.convexHull()而不是cv2.findContours()`，结果将是相同的。 - Subhamoy S.

如上所述（https://dev59.com/NGDVa4cB1Zd3GeqPc2Xl#9271260），如果我可以将视图更改为简单的元组列表，则Polygon.Polygon()将接受它，但是我似乎无法做到这一点:( - Subhamoy S.

你可以将contour.reshape(-1, 2)传递给Polygon.Polygon()。我已经更新了答案，并提供了一个完整的示例。 - HYRY

1

所以这就是我完成工作的方法：

import Polygon, numpy

# Here I extracted and combined some contours and created a convex hull from it.
# Now I wanna check whether a contour acquired differently intersects with this hull or not.

for contour in contours:  # The result of cv2.findContours is a list of contours
    contour1 = contour.flatten()
    contour1 = numpy.reshape(contour1, (int(contour1.shape[0]/2),-1))
    poly1 = Polygon.Polygon(contour1)

    hull = hull.flatten()  # This is the hull is previously constructued
    hull = numpy.reshape(hull, (int(hull.shape[0]/2),-1))
    poly2 = Polygon.Polygon(hull)

    if (poly1 & poly2).area()<= some_max_val:
        some_operations

我不得不使用for循环，这看起来有点繁琐，尽管它给了我期望的结果。如果有更好的方法，将不胜感激！

- Subhamoy S.

-1

受jiterrace答案的启发

我在使用Udacity深度学习课程时遇到了这篇文章（试图找到训练和测试数据之间的重叠部分）。

我不熟悉“视图”，并且发现语法有点难以理解，可能与我试图向以“表格”思考的朋友沟通时一样。我的方法基本上是将形状为（N，X，Y）的ndarray展平/重塑为形状为（N，X*Y，1）的数组。

print(train_dataset.shape)
print(test_dataset.shape)
#(200000L, 28L, 28L)
#(10000L, 28L, 28L)

1). INNER JOIN（更易理解，但速度较慢）

import pandas as pd

%%timeit -n 1 -r 1
def multidim_intersect_df(arr1, arr2):
    p1 = pd.DataFrame([r.flatten() for r in arr1]).drop_duplicates()
    p2 = pd.DataFrame([r.flatten() for r in arr2]).drop_duplicates()
    res = p1.merge(p2)
    return res
inters_df = multidim_intersect_df(train_dataset, test_dataset)
print(inters_df.shape)
#(1153, 784)
#1 loop, best of 1: 2min 56s per loop

2). SET INTERSECTION（快速）

%%timeit -n 1 -r 1
def multidim_intersect(arr1, arr2):
    arr1_new = arr1.reshape((-1, arr1.shape[1]*arr1.shape[2])) # -1 means row counts are inferred from other dimensions
    arr2_new = arr2.reshape((-1, arr2.shape[1]*arr2.shape[2]))
    intersected = set(map(tuple, arr1_new)).intersection(set(map(tuple, arr2_new)))  # list is not hashable, go tuple
    return list(intersected)  # in shape of (N, 28*28)

inters = multidim_intersect(train_dataset, test_dataset)
print(len(inters))
# 1153
#1 loop, best of 1: 34.6 s per loop

- B.Mr.W.

这是测试_points_是否共有的内容。这是关于由多边形/轮廓描述的整个形状的交集。 - Christoph Rackwitz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jterrace · Accepted Answer

您可以像这样将数组的视图作为单个维度传递给intersect1d函数：

您可以使用数组的视图作为单个维度传递给intersect1d函数，就像这样：

def multidim_intersect(arr1, arr2):
    arr1_view = arr1.view([('',arr1.dtype)]*arr1.shape[1])
    arr2_view = arr2.view([('',arr2.dtype)]*arr2.shape[1])
    intersected = numpy.intersect1d(arr1_view, arr2_view)
    return intersected.view(arr1.dtype).reshape(-1, arr1.shape[1])

这将创建每个数组的视图，将每行更改为一个值的元组。然后执行交集操作，并将结果更改回原始格式。以下是使用它的示例：

test_arr1 = numpy.array([[0, 2],
                         [1, 3],
                         [4, 5],
                         [0, 2]])

test_arr2 = numpy.array([[1, 2],
                         [0, 2],
                         [3, 1],
                         [1, 3]])

print multidim_intersect(test_arr1, test_arr2)

这会打印出：

[[0 2]
 [1 3]]