二维多边形的交集

发布于 2025-01-05 15:51:24 字数 275 浏览 0 评论 0原文

我有两个 OpenCV 凸包 numpy 数组,我想检查交集,而不创建 for 循环或创建图像并对它们执行 numpy.bitwise_and ,这两个数组都是Python 中相当慢。数组看起来像这样:

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

将 [[x1 y1]] 视为一个元素,我想在两个 numpy ndarray 之间执行交集。我怎样才能做到这一点?我发现了一些类似性质的问题,但我无法从那里找到解决方案。

I have two numpy arrays that are OpenCV convex hulls and I want to check for intersection without creating for loops or creating images and performing numpy.bitwise_and on them, both of which are quite slow in Python. The arrays look like this:

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

Considering [[x1 y1]] as one single element, I want to perform intersection between two numpy ndarrays. How can I do that? I have found a few questions of similar nature, but I could not figure out the solution to this from there.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

羁拥 2025-01-12 15:51:24

您可以将数组的视图用作 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]]

You can use a view of the array as a single dimension to the intersect1d function like this:

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])

This creates a view of each array, changing each row to a tuple of values. It then performs the intersection, and changes the result back to the original format. Here's an example of using it:

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)

This prints:

[[0 2]
 [1 3]]
煮酒 2025-01-12 15:51:24

您可以使用 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()

输出:

在此处输入图像描述

you can use http://pypi.python.org/pypi/Polygon/2.0.4, here is an example:

>>> 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]>

To convert the result of cv2.findContours to Polygon point format, you can:

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

This will convert the shape from (N, 1, 2) to (N, 2)

Following is a full example:

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()

Output:

enter image description here

走走停停 2025-01-12 15:51:24

这就是我为完成工作所做的:

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 循环,这看起来有点乏味,尽管它给了我预期的结果。任何更好的方法将不胜感激!

So this is what I did to get the job done:

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

I had to use for loop, and this altogether looks a bit tedious, although it gives me expected results. Any better methods would be greatly appreciated!

勿忘初心 2025-01-12 15:51:24

受到 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)。设置交点(快速)

%%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

inspired by jiterrace's answer

I came across this post while working with Udacity deep learning class(trying to find the overlap between training and test data).

I am not familiar with "view" and found the syntax a bit hard to understand, probably the same when I try to communicate to my friends who think in "table".
My approach is basically to flatten/reshape the ndarray of shape (N, X, Y) into shape (N, X*Y, 1).

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

1). INNER JOIN (easier to understand, slow)

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 (fast)

%%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
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文