0

是否有一种算法可以将可能跨越多个网格元素的三角形划分为多个三角形，其中没有跨越多个网格元素的三角形？

我在 2x2 网格中包含了一个糟糕的手绘三角形，该网格被切成七个较小的三角形。

之前和之后

4

2 回答 2

1

我是这样看的：


您的三角形是 3 线闭合多边形
点顺序为您提供缠绕规则（CW或CCW）

  1. 用网格线切割所有线

    但仍将三角形保留为单个闭合多边形并且不改变绕组

  2. 将多边形拆分为几个线列表

    只需将属于同一网格单元的所有线组合在一起，因此所有点都在单元内部或边缘。再次不要改变绕组！

  3. 将线列表转换为闭合多边形

    从其方向的第一行列表中的第一行开始。如果它加入实际列表中的任何行，请继续。如果不是，则继续沿相同的缠绕方向使用单元边缘线，直到碰到另一个线点或单元角。

    重复此操作，直到为该单元格形成闭合多边形（命中已使用的线/点））。以同样的方式处理其他单元格

  4. 现在你已经关闭了凸多边形列表

    所以把它分成三角形（三角形扇形）

三角形到网格

于 2014-05-05T08:16:33.867 回答
0

看到除我之外的其他人也曾尝试过这一点实际上非常令人耳目一新（我一直在用 OpenGL 编写一个引擎，它根据这个概念构建地形，但也将它放入 3d 中）。

话虽如此，Spektre 是对的。我的引擎遵循的几条规则与他的相似：

  • 坚持 CW 或 CCW 绕组（我使用的是 CW）

  • 我只是把三角形分割成更小的三角形，所以它们都是凸的——所以没有凹多边形。

  • 检测要分割的三角形数量的公式是N - 2，其中N是单元格中的点数。显然如果是3，你就有了一个完美的三角形（比如上面网格单元格中的蓝色三角形）

稍后我会尝试为您上传一些图片。希望您仍在为此努力或至少取得了进展！

于 2018-07-05T20:19:45.790 回答