正則多邊形的高效包裝算法

我正在尋找一種包裝算法，它會將正多邊形縮減爲矩形和直角三角形。該算法應該嘗試儘可能少地使用這種形狀，並且應該相對容易實施（鑑於挑戰的難度）。正則多邊形的高效包裝算法

如果可能的話，這個問題的答案應該解釋在建議的算法中使用的一般啓發式。

來源

2010-07-21 Steve

這是算法類還是計算機圖形類？ – eruciform 2010-07-21 03:34:22

這不適合上課。我不在學校。 – Steve 2010-07-21 03:35:50

事實上，如果他們可以爲iPhone，Mac桌面和.net編程，我可能願意給一個能夠很好地回答問題的人。 ;） – Steve 2010-07-21 03:38:21

我認爲答案是相當簡單的常規多邊形。

找到一條對稱軸，並在每個頂點與其鏡像之間畫一條線。這將多邊形分成梯形。每個梯形可以變成一個矩形和兩個直角三角形。

來源

2010-07-21 05:05:05

通過證明這會產生最小數量的圖塊，您可以獲得額外的功勞。 :) – Svante 2010-07-21 09:33:33

我現在認爲這實際上是最佳的:-) – Mau 2010-07-21 12:48:23

不，它並不總是最佳的。以兩邊平行於x = 0軸的正六邊形爲例。然後這個算法產生2個矩形和4個直角三角形，但是1個矩形和4個三角形就足夠了。儘管如此，解決方案可能足夠好並且易於實施。 – abc 2010-07-21 13:19:31

它不是特別的矩形+直角三角形，但是研究鑲嵌多邊形的好研究點是Voronoi Diagrams and Delaunay Triangulations和here和here。實際上，如果「恰到好處的三角形」足夠好，那麼這些保證可以爲您進行三角剖分，並且如果您真的需要這些三角形，您總是可以將任何三角形分成兩個直角三角形。或者，您可以切掉三角形的「尖端」，以製作更多直角三角形和一些矩形。

您也可以嘗試ear-clipping，或者通過徑向掃掠，如果您知道自己有相當規則的多邊形，或者「截斷最大的凸塊」。然後，將每個剩餘的三角形分成兩個以創建直角三角形。

polygon http://static.eruciform.com/images/polygon.png

您可以嘗試通過掃描一個方式，然後將另一做出梯形，使更少的休息和不同的拆分它，但你必須做一個檢查，以確保您的掃描線不是招在另一條線上劃過一條線。即使實際上是分形的，你總是可以耳夾。

但是，這有時會創建非常纖細的三角形。你可以執行啓發式操作，比如「最大化」，而不是沿着邊緣連續剪裁，但是需要更多時間，接近O（n^2）。在大多數情況下，Delaunay/Vornoi會更快速地完成這項工作，而不需要很小的三角形。

來源

2010-07-21 03:38:20 eruciform

絕對必須是矩形和直角三角形。我知道這聽起來很奇怪，但這是用戶需求。 – Steve 2010-07-21 03:41:00

已更新。你可以很容易地將任何三角形變成直角三角形和矩形。 – eruciform 2010-07-21 03:44:08

Delaunay三角剖分在這裏並不理想，因爲它們在中間引入了額外的不必要的點。每個內部點都可以「拖動」到相鄰的多邊形頂點，並且剩下一小部分三角形。 – 2010-07-21 06:24:03

你可以嘗試「切出」the largest rectangle that can fit in the polygon，留下一些剩菜。繼續重複在剩餘物上切出長方形，直到最後得到三角形碎片。然後，如有必要，可以將它們分成兩個直角三角形。我不知道這是否總能產生能給你最少量的矩形和直角三角形的解決方案。

來源

2010-07-21 03:56:13

我認爲這不是一個好主意：儘可能多地吃掉第一個矩形區域，然後不會留下「最簡單」的形狀。 – Mau 2010-07-21 12:30:28

不清楚他的要求是什麼。最少的總體形狀或大多數面積最小的形狀...... – eruciform 2010-07-21 14:13:49

對於規則的多邊形，它仍然會給你「很好」的形狀。再次，我不知道這是否會給你「最優化」的解決方案。 – 2010-07-21 19:58:33

正則多邊形的高效包裝算法

回答

相關問題