使用numpy/scipy将3D点投影到3D三角形的最近点

如何使用numpy/scipy计算一个点到N个三角形的最近投影？
现在，我将创建一个函数来计算到单个三角形basically this的投影，然后遍历整个三角形数组。但在开始之前，我想知道scipy中是否已经有了一个解决方案。类似于：


# DREAMY PSEUDOCODE

import numpy as np
N_TRIANGLES = 1000

point = np.random.rand(3) * 100 #random 3d point
triangles = np.random.rand(N_TRIANGLES,3,3) * 100 #array of triangles

from scipy.spatial import pointToTriangles
projections = pointToTriangles(point,triangles)

这里有一张图片可以帮助你想象：

在上图中，中间的红点是我的查询“point”，蓝点是在“triangles”np.array（）中定义的每个三角形的顶点。绿色表示我想要的结果。它们是“point”到定义的三角形的最接近的投影，我希望以点的数组的形式得到这些信息。
干杯！

这是我的代码。我在scipy中找不到任何可以直接帮助我的东西，这个解决方案比查询CGAL快大约2倍。它不处理折叠的三角形，但可以通过检查边长并返回最长边上最近的点来修复。

import numpy as np

def pointsToTriangles(points,triangles):

    with np.errstate(all='ignore'):

        # Unpack triangle points
        p0,p1,p2 = np.asarray(triangles).swapaxes(0,1)

        # Calculate triangle edges
        e0 = p1-p0
        e1 = p2-p0
        a = np.einsum('...i,...i', e0, e0)
        b = np.einsum('...i,...i', e0, e1)
        c = np.einsum('...i,...i', e1, e1)

        # Calculate determinant and denominator
        det = a*c - b*b
        invDet = 1. / det
        denom = a-2*b+c

        # Project to the edges
        p  = p0-points[:,np.newaxis]
        d = np.einsum('...i,...i', e0, p)
        e = np.einsum('...i,...i', e1, p)
        u = b*e - c*d
        v = b*d - a*e

        # Calculate numerators
        bd = b+d
        ce = c+e
        numer0 = (ce - bd) / denom
        numer1 = (c+e-b-d) / denom
        da = -d/a
        ec = -e/c

        # Vectorize test conditions
        m0 = u + v < det
        m1 = u < 0
        m2 = v < 0
        m3 = d < 0
        m4 = (a+d > b+e)
        m5 = ce > bd

        t0 =  m0 &  m1 &  m2 &  m3
        t1 =  m0 &  m1 &  m2 & ~m3
        t2 =  m0 &  m1 & ~m2
        t3 =  m0 & ~m1 &  m2
        t4 =  m0 & ~m1 & ~m2
        t5 = ~m0 &  m1 &  m5
        t6 = ~m0 &  m1 & ~m5
        t7 = ~m0 &  m2 &  m4
        t8 = ~m0 &  m2 & ~m4
        t9 = ~m0 & ~m1 & ~m2

        u = np.where(t0, np.clip(da, 0, 1), u)
        v = np.where(t0, 0, v)
        u = np.where(t1, 0, u)
        v = np.where(t1, 0, v)
        u = np.where(t2, 0, u)
        v = np.where(t2, np.clip(ec, 0, 1), v)
        u = np.where(t3, np.clip(da, 0, 1), u)
        v = np.where(t3, 0, v)
        u *= np.where(t4, invDet, 1)
        v *= np.where(t4, invDet, 1)
        u = np.where(t5, np.clip(numer0, 0, 1), u)
        v = np.where(t5, 1 - u, v)
        u = np.where(t6, 0, u)
        v = np.where(t6, 1, v)
        u = np.where(t7, np.clip(numer1, 0, 1), u)
        v = np.where(t7, 1-u, v)
        u = np.where(t8, 1, u)
        v = np.where(t8, 0, v)
        u = np.where(t9, np.clip(numer1, 0, 1), u)
        v = np.where(t9, 1-u, v)

        # Return closest points
        return (p0.T +  u[:, np.newaxis] * e0.T + v[:, np.newaxis] * e1.T).swapaxes(2,1)

将100个点投影到10k个三角形的一些测试数据：

import numpy as np
    import cProfile

    N_TRIANGLES = 10**4 # 10k triangles
    N_POINTS    = 10**2 # 100 points
    points      = np.random.random((N_POINTS,3,)) * 100
    triangles   = np.random.random((N_TRIANGLES,3,3,)) * 100

    cProfile.run("pointsToTriangles(points,triangles)") # 54 function calls in 0.320 seconds

这很快就会占用大量内存，所以在处理大数据集时，最好一次迭代一个点或三角形。

使用numpy/scipy将3D点投影到3D三角形的最近点

1条答案

相关问题

热门标签

最新问答