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

Question

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

9

我有一组描述不规则多边形区域边界的点：

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

我该如何从这个多边形内部均匀随机选择一个点？

- Arunas Jaspelkis

1

你是想从点集的凸包中选择点，还是从通过相邻顶点连接而成的（可能是凹多边形的）多边形中选择点？ - AJMansfield

2个回答

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

- AJMansfield

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mikebolt · Accepted Answer

我会分三个步骤来完成这个问题：

创建一个包含与给定多边形相同面积的三角形列表。如果您的多边形是凸的，那么更容易，因为您可以让所有三角形共享一个公共顶点。如果您的多边形不能保证是凸的，那么你需要找到更好的多边形三角剖分技术。下面是相关的维基百科文章。
随机选择要使用的三角形，权重由其面积决定。所以如果三角形A占据了75%的面积，而三角形B只占25%的面积，那么三角形A应该被选中的概率是75%，而B则是25%。这意味着找出每个三角形占据的总面积的分数，并将其存储在列表中。然后从0-1生成一个随机双精度数字（Math.random()做到了这一点），并将列表中的每个值相减，直到下一次相减使其变成负数。这将随机选择一个三角形，并考虑面积权重。
在所选择的三角形内随机选择一个点。您可以使用这个公式：sample random point in triangle。

或者，您可以选择一个覆盖整个多边形的矩形（例如其包围框），并在该矩形内随机选择一个点。然后检查该点是否在多边形内，并且如果它不在，则生成一个新的随机点并再次尝试，如有必要重复该过程。理论上可能需要很长时间，但实际上最多只需要四到五次尝试。

但是，您仍然需要有一个算法来确定该点是否在多边形内。如果您已经将其分解为三角形，则更容易，只需检查它是否在任何一个三角形中。