I want to create a set of N random convex disjoint polygons on a plane where each polygon must have at most V vertices, where N and V are parameters for my function, and I'd like to obtain a distribution as close as possible to uniform (every possible set being equally probable). Also I need to randomly select two points on the plane that either match with one of the vertices in the scene or are in empty space (not inside a polygon).

I already implemented for other reasons in the same programming language an AABB tree, Separating Axis Theorem-based collision detection between convex polygons and I can generate a random convex polygon with arbitrary amount of vertices inside a circle of given radius. My best bet thus far:

1. Generate a random polygon using the function I have available.
2. Query the AABB tree to test for interception with existing polygons.
3. If the AABB tree query returns empty set I push the generated polygon into it, otherwise I test with SAT against all the other polygons whose AABB overlaps with the generated one's. If SAT returns "no intersection" I push the polygon, otherwise I discard it.
4. Repeat from 1 until N polygons are generated.
5. Generate a random number in {0,1}
6. If the generated number is 1 I pick a random polygon and a random vertex on it as a point
7. If the generated number is 0 I generate a random position in (x,y) and test if it falls within some polygon (I might create a tiny AABB around it and exploit the AABB tree to reduce the required number of PiP tests). In case it's not inside any polygon I approve it as a valid point, otherwise I repeat from 5.
8. Repeat from 5 once more to get the second point.

I think the solution would possibly work, but unfortunately there's no way to guarantee that I can generate N such polygons for very large N, or find two good points in an acceptable time, and I'm programming in React, where long operations run on the main thread blocking the UI till they end. I could circumvent the issue by ejecting from create-react-app and learn Web Workers, which would require probably more time than it's worth for me.

CodePudding user response：

This is definitely non-uniform distribution, but perhaps you could begin by generating N points in the plane and then computing the Voronoi diagram for those points. The Voronoi diagram can be computed in O(n log n) time with

^{By Balu Ertl - Own work, CC BY-SA 4.0, Link}

CodePudding user response：

Ok, here is another proposal. I have little knowledge of js, but could cook up something in Python.

1. Use Poisson disk sampling with distance parameter d to generate N samples of the centers

2. For a given center make a circle with R≤d.

3. Generate V angles using Dirichlet distribution such that sum of angles is equal to 2π. Sort them.

4. Place vertices on the circle using angles generate at step#3 and connect them. This would be be your polygon