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

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）

其中一个问题是，如果区域非常稀疏，即它只包含其边界框的一小部分，那么性能可能会受到影响。如果出现问题，则需要使用更高级的方法，包括对多边形进行网格划分和选择网格单元。此外，如果区域完全为空，则该方法将永远不会返回。如果需要这些问题的保护，那么我建议对其进行更改，使其在放弃并返回null之前只进行一些尝试（从几十次到几千次）

要从点生成形状对象，可以执行以下操作：

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