问题标签 [triangulation]

最近做了一些计算机图形化编程，之前没有经验。我使用了库调用 CGAL（计算机几何算法库）。另外，我注意到有三角测量类和网格类。网状网只是一种三角网吗？他们有什么不同吗？

谢谢！

我最近遇到了需要一个库或一组库来处理二维多边形上的操作。我需要能够执行布尔/裁剪操作（差异和联合）和三角测量。

到目前为止，我发现的库是poly2tri、CGAL和GPC。Poly2tri 看起来很适合三角剖分，但我仍然需要布尔运算，而且我不确定它的成熟度。

只有我自己的项目是免费的，CGAL 和 GPC 才免费。我的特定项目不是商业项目，所以我对支付或申请任何许可证犹豫不决。但我可能想将我的代码用于未来的商业项目，所以我对 CGAL 的开源许可证和 GPC 的仅限免费软件的限制犹豫不决。似乎没有任何具有良好 BSD 风格许可证的多边形裁剪库。

哦，C/C++ 是首选。

有人知道 Maya 使用什么三角测量算法吗？缺乏这一点，最有可能尝试的算法是什么？我尝试了一些简单的方法（最短/最长的边缘，最小的最小角度，最小/最大的区域），但它们都错了。Delaunay 是最合理的算法吗？

编辑：顺便说一句，关于如何在 3D 空间中为 2D 四边形实现 Delaunay 以生成两个三角形的伪代码非常受欢迎！

编辑 2：不幸的是，这不是 3D 空间中的答案（仅适用于 2D）。

我有两个地形的 TIN（三角形不规则网络）。第一个（TIN1）是原始的，假设有 X 个点。另一个（TIN2）被简化（点的数量被一些抽取算法减少了），假设它是从 Y 点构建的，其中 X>Y。现在，我如何在这两个 TIN 之间进行以下比较：

1) TIN2 与 TIN1 有何相似之处？或 TIN2 如何偏离 TIN1？或者我如何比较 TIN2 与 TIN1 的精度？

2) 有哪些工具或方法可以帮助我获得关于 TIN2 相对于 TIN1 准确性的大部分信息？

如果你能指出我的任何论文、书籍、链接……？非常感谢！

我正在寻找一种打包算法，它将正多边形减少为矩形和直角三角形。该算法应尝试使用尽可能少的此类形状，并且应该相对容易实现（考虑到挑战的难度）。

如果可能，这个问题的答案应该解释建议算法中使用的一般启发式方法。

我有数千个四边形数组；4 面 3D 多边形。我所知道的只是四角的坐标。

这些四边形的子集定义了 3D 形状的封闭外壳。其余的四边形位于这个封闭实体的内部。

如何确定哪些四边形是外壳的一部分，哪些四边形是内部的一部分？这不是性能关键代码。

编辑：对外壳形状的进一步限制

• 形状内部没有孔，它是一个单一的表面。
• 它包含凸面和凹面部分。
• 我有一些已知在外壳内部的点。

我在看这个关于这个图书馆的问题。然而，我仍然不清楚这个库是否可以像 glu tesselator 那样做并返回一系列三角形，然后我可以用 OpenGL 渲染这些三角形。如果它可以做到这一点，这是如何做到的？我只是从阅读文档中不清楚这一点。所以基本上我想要找出的是，如果它实际上可以三角化，一旦我添加了我的轮廓，我如何获得三角形顶点以便我可以用 opengl 渲染它们？

谢谢

我有一个顶点表示三角形条带的数组。我需要将其转换为多边形。有很多解决方案可以做相反的事情，但我没有找到解决上述问题的方法。或者它可能太容易了，我只是看不到它。请帮忙。

OpenGL=兼容，见 http://en.wikipedia.org/wiki/Triangle_strip

示例：对于这个地带http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png 我需要输出 ABDFEC 或 ACEFDB

完成 2D 三角剖分后，一些三角形具有相同的颜色，我想重新组合它们以绘制类似颜色的图形路径。我发现如果我只是一个一个地绘制三角形，一些图形渲染器会显示三角形之间的接缝（至少在涉及抗锯齿和/或透明度的情况下）。

那么如何获取一组（非重叠）三角形并生成可能包含孔和不相交多边形的图形路径？

盲目地将三角形添加到图形路径实际上非常适合填充（当然不是用于描边），但是导出那些额外的内部点感觉不合适。

大多数迭代算法需要一个初始的空三角形来让球滚动。似乎一个常用的技巧就是使超三角形与点集相比非常大。

但根据“数值配方：科学计算的艺术”：

“......如果距离只是有限的（到边界点），则构造的三角剖分可能不是非常德劳内。例如，在不寻常的情况下，它的外边界可能会略微凹入，具有直径数量级的小负角“真实”点集除以到“虚构”（边界）点的距离。

那么有哪些选项可以用无穷远处的点来增加笛卡尔坐标，而不必将所有输入转换为不同的坐标系，例如齐次坐标？这些点如何与通常的几何谓词 CCW 和 Incircle 相匹配？

Incircle (a,b,c) Infinity -> False。假设 a,b,c 是有限的。

但是当 a,b,c 之一是无穷远点时呢？圆变成半平面然后测试变成逆时针检查吗？如果外接圆上有 2 个或更多点是无限的怎么办？圆圈是否扩展成一个完整的平面，导致测试始终为真？CCW呢？您如何根据在无穷远处有一个或多个点的线对点进行分类？