如何生成像 Voronoi diagram/Thiessen 多边形中的多边形并获取每个多边形的节点？

Question

我希望能够生成一组多边形，我可以在其中提取每个多边形的所有节点。例如：

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...

我对可用工具不感兴趣，因为这只是项目的一部分。我希望能够插入随机点来生成这个包含多边形及其节点坐标的随机数据集。

我从哪里开始？有没有我可以用编程语言实现的算法？顺便说一句：数据应该作为几何图形在 PostgreSQL 数据库中使用。我要使用的语言是 Java.

Answer 1

Tinfour 项目有一个名为 BoundedVoronoiDiagram 的 Java class，它可能对您有用，可以作为想法的来源，请参阅 Tinfour.org。有一个名为 ExampleVoronoi 的示例应用程序，我使用它（稍作修改）从 10 个顶点生成以下图片：

将以下代码添加到演示的末尾会生成多边形及其顶点的列表。该代码将多边形标识为开放（无界）或封闭（有界和有限）：

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

例如：

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

如何生成像 Voronoi diagram/Thiessen 多边形中的多边形并获取每个多边形的节点？

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

java

gis

algorithm

voronoi

polygon