2014-04-28 174 views
1

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

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

Before and after

+0

你能夠通過網格線拆分三角形,或者是問題的一部分嗎?一旦你分割它,你就剩下一些凸多邊形的集合。由於它們是凸面的,因此很容易分解成三角形。 –

+0

這就是問題所在。我會期望在某些分割上出現凸多邊形,但我可以將這些分成三角形。 – voodoogiant

+0

添加了一個答案希望你知道如何計算線路之間的交集... – Spektre

回答

0

我認爲是這樣的:

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

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

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

2.split多邊形幾行列出

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

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

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

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

  • 所以只是把它分解到三角形
  • (三角形扇)

triangle to grid