python - 在python中查找点是否在3D多边形中

Question

我试图找出一个点是否在 3D 多边形中。我使用了在网上找到的另一个脚本来解决许多使用光线转换的 2D 问题。我想知道如何改变它以适用于 3D 多边形。我不会看到带有很多凹面或孔或任何东西的非常奇怪的多边形。这是 python 中的 2D 实现:

def point_inside_polygon(x,y,poly):

    n = len(poly)
    inside =False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x,p1y = p2x,p2y

    return inside

任何帮助将不胜感激!谢谢。

Answer 1

提出了类似的问题here ，但重点关注效率。

@Brian 在此建议的 scipy.spatial.ConvexHull 方法和 @fatalaccidents可以，但是如果您需要检查多个点，则 get 会非常慢。

嗯，most efficient solution ，也来自 scipy.spatial，但使用了 Delaunay 曲面分割:

from scipy.spatial import Delaunay

Delaunay(poly).find_simplex(point) >= 0  # True if point lies within poly

这是可行的，因为如果该点不在任何单纯形中(即在三角剖分之外)，则 .find_simplex(point) 返回 -1 。 (注意:它适用于 N 维，而不仅仅是 2/3D。)

<小时/>

性能比较

首先一分:

import numpy
from scipy.spatial import ConvexHull, Delaunay

def in_poly_hull_single(poly, point):
    hull = ConvexHull(poly)
    new_hull = ConvexHull(np.concatenate((poly, [point])))
    return np.array_equal(new_hull.vertices, hull.vertices)

poly = np.random.rand(65, 3)
point = np.random.rand(3)

%timeit in_poly_hull_single(poly, point)
%timeit Delaunay(poly).find_simplex(point) >= 0

结果:

2.63 ms ± 280 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1.49 ms ± 153 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

所以 Delaunay 方法更快。但这取决于多边形的大小!我发现，对于由超过 65 个点组成的多边形，Delaunay 方法变得越来越慢，而 ConvexHull 方法的速度几乎保持不变。

对于多个点:

def in_poly_hull_multi(poly, points):
    hull = ConvexHull(poly)
    res = []
    for p in points:
        new_hull = ConvexHull(np.concatenate((poly, [p])))
        res.append(np.array_equal(new_hull.vertices, hull.vertices))
    return res

points = np.random.rand(10000, 3)

%timeit in_poly_hull_multi(poly, points)
%timeit Delaunay(poly).find_simplex(points) >= 0

结果:

155 ms ± 9.42 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
1.81 ms ± 106 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

因此，Delaunay 提供了极大的速度提升；更不用说要等多久才能达到10000点以上。在这种情况下，多边形大小不再有太大的影响。

<小时/>

综上所述，Delaunay不仅速度快很多，而且代码也非常简洁。