计算几何,四面体符号体积
我不确定这是否是正确的地方,但是这里......
简短版本:我正在尝试计算平面上三角形的方向,由三条边的交点形成,而不显式计算交点.
长版:我需要在3D三角形上对三角形上的PSLG进行三角测量.PSLG的顶点由线段与穿过三角形的平面的交点定义,并保证位于三角形内.假设我有交点,我可以投影到2D并使用点线侧(或三角形有符号区域)测试来确定任意3个交叉点之间的三角形的方向.
问题是我无法明确计算交点,因为当我找到线平面交点时会累积浮点误差.为了弄清楚线段是否在第一个位置撞击三角形,我使用了一些可自由使用的强大几何谓词,它给出了四面体体积的符号,或等效于点位于平面的哪一侧.我可以确定线段端点是否在通过三角形的平面的相对侧,然后在线段和三角形的每个边之间形成四面体以确定交叉点是否位于三角形内.
由于我无法明确计算交叉点,我想知道是否有一种方法可以仅使用原始点在3D中表达相同的2D方向计算.如果有三条边撞击三角形,总共给我9分.假设我所要求的甚至是可能的(仅使用3D方向测试),那么我猜我需要在这9个点之间形成所有可能的四面体的一些子集.我甚至难以想象这一点,更不用说将其提炼成公式或代码了.我甚至不能谷歌,因为我不知道这类问题的行业标准术语是什么.
任何想法如何处理这个？谢谢.也许我应该问MathOverflow ......
编辑:在阅读了一些评论之后,我发生了一件事......也许如果我能在3个线段之间拟合非重叠的四面体,那么任何一个穿越平面的方向都将是答案我我正在寻找.除了边缘包围一个简单的三角形棱镜,我不确定这个子问题是否也可以解决.
编辑:请求的图像.
我在MO&SO上回答这个问题,扩大了我对MO的评论.
我的感觉是,没有带有签名四面体体积的计算技巧可以避免主要关注的精度问题.这是因为,如果您有紧密扭曲的线段,三角形的方向取决于切割平面的精确定位.
[图片已删除; 见上图]
在上面的例子中,上平面按顺序(a,b,c)[从上面的ccw] :( 红色,蓝色,绿色)穿过片段,而下平面以相反的顺序交叉(c, b,a):( 绿色,蓝色,红色).切割平面的高度可以由您的最后一点精度确定.
因此,我认为继续计算切割平面中的交点是有意义的,使用足够的精度来使计算精确.如果您的段端点坐标和平面系数具有L位精度,那么只需要一个小的常数因子增加.虽然我不确定究竟是什么因素,但它很小 - 可能是4.你不需要例如L 2位,因为计算是求解线性方程.因此,精确计算所需的精度不会出现爆炸性增长.
祝好运!
(由于我没有声誉,我被禁止发布澄清图像.请参阅MO答案.)
编辑:看到MO答案,但这里是图像:
