8

不規則な多角形領域の境界を表す点のセットがあります。

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

この多角形の内部からランダムな点を一様に選択するにはどうすればよいですか?

4

2 に答える 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して aPoint.Floatにキャストする必要もあります)。Math.random()float

これに関する 1 つの落とし穴は、リージョンが非常にまばらで、バウンディング ボックスのごく一部しか含まれていない場合、パフォーマンスが低下する可能性があることです。これが問題になる場合は、ポリゴンのメッシュ化とメッシュ セルの選択を含む、より高度な方法を使用する必要があります。また、領域が完全に空の場合、メソッドは戻りません。これらの問題からの保護が必要な場合は、あきらめて 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 に答える