如何在 Python 中检测空间路径中的自交集?

Question

假设我在多维空间中有一条路径，由路径上的点数组给出。

例如

p[0] = [  0,  0,  0,   0,...]
p[1] = [  0,  0,  0,0.01,...]

等。

检测路径是否有任何自相交的有效算法是什么？ 路径完全有可能在我存储的点之间的点相交。

例如，在 2D 中：

p[0] = [  0,   0]
p[1] = [  1,   0]
p[2] = [  1,   1]
p[3] = [0.5,-0.5]

这条路径没有任何相同的点，但有一个 自交点 .

编辑：

我目前正在测试是否有任何点落在每对点创建的圆柱内。

这是我一直在玩的代码：

import numpy as np
def pairs(l):
for i in range(0,len(l),2):
yield (i,l[i:i+2])
def in_cyl(h0,h1,tol,p):
# efficient cylinder test from https://www.flipcode.com/archives/Fast_Point-In-Cylinder_Test.shtml
l = np.linalg.norm(h0-h1)
dx = h1-h0
for point in p:
pdx = point-h0
dot = np.dot(pdx,dx)
if dot < 0 or dot > l**2:
# outside end caps
continue
else:
# point lies within end caps. Find dist from point to cyl axis
dsq = np.dot(pdx,pdx) - dot**2/l**2
if (dsq > tol**2):
# outside cyl
continue
else:
# inside cyl
return True
return False
def self_intersect(p,tol):
for i,(h0,h1) in pairs(p):
if in_cyl(h0,h1,tol,np.vstack([p[:i],p[i+2:]])):
return True
return False
# 50-dimensional test. Intersections should be very rare
dim = 50
test_points = np.random.randn(2500,(50))
print(self_intersect(test_points,0.1))

在我的机器上，这相当慢。

%timeit self_intersect(np.random.randn(2000,(10)),0.1)
10 s ± 94.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 1

自交搜索可以通过复杂度为 O(log(n(( + O(n*log(n(( 的 BVH 遍历来实现，以构建树(通常 BVH 构建一次并多次用于不同的目的(。

对于这种情况，遍历非常简单，让我展示二进制 BVH 的示例：

1. 首先，我们定义任务 - BVH的两个相交节点
2. 从任务开始(根节点、根节点(
3. 如果task.nodeA=task.nodeB：
   • 添加Task(task.nodeA.left,task.nodeA.left)
   • 添加Task(task.nodeA.right,task.nodeA.right)
   • 添加Task(task.nodeA.left,task.nodeA.right)
4. 否则，如果task.nodeAtask.nodeB相交：
   • 如果task.nodeA和task.nodeB是叶子 - 检查交集(小心共享点的线，它们不应该被计算在内(
   • 否则拆分体积较小的节点(如果不是叶节点，则拆分另一个节点(并添加Task(task.smallNode,task.splitedNode.left)和Task(task.smallNode,task.splitedNode.right)

你可以在开源库 MeshLib 中找到 2d 折线的 c++ 实现(它内部使用 AABB 树 BVH 结构(。它还具有python模块，您可以在其中运行以下代码：

from meshlib import mrmeshpy
from meshlib import mrmeshnumpy
import numpy as np
# mrmeshpy uses float32 for vertex coordinates
# however, you could also use float64
points = np.ndarray(shape=(4,2), dtype=np.float32, buffer=np.array([[0.0,0.0],[1.0,0.0],[1.0,1.0],[0.5,-0.5]], dtype=np.float32))
# create polyline structure from numpy points array
polyline = mrmeshnumpy.polyline2FromPoints(points)
# find indices of self-intersecting polyline edges
selfInters = mrmeshpy.findSelfCollidingEdges(polyline)
assert (selfInters.size() == 1)
# get line segments of that edges
segm1 = polyline.edgeSegment(mrmeshpy.EdgeId(selfInters[0].aUndirEdge))
segm2 = polyline.edgeSegment(mrmeshpy.EdgeId(selfInters[0].bUndirEdge))
# find coordinates of intersection
inter = mrmeshpy.intersection(segm1,segm2) # inter == [0.666667,0.0]
assert (abs(inter.x - 2.0/3.0) < 0.001 and inter.y == 0)