8

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

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

如何从这个多边形的内部统一选择一个随机点？

4

2 回答 2

18

我会分三个步骤来做到这一点：

  1. 创建一个三角形列表，这些三角形覆盖与给定多边形相同的区域。如果您的多边形是凸的，则更容易，因为您可以让所有三角形共享一个公共顶点。如果您的多边形不能保证是凸的，那么您将不得不找到一种更好的多边形三角测量技术。这是相关的维基百科文章。

  2. 随机选择要使用的三角形，按其面积加权。因此，如果三角形 A 占面积的 75%，三角形 B 占面积的 25%，则应选择三角形 A 的时间为 75%，选择三角形 B 的时间为 25%。这意味着找到每个三角形占据的总面积的一部分，并将其存储在一个列表中。然后从 0 - 1 生成一个随机双精度数（Math.random() 执行此操作），并减去列表中的每个值，直到下一个减法将其变为负数。这将随机选择一个三角形，并考虑到面积权重。

  3. 在所选三角形内随机选择一个点。您可以使用这个公式：在三角形中采样随机点。

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

不过，您仍然需要一个算法来确定该点是否在多边形内。如果你已经把它分成三角形，这更容易，只需检查它是否在其中任何一个中。

于 2013-10-20T19:45:14.890 回答
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为此目的使用 a 。

如果double不需要精度，只需将其替换为float（您还必须更改Point.Double为Point.Float并强制Math.random()转换为 a 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()));
}
于 2013-10-20T21:13:03.560 回答