如何获得不规则多边形内部的随机点？

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())); 
}