冷拔異型基於分確保線不交叉

說，我有100分，想畫一個closedcurve（我使用C＃和圖形），像這樣：冷拔異型基於分確保線不交叉

Graphics g = this.CreateGraphics(); 
     Pen pen = new Pen(Color.Black, 2); 
     Point[] points = new Point[DrawingPoints]; 
     for (int x = 0; x < DrawingPoints; x++) 
     { 
      int px = r.Next(0, MaxXSize); 
      int py = r.Next(0, MaxYSize); 
      Point p = new Point(px, py); 
      points[x] = p; 
     } 
     g.DrawClosedCurve(pen, points);

它連接因爲他們進入點[]和線交叉點 - 你不會得到一個堅實的數字與此。

是否有一個算法，這將有助於我折騰分獲得了堅實的身影？下面是一張圖片（儘可能努力地嘗試）來幫助可視化我要求的內容。

enter image description here

來源

2011-11-27 abolotnov

應該，說發生什麼事，非交叉新月形狀？ – Per

同樣的問題改寫 - 如果我點的數組，如何「拋」他們，如果它們連接在它們的順序我結束了一種固體形狀（線不交叉）的方式。 – abolotnov

@Per，真的沒什麼，這只是一個正常的形狀就像任何其他。 – abolotnov

那麼，在爲O（n log n）的時間，你可以計算點的質心和有關心角的順序進行排序，留下一個星形多邊形。這是有效的，但可能會過多地擾亂你點的順序。

我想你會更開心了2-OPT方法的結果TSP（說明here）。 2-OPT在實踐中是最壞情況指數但是多項式時間。

來源

2011-11-27 19:00:59 Per

冷拔異型基於分確保線不交叉

回答

相關問題