How to get a random point on the inner surface of an irregular polygon?

Question

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

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

How can I evenly select a random point from the inside of this polygon?

Answer 1

I would do this in three steps:

• Create a list of triangles that cover the same area as the provided polygon. If your polygon is convex, this is easier since you can have all the triangles with a common vertex. If your polygons are not guaranteed convex, you will need to find the best polygon triangulation technique. Here is the related Wikipedia article .

• 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 selected at 75% of the time and B 25%. This means finding a fraction of the total area that each triangle occupies and keeping it in the list. Then create a random double number from 0 - 1 (this is what Math.random () does) and subtract each value in the list until the next subtraction makes it negative. This will select the triangle at random based on weight.

• Randomly select a point in the selected triangle. You can use this formula: a sample of a random point in a triangle .

Alternatively, you can select a rectangle that spans the entire polygon (for example, its bounding rectangle) and randomly select a point inside that rectangle. Then check if the point is inside the polygon, and if it does not generate a new random point and try again, repeating if necessary. Theoretically, this can last forever, but in practice it should go through a maximum of four or five attempts.

You still need to have an algorithm to determine if a point is inside the polygon. If you have already divided it into triangles, it’s easier, just check if it was in any of them.

Answer 2

If you are going to do this using java, you really should have a class for glasses, instead of using parallel arrays. Also, while it is technically permitted to use underscores as the initial character for a name, this is not best practice; if you use this to indicate that they are intended for internal use only, 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); } 

By doing this, curved borders are processed just as easily. If you wish, you can even give him substandard areas. Creating shapes from dots is also easy; I would recommend using Path2D for this purpose.

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

The only catch in this is that if a region is very sparse, it contains only a very small percentage of its bounding box, then performance may suffer. If this becomes a problem, you will need to use a more advanced method, including combining the polygon and selecting the cell cell. Also, if the area is completely empty, the method will never return. If you need protection against these problems, I would recommend changing it so that it can only make a certain number (from several tens to several thousand) of attempts before abandoning it and returning null.

To create a shape object from 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 integer points are desired then randomly generate 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); } 

Alternatively, if the shapes you are interested in are quite small, you can simply iterate over all the integer points in the bounding box, add valid ones to the 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())); }