问题标签 [triangulation]

我一直在研究Delaunay 三角剖分（不是作业），我想到了以下问题：给定S平面上的一组点（基数为n）和一组三角形T（基数应为n-2） - 如何确定是否三角形设置T形成一个德劳内三角剖分DT(S)？

第一个问题是 Delaunay 三角剖分不是唯一的，因此再次为点集重建它并与三角形集进行比较不会给我们答案。此外，最优的 Delaunay 三角剖分算法很难实现（但是，使用像 CGAL 这样的库就可以了）。

假设我们知道如何检查三角形集是否是三角剖分（不一定是 Delaunay）。那么我们应该使用 Delanuay 三角剖分的定义：对于三角剖分中的每个三角形t，没有一点 inS严格位于 的圆周内t。这导致我们采用以下方法：

1. 琐碎的方法。只需迭代T，计算圆周并迭代S，检查点是否在圆周内。然而，这需要O(n^2)时间，这不是非常理想的。
2. 迷人的方法。再次，迭代T并计算周长。如果有一点s在圆周内，则表示它到圆周中心的距离小于半径。使用最近邻搜索结构S，我们将加快我们的算法。例如，简单的 kd-tree结构将我们引导到O(n log n)平均和O(n sqrt(n))最坏情况下的算法。
3. 有没有人有更简单的想法？

现在让我们回到检查是否T是三角剖分的问题。诸如 的相等性S和三角形的顶点集之类的琐碎先决条件的执行速度不会比O(n log n). 剩下的——检查每两个三角形是否T在一个共同的面上相交，或者根本不相交。

1. T同样，我们可以通过一遍又一遍地迭代来做到这一点T，检查交叉点，但这是O(n^2)算法。
2. 让我们想想«三角形t1和t2相交»是什么意思？如果它们的边相交或者如果一个三角形完全位于另一个三角形中，则它们相交。O(n log n)使用Bentley-Ottmann 算法可以及时解决所有边相交的问题（最坏的情况是O((n + k) log n)，其中k是交叉点的计数，但我们可以在找到第一个交叉点的那一刻停止算法）。此外，我们没有认识到一个三角形完全包含另一个三角形的情况，但我相信我们可以修改 Bentley-Ottmann 算法以保持三角形穿过扫描线而不是线段，正如我所说，这产生了我们的O(n log n)算法。但是，实现起来确实很复杂。
3. 我考虑过迭代算法——让我们保持不相交（或仅通过边相交）三角形的结构（它应该与 kd-tree 非常相似）。然后我们尝试添加下一个三角形t：首先检查t' 的任何顶点是否已经在其中一个三角形中——然后我们得到了一个交点。否则，添加t到结构中。但是，如果我们想要O(log n)或O(sqrt(n))有时间进行搜索和添加查询，我们必须平衡这个结构的高度，这对于 kd-trees 来说也太难了。

那么，有没有人知道这个问题的任何简单解决方案？

我正在尝试使用openmp并行化Guibas Stolfi delaunay 三角测量。

这里有两件事要并行化-我所做的mergesort()和我被卡住的divide() 。我尝试了所有可能的方法，但徒劳无功。

在 divide() 中遵循的方法（除 n 征服）与 mergesort() 相同，但应用相同的并行化技术（omp 部分）仅适用于 mergesort。

我尝试了此处显示的并行化技术，但即使这样也行不通。我在某处读到了嵌套并行性，但我不确定如何实现它。谁能解释分治算法是如何并行化的？

代码：在主函数和应用部分构造中调用了两次合并排序。对除法执行相同操作不起作用

当我尝试使用 GLUtesselator 对文本实体进行三角测量时遇到了这个问题。但是，它可以在使用 GLUtesselator 对任何多边形进行三角剖分期间发生。问题是有时 GLUtesselator 会生成面积为零的三角形。大多数时候您可以忽略它们，但在某些情况下它们不能被忽略。我试图找到一个解决方案，以便给定多边形的最终三角剖分没有任何零面积三角形或 T 形交点。据我所知，GLUtesselator 是可用的最强大和最稳定的 tesselator 之一，所以我想坚持下去，不介意做一些后处理来修复三角剖分，而不是自己编写一个新的 tesselator。

我将尝试演示字符“H”的镶嵌问题。请注意，我是 stackflow 的新用户，所以我还不能发布图片，没有图片就不可能解释这个问题，所以我只是将 URL 发布到我描述问题的博客上。您也可以在 GLUtesselator 上查看它：零面积三角形和 T 形交点的问题http://www.dixittech.com/blog

我认为这是一个非常基本的问题，它的解决方案将使许多在类似领域工作的开发人员受益。我相信我不是第一个偶然发现它的人。有什么建议可以做到吗？任何替代方法也非常受欢迎。

我正在研究一种相当于旅行商问题的路径规划算法。我不知道我可能有多少个节点，所以我愿意牺牲准确性来换取速度。我的问题可以建模为一个完全连接的图，节点之间的转换成本不仅仅与节点之间的距离有关。我想将我的搜索空间限制为位于 delaunay 三角剖分上的连接（我读过的研究指出，TSP 解决方案中 95-100% 的连接位于 delaunay 三角剖分上）但由于我的图表无法表达作为 2D 甚至 3D 几何，我不能直接在我的表示中使用它。

我想为大于 3 维（4-6）的情况建立三角测量。我有代表非凸面的点。对于 2D 和 3D 案例，DelaunayTri 是一种可行的方法。更高维度呢？

（原问题是用线性超平面逼近一些非线性超曲面）

问候， 安德烈

我正在寻找一个包含网格操作工具（数据结构、网格简化算法、三角剖分）的 java 库。类似于http://gts.sourceforge.net/index.html但适用于 Java。

Stack 上有一个类似的问题，但它是从 09 年开始的，没有令人满意的答案……所以再一次。

我在整个互联网和科学数据库中搜索了一篇关于单调多边形的 Delaunay 三角剖分的论文。我不是在寻找任意的多边形三角剖分，而是在寻找 Delaunay 三角剖分。有人知道这样的出版物，其中单调多边形是德劳内三角剖分的吗？谢谢！

我试图从一组非常稀疏的数据中绘制出无线网络的信号强度，并且想知道在数学上是否可以做到这一点。

想象一下，我们在手机上安装了一些应用程序，每部手机都将它们的位置和信号强度上传到某个中央数据库。目标是利用这个非常稀疏的图表并尝试绘制信号强度，然后能够在二维或三个维度上猜测无线网络的有用范围。我认为我们还应该想象没有人直接站在接入点旁边，因此中心将是未知的。非常粗略地说，在我们生成一个有用的无线网络网格以绘制多边形之前，我们需要什么密度的点？

您可以期望在 DBM 中测量的无线网络强度与距离成反比和线性关系。我想知道这是否可以用来帮助为 Delaunay 转换生成额外的点？

我见过很多线模式的地形，所有地形都使用三角形。如果您将它用于不同的高度，我就明白了，但是为什么人们在地形中的平坦区域使用这么多三角形？如果有一个大的平坦区域，创建一个大正方形或至少一个大三角形（尽可能大）而不是使用这么多小三角形不是明智的吗？

所以我的问题是，是否有理由这样做（也许是纹理）？我知道镶嵌做了类似的事情，但从我的角度来看仍然留下了太多的三角形。

以下代码（Pg.187，Rourke 的 C 语言计算几何）需要相同的时间来串行运行和并行运行（2 proc）。请帮我找出问题所在。这是平行部分