将三角形网格化为网格

Question

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

我已经在一个2x2网格中包含了一个蹩脚的手绘三角形，将其切成七个更小的三角形。

Answer 1

我认为是这样的：

• 你的三角形是三线闭多边形
• 点的顺序为您提供了缠绕规则（顺时针或逆时针）

1 。按网格线切割所有线条

• 但仍留下三角形作为单一封闭的多边形
• 不改变绕组

2.split多边形几行列出

• 刚刚组合在一起属于同一网格单元的所有行
• 所以所有的点是在单元格内或在边缘
• 不改变绕组！

3.convert行列出了封闭的多边形

• 开始在其方向在第一线名单第一行
• 如果加入实际列表中的任何行继续与它
• 如果不是，则继续在相同卷绕方向上的细胞边缘线
• 直到命中另一个线点或细胞角落
• 重复此操作直到关闭pol ygon为这个细胞形成（打已经使用线/点））
• 过程中的其他细胞以同样的方式

4.now你已经关闭凸多边形列表

• 所以只是把它分解到三角形
• （三角形扇）