创建相邻三角形的algorithm

我有一个系统,你可以点击一次在节点中放置一个场景。 当放置3个节点时,它形成一个三角形。 放置任何未来节点时,通过将该节点连接到最近的2个节点,创建一个新的三角形。

这在大多数情况下都能正常工作,但是在靠近具有非常锐角的三角形附近使用时是有缺陷的,因为2个最近的节点中的一个通常不是应该使用的节点。

例如,请参阅下面的图像。 品红三角是第一个放置。 如果我再点击标记为X的位置,我所得到的是一个新的三角形,其中蓝色覆盖层是。 我想要的是一个新的三角形的绿色覆盖。 (即在这个例子中,与品红对称对称)澄清:绿色和品红三角不重叠 – 绿色三角在蓝色下延伸到最左边的节点)

实际和期望行为的例子

如何确定创建新三角形时要使用哪2个顶点,以避免三角形叠加?

编辑 :search最近的边缘给出更好的结果,但不是完美的。 考虑这种情况:

在这里输入图像描述

“最近边缘”testing是不明确的,可以返回AB或AC(因为两者的最近点都是A)。 期望的结果将是AC,以形成没有边缘重叠的ACX三角形。 我怎么能确保这个结果? (如果可能的话,我宁愿不必执行单独的边缘重叠testing,因为我担心最近的边缘testing不一定会发现2是完全等距的,给定浮点精度问题)。

find到边的最小距离 (即由节点定义的线段),而不是find到节点的最小距离 。

然后,如果最近点是一个顶点(你必须使用一些浮点数epsilon **testing),比较从新点到顶点的线与连接到顶点的每条边之间的角度。 select绝对角度最小的那个:

MinAngle(newPoint, vertex, edge1, edge2) { newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this edge1Unit = norm(edge1 - vertex); // you probably have these from your dist to line tests edge2Unit = norm(edge2 - vertex); edge1Dot = dot(edge1Unit, newEdgeUnit); edge2Dot = dot(edge2Unit, newEdgeUnit); // you can simply compare dot products to find the minimum absolute angle if (edge1Dot > edge2Dot) return edge1; // set up this way so you can generalize to an array return edge2; } 

**为避免添加可能会破坏epsilontesting的退化三角形,您可能需要在不允许添加点的每个顶点周围放置一个区域(类似于上面使用的某个倍数内的不允许的点)。

放置第一个三角形后,放置一个新的顶点时,将始终生成两个新的边。 新三角形的第三条边总是与上一个三角形共享的边。 如果你能find一种方法来确定共享边,你就知道要连接哪个顶点,但这是最难的部分。 我相信你可以通过从新的顶点到所产生的最后三个边的每一个的中心(或者可能是3个最近的边)的一条线来做到这一点。

在这里输入图像描述

如果从顶点到边缘中心的线条不能穿过其他两条边线中的任何一条,那么您就有了共享边缘。 共享边将告诉你哪个顶点连接到你的新顶点。

吉米提出了一个关于新三角形将如何走向这一点的含糊不清的观点:

暧昧的三角形

这将使您有机会select两个有效的三角形。 也许打破哪个中心点是最接近的领带。

考虑到你的更新,虽然更复杂,但我的解决scheme只会在有两个有效的三角形时产生联系。 使用这种方法你的第二个例子图像会产生你想要的结果。

在这里输入图像描述

有了你的品红三角形ABC,你就可以合并一个新的顶点X.我认为很显然,在D中有两条线不会在三角形ABC的任何边之间相交。

这两条线可以是AX&BX,BX&CX或AX&CX。 那么你可以把你的问题当成“做两条线相交”的经典问题? 然后可以检查这些线对中的哪一对不与任何ABC三角形边相交,例如, 来自此问题的任何方法 。 因此,你将有新的三角形的两个新的边缘。

搞清楚你是否在一个明确的区域(下面的1,2,3)中是相当容易的:把你的三角形的每个边看作一个2D平面,并testing你新点的平面的哪一侧。 如果你在其中两个而不是一个内部,那么这个对应于三角形的边缘,它为你的新三角形贡献了两个顶点。

Voronoi地区的一个三角形

如果你是在一个和两个外面,你是在一个模糊的情况下,你的新点的三角形的最近的部分是一个角落。 在这种情况下,您可以从相对边缘(您内部的那个边缘)和最近的顶点(您在外面的两个平面共享的顶点)的中点形成2D平面。 你可以select一个边缘,取决于你的新点在这个平面的哪一边。

请注意,2D中的平面testing的工作方式与3D中的相同:从平面上的任意位置点到平面的法向(2D,这是线的垂线)。

(顺便说一句,这个图像中的洋红色分隔的区域被称为Voronoi区域;它们是包含最靠近三角形的特定边缘或顶点的点的空间区域。相当正确,这些不完全是Voronoi地区。)