將三角形網格化爲網格

Question

是否有一種算法可以將可能跨越多個網格單元的三角形劃分爲多個三角形，其中沒有跨越多個網格單元的三角形？

我已經在一個2x2網格中包含了一個蹩腳的手繪三角形，將其切成七個更小的三角形。

Answer 1

我認爲是這樣的：

• 你的三角形是三線閉多邊形
• 點的順序爲您提供了纏繞規則（順時針或逆時針）

1 。按網格線切割所有線條

• 但仍留下三角形作爲單一封閉的多邊形
• 不改變繞組

2.split多邊形幾行列出

• 剛剛組合在一起屬於同一網格單元的所有行
• 所以所有的點是在單元格內或在邊緣
• 不改變繞組！

3.convert行列出了封閉的多邊形

• 開始在其方向在第一線名單第一行
• 如果加入實際列表中的任何行繼續與它
• 如果不是，則繼續在相同卷繞方向上的細胞邊緣線
• 直到命中另一個線點或細胞角落
• 重複此操作直到關閉pol ygon爲這個細胞形成（打已經使用線/點））
• 過程中的其他細胞以同樣的方式

4.now你已經關閉凸多邊形列表

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