计算几何，四面体签名量 [英] Computational geometry, tetrahedron signed volume

问题描述

我不确定这是否是正确的地方要问，但是在这里......

短版： m试图计算一个平面上三角形的方向，由三条边相交形成，而不明确计算交点。

长版本：我需要在3D中对三角形上的PSLG进行三角测量。 PSLG的顶点由线段与通过三角形的平面的交点定义，并保证位于三角形内。假设我有交点，我可以投影到2D，并使用点线边（或三角符号区域）测试来确定任意3个交点之间的三角形方向。

问题是我无法明确地计算交点，因为当我找到线平面交点时会积累浮点错误。为了弄清楚线段是否碰到了三角形，我使用了一些免费提供的鲁棒几何谓词，它们给出了四面体体积的符号，或者等价于一个点位于平面的哪一侧。我可以确定线段端点是否位于通过三角形的平面的相对两侧，然后在线段与三角形的每条边之间形成四面体以确定交点是否位于三角形内。

因为我不能明确计算交点，所以我想知道是否有一种方法可以仅使用原始点在3D中表示相同的2D定向计算。如果有三个边缘击中三角形，总共给我9个点。假设我所要求的甚至是可能的（仅使用3D定向测试），那么我猜测我需要在这9个点之间形成所有可能的四面体的一些子集。我甚至很难想象这一点，更不用说把它提炼成一个公式或代码。我甚至无法谷歌这一点，因为我不知道这种类型的问题可能是什么行业标准术语。

任何想法如何继续？谢谢。也许我应该问MathOverflow以及...

编辑：在阅读了一些评论之后，发生在我身上的一件事情......也许如果我可以适合非常规的话，三条线段之间有重叠的四面体，那么任何一个穿过飞机的方向都是我正在寻找的答案。除了当边缘包围一个简单的三角棱镜时，我不确定这个子问题是否可以解决。

编辑：请求的图片。

解决方案

我正在回答MO& SO，扩大了我对MO的评论。

我的感觉是，没有签名四面体卷的计算技巧将避免您主要关注的精度问题。这是因为，如果您有严格扭曲的部分，三角形的方向取决于切割平面的精确定位。

[image removed;见下面]

在上面的例子中，上面的平面以（ a，b，c ）[从上面的ccw]顺序穿过段：（ red，蓝色，绿色），而较低的平面以相反的顺序（ c，b，a ）交叉：（ green，blue，red ）。切割平面的高度
可以由你的最后一位精度决定。

因此，我认为有必要继续计算点数在
切割平面的交点，使用足够的精度使计算精确。如果您的分段端点坐标和平面系数具有 L 位的精度，那么只需要一个小的恒定因子增量。虽然我不确定这个因素究竟是什么，但它很小 - 可能是4.您不需要比如位，因为计算是求解线性的方程。
所以计算精确度所需的精度不会出现爆炸。

祝您好运！

（我没有发布澄清图片，因为我没有声望。请参阅

编辑：请参阅MO回答，但这里是图片：

I'm not sure if this is the right place to ask, but here goes...

Short version: I'm trying to compute the orientation of a triangle on a plane, formed by the intersection of 3 edges, without explicitly computing the intersection points.

Long version: I need to triangulate a PSLG on a triangle in 3D. The vertices of the PSLG are defined by the intersections of line segments with the plane through the triangle, and are guaranteed to lie within the triangle. Assuming I had the intersection points, I could project to 2D and use a point-line-side (or triangle signed area) test to determine the orientation of a triangle between any 3 intersection points.

The problem is I can't explicitly compute the intersection points because of the floating-point error that accumulates when I find the line-plane intersection. To figure out if the line segments strike the triangle in the first place, I'm using some freely available robust geometric predicates, which give the sign of the volume of a tetrahedron, or equivalently which side of a plane a point lies on. I can determine if the line segment endpoints are on opposite sides of the plane through the triangle, then form tetrahedra between the line segment and each edge of the triangle to determine whether the intersection point lies within the triangle.

Since I can't explicitly compute the intersection points, I'm wondering if there is a way to express the same 2D orient calculation in 3D using only the original points. If there are 3 edges striking the triangle that gives me 9 points in total to play with. Assuming what I'm asking is even possible (using only the 3D orient tests), then I'm guessing that I'll need to form some subset of all the possible tetrahedra between those 9 points. I'm having difficultly even visualizing this, let alone distilling it into a formula or code. I can't even google this because I don't know what the industry standard terminology might be for this type of problem.

Any ideas how to proceed with this? Thanks. Perhaps I should ask MathOverflow as well...

EDIT: After reading some of the comments, one thing that occurs to me... Perhaps if I could fit non-overlapping tetrahedra between the 3 line segments, then the orientation of any one of those that crossed the plane would be the answer I'm looking for. Other than when the edges enclose a simple triangular prism, I'm not sure this sub-problem is solvable either.

EDIT: The requested image.

解决方案

I am answering this on both MO & SO, expanding the comments I made on MO.

My sense is that no computational trick with signed tetrahedra volumes will avoid the precision issues that are your main concern. This is because, if you have tightly twisted segments, the orientation of the triangle depends on the precise positioning of the cutting plane.
[image removed; see below]
In the above example, the upper plane crosses the segments in the order (a,b,c) [ccw from above]: (red,blue,green), while the lower plane crosses in the reverse order (c,b,a): (green,blue,red). The height of the cutting plane could be determined by your last bit of precision.

Consequently, I think it makes sense to just go ahead and compute the points of intersection in the cutting plane, using enough precision to make the computation exact. If your segment endpoints coordinates and plane coefficients have L bits of precision, then there is just a small constant-factor increase needed. Although I am not certain of precisely what that factor is, it is small--perhaps 4. You will not need e.g., L² bits, because the computation is solving linear equations. So there will not be an explosion in the precision required to compute this exactly.

Good luck!

(I was prevented from posting the clarifying image because I don't have the reputation. See the MO answer instead.)

Edit: Do see the MO answer, but here's the image:

这篇关于计算几何，四面体签名量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！