TLDR:我需要构建一个用于快速内点测试的 python 对象,类似于 SciPyConvexHull
或DelaunayTriangulation
. 问题是我提前知道必须构造点的三角剖分的顺序:(6 个点,8 个三角形面,每个面都有特定的顺序)。实际上,我已经知道凸包应该是什么,但我需要一种可以与现有(和优化!)库(例如 Scipy spatial)一起使用的形式。我怎样才能做到这一点?
背景: 我需要构建一个三角棱镜(想象一个 Toblerone 条 - 2 个端面,6 个侧面,全部为三角形)以进行一些内点测试。由于我将有许多这样的棱镜彼此相邻放置(在它们的侧面相邻,想象许多 Toblerone 条竖立在它们的末端并且彼此相邻),我需要小心确保空间中没有区域被两个包含相邻的棱镜。棱镜的横截面通常不均匀,因此相邻棱镜之间可能重叠,如下图所示两个相邻棱镜之间的近似平面:
____
|\ /|
| \/ |
| /\ |
|/__\|
注意沿着面部构造的两条不同的对角线——这就是问题所在。一个棱镜可能会使用 \ 对角线将面分成两个三角形,而相邻的棱镜可能会使用 /。为了确保相邻棱镜之间没有重叠,我需要明确控制三角形的形成顺序,以便它们始终使用相同的对角线。我可以做到这一点:对于我需要构建的每个棱镜,我提前知道应该以什么顺序构建三角形面。这是两个相邻棱镜的图示,它们之间有正确的共享对角线:相邻棱镜,共享对角线
我的问题是使用这些棱镜进行快速内点测试。以前,我使用的是这个答案中链接的方法:Delaunay(prism_points).find_simplex(test_points) >= 0
。它很快,因为它使用了高度优化的库代码,但我无法控制三角剖分的构造,所以可能会有重叠。
如果我将外壳构造为显式np.array
对象(顶点、面),那么我可以使用自己的代码进行测试(有许多可能的方法,我正在投射光线并测试与每个三角形面的交点)。find_simplex()
问题是这比前面提到的方法慢了大约 100 倍。虽然我确信我可以更快地获得代码,但值得指出的是,这段代码已经从 Cython 的另一个用例中得到了相当优化 - 我不确定我是否能在这里找到我需要的所有额外速度。至于不可避免的“你真的需要速度问题”,请相信我的话。这将 5 分钟的工作变成了数小时。
我需要的是构建一个可以与外部优化库一起使用的对象,同时保留对三角形面的控制。在我的代码中添加额外的 Cython 当然是一种选择,但是已经存在这样高度优化的代码,使用它会非常可取。
感谢任何可以提供帮助的人。