我正在尋找一種算法在多邊形內生成均勻分佈的點。在多邊形中生成均勻分佈點的算法
下面是情形：
我具有由點中的角部（X，Y）爲每一個點的座標指定的多邊形。我在多邊形內生成點的數量。例如，假設我有一個包含5個點的多邊形：（1，1）; （1,2）; （2,3）; （3，2）;和（3，1）
我需要在該多邊形內生成20個等距離的點。
注意：某些多邊形可能不支持均勻分佈的點，但我希望以儘可能一致地覆蓋多邊形的所有區域的方式分佈這些點。 （我的意思是我不想要一個比另一個更多的點）
有沒有一個算法來做到這一點？或者可能是一個庫
我正在研究C＃應用程序，但任何語言都可以，因爲我只需要算法並且可以將其翻譯。
非常感謝您的幫助
簡單的方法我用的是：
三角測量多邊形。耳朵剪裁完全合適，因爲您需要的只是將多邊形解剖爲一組不重疊的三角形。
計算每個三角形的面積。從每個三角形的樣本按比例相對於整個三角形的面積。這樣每個樣本只需要一個統一的隨機數。
確定一個點來自給定的三角形後，均勻地在三角形上進行採樣。這本身比你想象的要容易。
所以真的這一切都歸結爲你如何在三角形內抽樣。這很容易完成。三角形由3個頂點定義。我會給他們打電話P1，P2，P3。
挑三角形的任何邊緣。生成一個沿着該邊緣均勻分佈的點（P4）。因此，如果P1和P2是相應端點的座標，那麼如果r在區間[0,1]上具有均勻分佈，則P將是沿該邊緣的均勻採樣點。
P4 =（1-R）* P1 + R * P2
接着，沿P3和P4之間的線段樣品，但這樣做的不均勻。如果s是在區間[0,1]的均勻隨機數，然後
P5 =（1-SQRT（S））* P3 + SQRT（秒）* P4
r和s當然是獨立的僞隨機數。然後P5將隨機採樣，統一在三角形上。
好的是它不需要拒絕計劃來實現，所以很長的薄多邊形不是問題。對於每個樣本，成本只是需要每個事件產生三個隨機數。由於耳廓修剪相當簡單，而且是一項高效的任務，即使對於看起來很髒的多邊形或非凸多邊形，採樣也是有效的。
+1用於對多邊形進行三角化並對由三角形區域加權的離散分佈進行採樣。對於三角形內的採樣，我傾向於採樣右邊的單位三角形[（0,0），（0,1），（1,0）]並將仿射變換應用到目標三角形上;變換矩陣可以預先計算並且只需要乘法和加法即可有效應用。請注意，從右側單位三角形取樣很容易：'x，y < - U;如果x + y> 1，則x，y：= 1-y，1-x'。 – ecatmur
@ecatmur - 是的，有幾種方法可以在單工中進行抽樣。我使用了我選擇的那個，因爲更高維單形的擴展很容易看到。 – 2012-06-25 12:33:54
確實如此，但是從標準單位單體中抽樣也很容易和高效 - 參見例如http://stackoverflow.com/questions/3010837/sample-uniformly-at-random-from-an-n-dimensional-unit-simplex – ecatmur
一個簡單的方法來做到這一點是這樣的：
這種方法會產生一定數量的浪費點。對於一個三角形，它不會超過50％。對於任意多邊形，這可以是任意高的，所以你需要看看它是否適合你。
對於任意多邊形，可以先將多邊形分解爲三角形，這樣可以保證浪費點的保證上限：50％。
對於距離相等的點，從空間填充曲線生成點（並丟棄所有不在多邊形中的點）。
想象一下一個非常薄的矩形對角線定位。這浪費了大量的樣品。仍然是一個合理的方法。 –
@romkyns，我錯誤地只想到三角形。我爲任意多邊形添加了一個解決方案。 – usr
想象一下薄的_triangle_對角線位置:) :) –
Genettic算法可以在http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
做到這一點，而迅速
Reffer到GENETIC ALGORITHMS FOR GRAPH LAYOUTS WITH GEOMETRIC CONSTRAINTS
您可以使用強制向圖的是...
看它公然可以扔你骨頭。
我沒有嘗試過它，
但我remmember有一個方法可行設置一些頂點的修復在圖形
你的算法最終會像
量表圖的邊連接到有界框的
儘管它不會是絕對的，因爲一些凹凸形狀可以產生wiered結果（取一個星）
最後：沒看過，但似乎由標題相關的和抽象的
看看Consistent Graph Layout for Weighted Graphs
希望這有助於...
能解釋爲什麼他認爲這不好？ –
可能是因爲您提供的信息來源有助於開發不提供實際答案的答案 – MikeT
簡單的答案來自一個更簡單的問題：如何從均勻分佈中生成給定數量的隨機分佈點，這些點將全部適合給定的多邊形內？找到你的多邊形的邊界框（假設它是[a，b] x [c，d]），然後繼續生成實數對，其中一個來自U（a，b） ，另一個來自U（b，c），直到你有n個座標對適合你的多邊形。這很容易編程，但是，如果你的多邊形非常參差不齊，或者很薄並且傾斜，那麼非常浪費和緩慢。
爲了更好的回答，找到最小的旋轉矩形邊界框，並在變換後的座標中進行上述操作。
更好的答案來自一個更好的問題。假設你想把一組n個關塔覆蓋一個多邊形。您可以將其看作是一個優化問題：找到n個點的2n座標，以最小化符合您的目標的成本函數（或最大化值函數）。一個可能的成本函數可以計算每個點到最近鄰點的距離或多邊形的邊界（取較小者），並計算這個序列的方差作爲「非均勻性」的度量。您可以使用一組隨機的n個點，如上所述，作爲您的初始解決方案。
我在一些書中見過這樣的「崗位問題」。算法，演算或優化。
@Youssef：抱歉，延誤;一個朋友來了，一個網絡被打開了。 @其他：請耐心等待，不要這麼觸動我開心。
放置了了望塔的問題並不比採樣均勻分佈更好;這是一個完全不同的問題。 –
您可能想要嘗試http://math.stackexchange.com/獲取算法，然後在此處發帖，如果您需要幫助將算法轉換爲C＃。 –