如何生成平面凸多邊形內部的隨機點？

01-01

假設已知平面內凸多邊形各頂點坐標，如何在凸多邊形內部均勻生成隨機數？

拆成若干個三角形，先按面積大小的概率選定三角形，再在三角形內選定隨機點。

補充一下 @葉飛影的答案，按面積大小採樣是一個離散採樣問題，可使用 Alias method 達到 O(1) 運行時間、O(n) 預計算時間和 O(n) 空間。多年前寫過一篇相關的博文回應CSDN肖舸《做程序，要「專註」和「客觀」》，實驗比較各離散採樣演算法。

找一個適當大小的矩形把該區域蓋住，在矩形內隨機取點。沒取到該區域的點就再來一次，直到取到為止。

多次取也取不出來的可能性是有的，比如某種凹多邊形的情況比如星形，目標區域占矩形面積不高的情況下。但持續取點，可以取到的概率是趨向於1的。但是如果確實多邊形長得比較奇怪無法取到合適的矩形，這種情況下就用樓上的方法吧。這種方法的優點是編程容易一些。

取凸多邊形的外接矩形，在矩形中隨機取點，如果落在凸多邊形外，再次隨機取點，直至落在凸多邊形內。

ArcGIS里有Create Random Points工具，實現方法是對多邊形進行三角切分，按三角形面積大小為概率隨機取出一個三角形，對三角形的兩條邊各取隨機數作平行線，交點在三角形內則為採樣點，交點在三角形外則對稱映射到三角形內作為採樣點。同 @葉飛影的答案。

Use normalized barycentric coordinate

各點坐標作為基。