How can I generate polygons like in a Voronoi diagram/Thiessen Polygons and get the nodes for each of the polygons?

Question

I want to be able to generate a set of polygons where I can extract all nodes for every polygon. For example:

Polygon 1 - (0, 0),(0,2),(2,0)
Polygon 2 - (0, 2),(2,2),(2,0)
Polygon 3 - (0, 2),(5,5),(8,5),(8,0),(2,0)
And so on...

I'm not interested in available tools since this is just a part of a project. I want to be able to insert random points to generate this random dataset with polygons and its nodes coordinates.

Where do I start? Is there an algorithm I can implement in a programming language? BTW: the data is supposed to be used in a PostgreSQL database as geometries. The language I want to use is Java.

Answer 1

The Tinfour project has a Java class called the BoundedVoronoiDiagram that may be useful to you as a source of ideas, see Tinfour.org. There an example application called ExampleVoronoi that I used (slightly modified) to produce the following picture from 10 vertices:

Adding the following code to the end of the demo produces a list of polygons and their vertices. The code identifies polygons as either open (unbounded) or closed (bounded and finite):

List<ThiessenPolygon> polygons = diagram.getPolygons();
for (ThiessenPolygon p : polygons) {
    Vertex v = p.getVertex(); // defining vertex for polygon
    String openString = p.isOpen() ? "open  " : "closed";
    double area = p.getArea();
    System.out.format("Vertex %2d, polygon is %s, area=%5.2f%n",
            v.getIndex(), openString, area);
    List<IQuadEdge> edges = p.getEdges();
    for (IQuadEdge e : edges) {
        Vertex a = e.getA(); // first point in edge
        System.out.format("   %12.6f, %12.6f%n", a.getX(), a.getY());
    }
}

For example:

Vertex  9, polygon is closed, area= 0.09
       0.358217,     0.496937
       0.625090,     0.764692
       0.454992,     0.887576
       0.181977,     0.854051