如何獲得不規則多邊形內部的隨機點？

Question

我有一組描述不規則的多邊形區域的邊界點：

int [] x = { /*...*/ }; 
int [] y = { /*...*/ }; 

我怎樣才能均勻地選擇這個多邊形內部的隨機點？

Answer 1

我將分三個步驟做到這一點：

1. 創建覆蓋同一區域，你給出的多邊形的三角形的列表。如果您的多邊形是凸面的，則更容易，因爲您可以讓所有三角形共享一個公共頂點。如果你的多邊形不能保證凸出，那麼你將不得不尋找一個更好的多邊形三角測量技術。這裏是相關的Wikipedia article。

2. 隨機選擇使用哪個三角形，按其面積加權。因此，如果三角形A佔面積的75％，三角形B佔面積的25％，則三角形A應該選擇75％的時間和B 25％。這意味着找出每個三角形佔據的總面積的一小部分，並將其存儲在一個列表中。然後生成一個從0到1的隨機雙數（Math.random（）做到這一點），並減去列表中的每個值，直到下一個減法使它爲負。隨機選取一個三角形，考慮面積權重。

3. 隨機挑選所選三角形內的一個點。你可以使用這個公式：sample random point in triangle。

或者，您可以選擇一個覆蓋整個多邊形的矩形（如邊界框），並隨機選取該矩形內的一個點。然後檢查點是否在多邊形內，如果不是，則生成一個新的隨機點並再次嘗試，必要時重複。從理論上講，這可能會持續一段時間，但實際上最多需要四到五次嘗試。

你仍然需要一個算法來確定點是否在多邊形內。如果你已經把它分解成三角形，這很容易，只要檢查它是否在任何這些。

Answer 2

如果你打算用java做這個，你真的應該有一個類的點，而不是使用平行數組。此外，雖然技術上允許使用下劃線作爲名稱的首字母，但這不是最佳做法;如果您使用它來表示它們僅用於內部使用，則將其聲明爲private或protected或您需要的任何內容。

import java.awt.Point; 
import java.awt.Shape; 
import java.awt.Rectangle; 

/** 
* This method uniformly selects a random point contained in the shape 
* supplied to it. 
* @param region The region to select from. 
* @returns A random point contained in the shape. 
*/ 
Point generatePoint(Shape region){ 
    Rectangle r = region.getBounds(); 
    double x, y; 
    do { 
     x = r.getX() + r.getWidth() * Math.random(); 
     y = r.getY() + r.getHeight() * Math.random(); 
    } while(!region.contains(x,y)) 

    return new Point.Double(x,y); 
} 

這樣做，彎曲的邊界就像處理一樣容易。如果需要，您甚至可以傳遞非連續區域。從點生成形狀也很容易;我建議爲此使用Path2D。

如果不需要double精度，只是float取代它（你也將不得不改變Point.Double到Point.Float和投Math.random()到float）。

其中一個問題就是如果這個區域非常稀疏，那麼它只包含極小比例的邊界框，那麼性能可能會受到影響。如果這成爲問題，則需要使用更高級的方法，包括對多邊形進行網格劃分並選擇網格單元。另外，如果該區域完全是空的，該方法將永遠不會返回。如果需要保護這些問題，那麼我會建議對其進行更改，以便在放棄和返回空值之前只嘗試一些數字（從幾十到幾千）。

爲了從點狀物體，你可以這樣做：

import java.awt.geom.Path2D; 

//[...] 

Path2D path = new Path2D.Double(); 

path.moveto(_x[0], _y[0]); 
for(int idx = 1; idx < _x.length; idx++) 
    path.lineto(_x[idx], _y[idx]); 
path.closePath(); 

---

如果只有整點的需要，然後做隨機生成這樣，而不是：

import java.awt.Point; 
import java.awt.Shape; 
import java.awt.Rectangle; 

/** 
* This method uniformly selects a random integral point contained in the 
* shape supplied to it. 
* @param region The region to select from. 
* @returns A random point contained in the shape. 
*/ 
Point generateIntegralPoint(Shape region){ 
    Rectangle r = region.getBounds(); 
    int x, y; 
    Random rand = new Random(); 
    do { 
     x = r.getX() + rand.nextInt((int) r.getWidth()); 
     y = r.getY() + rand.nextInt((int) r.getHeight()); 
    } while(!region.contains(x,y)) 
    return new Point(x,y); 
} 

或者，如果你是我的形狀有趣的是相當小，你可以遍歷邊界框中的所有積分點，將有效點添加到列表中，然後從列表中選擇。

import java.awt.Point; 
import java.awt.Shape; 
import java.awt.Rectangle; 

/** 
* This method uniformly selects a random integral point contained in the 
* shape supplied to it. 
* @param region The region to select from. 
* @returns A random point contained in the shape, or {@code} null if the 
*   shape does not contain any integral points. 
*/ 
Point generateIntegralPoint(Shape region){ 
    Rectangle r = region.getBounds(); 
    Random rand = new Random(); 

    ArrayList<Point> list = new ArrayList<>(); 

    for(int x = (int) r.getX(); x <= (int) (r.getX() + r.getWidth()); x++) 
     for(int y = (int) r.getY(); y <= (int) (r.getY() + r.getHeight()); y++) 
      if(region.contains(x,y)) 
       list.add(new Point.Float(x,y)); 

    if(list.isEmpty()) 
     return null; 

    return list.get(rand.nextInt(list.size())); 
}