二维多边形的交集

Question

我有两个 numpy 数组，它们是 OpenCV 的凸包，我想检查它们是否相交，但不想使用循环或者生成图像后用 numpy.bitwise_and 来处理，因为这两种方法在 Python 中都比较慢。这两个数组看起来是这样的：

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

我想把 [[x1 y1]] 当作一个整体，想在这两个 numpy 数组之间检查相交。请问我该怎么做？我看到过一些类似的问题，但从中没找到解决办法。

Answer 1

你可以使用这个链接：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()

输出结果：

Answer 2

你可以把数组看成一维的形式，然后用这个形式去调用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]]

Answer 3

所以我做了以下这些事情来完成这个任务：

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循环，虽然这样做看起来有点繁琐，但结果是我想要的。如果有更好的方法，我会非常感激！