How to get a random point on the interior of an irregular polygon? [closed]

Question

I have a set of points that describe the boundaries of an irregular polygonal region:

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

How can I uniformly select a random point from the interior of this polygon?

Answer 1

I would do this in three steps:

1. Create a list of triangles that cover the same area as the polygon you are given. If your polygon is convex it is easier, since you can have all triangles share a common vertex. If your polygons are not guaranteed to be convex, then you'll have to find a better polygon triangulation technique. Here's the relevant Wikipedia article.

2. Randomly choose which triangle to use, weighted by its area. So if triangle A is 75% of the area and triangle B is 25% of the area, triangle A should be picked 75% of the time and B 25%. This means find the fraction of the total area that each triangle takes up, and store that in a list. Then generate a random double number from 0 - 1 (Math.random() does this), and subtract each value in the list until the next subtraction would make it negative. That will pick a triangle at random with the area weights considered.

3. Randomly pick a point within the chosen triangle. You can use this formula : sample random point in triangle.

Alternatively, you can pick a rectangle that covers the entire polygon (such as its bounding box) and randomly pick a point within that rectangle. Then check if the point is inside the polygon, and if it isn't then generate a new random point and try again, repeating as necessary. Theoretically this could take forever, but in practice it should take four or five tries at most.

You still need to have an algorithm to determine if the point is inside the polygon though. If you already have it broken up into triangles this is easier, just check if it's in any of those.

Answer 2

If you are going to do this with java, you really ought to have a class for the points, instead of using parallel arrays. Additionally, while it is technically allowed to use an underscore as the initial character of a name, this is not best practice; if you are using that to denote that they are only for internal use, then declare them private or protected or whatever you need.

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

Doing it this way, curved boundaries are handled just as easily. You can even pass it noncontinuous regions, if desired. Generating the shape from the points is also easy; I would recommend using a Path2D for that purpose.

If double precision is not required, just replace it with float (you will also have to change Point.Double to Point.Float and cast Math.random() to a float).

The one catch on this is that if the region is very sparse, in that it contains only a very small percentage of its bounding box, then the performance may suffer. If this becomes a problem, you will need to use a more advanced method involving meshing the polygon and selecting a mesh cell. Also, if the region is entirely empty, the method will never return. If protection from these issues is needed, then I would recommend changing it so it will only make some number (anything from a few dozen to a few thousand) of attempts before giving up and returning null.

To generate the shape object from the points, you can do something like:

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

---

If only integral points are desired, then do the random generation like this instead:

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

Alternately, if the shapes you are interested in are fairly small, you could just iterate through all the integral points in the bounding box, add the valid ones to a list, and select from the list.

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