如果寻找点在python中3D聚(Finding if point is in 3D poly in

我试图找出一个点是否在一个三维聚。 我用了另一个脚本，我在网上找到占用大量的使用光线投射的2D问题的关心。 我想知道这到底是怎么被改变为3D多边形工作。 我不打算在看有很多凹坑或孔或什么的，真是奇怪的多边形。 这里是蟒蛇的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:

感谢所有那些评论。 为寻找这个答案，我发现一个，对于某些情况下（但不复杂的案件）的作品。

我在做什么用scipy.spatial.ConvexHull像shongololo建议是，但有轻微的扭曲。 我想提出点云的三维凸包，然后将我检查到一个“新”点云中的点，使新的3D凸包。 如果它们是相同的，然后我假设它必须是凸包内。 我还是感激，如果有人有这样做的更强大的方式，因为我认为这是一个有点hackish。 该代码将类似于如下：

from scipy.spatial import ConvexHull

def pnt_in_pointcloud(points, new_pt):
    hull = ConvexHull(points)
    new_pts = points + new_pt
    new_hull = ConvexHull(new_pts)
    if hull == new_hull: 
        return True
    else:
        return False

希望这可以帮助别人的未来寻找一个答案！ 谢谢！

Answer 2:

我检查了QHull版本（从上面），并且线性规划溶液（例如，参见这个问题 ）。 到目前为止，使用QHull似乎是最好的选择，虽然我可能会丢失一些优化与scipy.spatial LP。

import numpy
import numpy.random
from numpy import zeros, ones, arange, asarray, concatenate
from scipy.optimize import linprog

from scipy.spatial import ConvexHull

def pnt_in_cvex_hull_1(hull, pnt):
    '''
    Checks if `pnt` is inside the convex hull.
    `hull` -- a QHull ConvexHull object
    `pnt` -- point array of shape (3,)
    '''
    new_hull = ConvexHull(concatenate((hull.points, [pnt])))
    if numpy.array_equal(new_hull.vertices, hull.vertices): 
        return True
    return False


def pnt_in_cvex_hull_2(hull_points, pnt):
    '''
    Given a set of points that defines a convex hull, uses simplex LP to determine
    whether point lies within hull.
    `hull_points` -- (N, 3) array of points defining the hull
    `pnt` -- point array of shape (3,)
    '''
    N = hull_points.shape[0]
    c = ones(N)
    A_eq = concatenate((hull_points, ones((N,1))), 1).T   # rows are x, y, z, 1
    b_eq = concatenate((pnt, (1,)))
    result = linprog(c, A_eq=A_eq, b_eq=b_eq)
    if result.success and c.dot(result.x) == 1.:
        return True
    return False


points = numpy.random.rand(8, 3)
hull = ConvexHull(points, incremental=True)
hull_points = hull.points[hull.vertices, :]
new_points = 1. * numpy.random.rand(1000, 3)

哪里

%%time
in_hull_1 = asarray([pnt_in_cvex_hull_1(hull, pnt) for pnt in new_points], dtype=bool)

生产：

CPU times: user 268 ms, sys: 4 ms, total: 272 ms
Wall time: 268 ms

和

%%time
in_hull_2 = asarray([pnt_in_cvex_hull_2(hull_points, pnt) for pnt in new_points], dtype=bool)

产生

CPU times: user 3.83 s, sys: 16 ms, total: 3.85 s
Wall time: 3.85 s

文章来源: Finding if point is in 3D poly in python