构造具有已知三角形面的凸包对象
Constructing convex hull object with known triangular faces
TLDR:我需要构造一个 python 对象来进行快速内点测试,类似于 SciPy ConvexHull
或 DelaunayTriangulation
。问题是我提前知道点 的三角剖分必须 的构建顺序:(6 个点,8 个三角形面,每个面都有特定的顺序)。实际上,我已经知道凸包应该是什么,但我需要它的形式可以与现有(和优化!)库(例如 Scipy 空间)一起使用。我该怎么做?
上下文:
我需要构建一个三棱柱(想象一个 Toblerone 杆 - 2 个端面、6 个侧面,均为三角形)以便进行一些内点测试。因为我会有许多这样的棱镜彼此相邻(在它们的侧面相邻,想象许多 Toblerone 条竖立在它们的末端并彼此相邻),我需要小心确保 space 中没有区域包含在两个相邻的棱镜中。棱镜的横截面通常不会是均匀的,因此相邻棱镜之间可能会重叠,如两个相邻棱镜之间的近似平面图所示:
____
|\ /|
| \/ |
| /\ |
|/__\|
注意沿面构造的两条不同的对角线 - 这就是问题所在。一个棱镜可以使用 \ 对角线将面分成两个三角形,而相邻的棱镜可以改为使用 /。为了确保相邻棱镜之间不重叠,我需要明确控制三角形的形成顺序,以便它们始终使用相同的对角线。我可以做到这一点:对于我需要构建的每个棱镜,我提前知道应该以什么顺序构建三角形面。这是两个相邻棱镜的图示,它们之间有正确的共享对角线:neighbouring prisms, shared diagonal
我的问题是使用这些棱镜执行快速内点测试。以前,我使用的是 answer 中链接的方法:Delaunay(prism_points).find_simplex(test_points) >= 0
。它很快,因为它使用高度优化的库代码,但我无法控制三角剖分的构造,因此可能会有重叠。
如果我将外壳构造为显式 np.array
对象(顶点、面),那么我可以使用自己的代码进行测试(有多种可能的方法,我正在投射光线并测试相交每个三角形面)。问题是这比前面提到的 find_simplex()
方法慢大约 100 倍。虽然我确信我可以更快地获得代码,但值得指出的是,这段代码已经从另一个使用 Cython 的用例中进行了相当优化——我不确定我是否可以在这里找到我需要的所有额外速度。至于不可避免的"do you really need the speed question",请相信我的话。这将 5 分钟的工作变成了许多小时。
我需要的是构建一个我可以与外部优化库一起使用的对象,同时保留对三角形面的控制。在我的代码中添加额外的 Cython 当然是一种选择,但是如果已经存在这样高度优化的代码,那么使用它会非常可取。
感谢任何可以提供帮助的人。
一半的解决方案...不是原始问题的精确解决方案,而是实现相同结果的不同方法。任何三棱柱都可以精确地分成三个四面体(参见 http://www.alecjacobson.com/weblog/?p=1888)。这是一个特殊情况,即任何多面体都可以通过将所有面连接到一个顶点来拆分为四面体,如果这些面还没有包含它的话。
确切地知道我希望棱镜的面三角形如何排列,我可以算出三个四面体将重现相同的三角形配置(当然在原始棱镜本身内部添加了额外的面)。然后,我依次围绕这三个四面体(即 4 个点的集合)中的每一个形成 Delaunay 三角剖分,并执行原始内点测试:如果它匹配任何一个,那么我对整个棱镜的结果都是肯定的。关键是,通过一次只给 Delaunay 构造函数四个点,我确切地知道它会 return 什么三角剖分,因为只有一种方法可以形成这样的四面体(假设没有几何退化)。
它有点冗长,涉及的测试数量是我想要的 3 倍,但这是一个开始。如果将来有人知道我怎样才能做得更好,请告诉我。
TLDR:我需要构造一个 python 对象来进行快速内点测试,类似于 SciPy ConvexHull
或 DelaunayTriangulation
。问题是我提前知道点 的三角剖分必须 的构建顺序:(6 个点,8 个三角形面,每个面都有特定的顺序)。实际上,我已经知道凸包应该是什么,但我需要它的形式可以与现有(和优化!)库(例如 Scipy 空间)一起使用。我该怎么做?
上下文: 我需要构建一个三棱柱(想象一个 Toblerone 杆 - 2 个端面、6 个侧面,均为三角形)以便进行一些内点测试。因为我会有许多这样的棱镜彼此相邻(在它们的侧面相邻,想象许多 Toblerone 条竖立在它们的末端并彼此相邻),我需要小心确保 space 中没有区域包含在两个相邻的棱镜中。棱镜的横截面通常不会是均匀的,因此相邻棱镜之间可能会重叠,如两个相邻棱镜之间的近似平面图所示:
____
|\ /|
| \/ |
| /\ |
|/__\|
注意沿面构造的两条不同的对角线 - 这就是问题所在。一个棱镜可以使用 \ 对角线将面分成两个三角形,而相邻的棱镜可以改为使用 /。为了确保相邻棱镜之间不重叠,我需要明确控制三角形的形成顺序,以便它们始终使用相同的对角线。我可以做到这一点:对于我需要构建的每个棱镜,我提前知道应该以什么顺序构建三角形面。这是两个相邻棱镜的图示,它们之间有正确的共享对角线:neighbouring prisms, shared diagonal
我的问题是使用这些棱镜执行快速内点测试。以前,我使用的是 answer 中链接的方法:Delaunay(prism_points).find_simplex(test_points) >= 0
。它很快,因为它使用高度优化的库代码,但我无法控制三角剖分的构造,因此可能会有重叠。
如果我将外壳构造为显式 np.array
对象(顶点、面),那么我可以使用自己的代码进行测试(有多种可能的方法,我正在投射光线并测试相交每个三角形面)。问题是这比前面提到的 find_simplex()
方法慢大约 100 倍。虽然我确信我可以更快地获得代码,但值得指出的是,这段代码已经从另一个使用 Cython 的用例中进行了相当优化——我不确定我是否可以在这里找到我需要的所有额外速度。至于不可避免的"do you really need the speed question",请相信我的话。这将 5 分钟的工作变成了许多小时。
我需要的是构建一个我可以与外部优化库一起使用的对象,同时保留对三角形面的控制。在我的代码中添加额外的 Cython 当然是一种选择,但是如果已经存在这样高度优化的代码,那么使用它会非常可取。
感谢任何可以提供帮助的人。
一半的解决方案...不是原始问题的精确解决方案,而是实现相同结果的不同方法。任何三棱柱都可以精确地分成三个四面体(参见 http://www.alecjacobson.com/weblog/?p=1888)。这是一个特殊情况,即任何多面体都可以通过将所有面连接到一个顶点来拆分为四面体,如果这些面还没有包含它的话。
确切地知道我希望棱镜的面三角形如何排列,我可以算出三个四面体将重现相同的三角形配置(当然在原始棱镜本身内部添加了额外的面)。然后,我依次围绕这三个四面体(即 4 个点的集合)中的每一个形成 Delaunay 三角剖分,并执行原始内点测试:如果它匹配任何一个,那么我对整个棱镜的结果都是肯定的。关键是,通过一次只给 Delaunay 构造函数四个点,我确切地知道它会 return 什么三角剖分,因为只有一种方法可以形成这样的四面体(假设没有几何退化)。
它有点冗长,涉及的测试数量是我想要的 3 倍,但这是一个开始。如果将来有人知道我怎样才能做得更好,请告诉我。