如何在点网格上构建Voronoi图

Question

我有一个双精度的二维数组，它隐式地定义了二维有界整数格上的值。另外，我有n2D种子点（可能具有非整数坐标）。我想用最接近的种子点来识别每个网格点，然后将用每个种子点识别的网格点的值相加。

使用JTS/Geotools最有效的方法是什么？我已经用VoronoiDiagramBuilder构建了一个Voronoi图，但我不确定如何基于它有效地分配所有网格点。

Answer 1

最好的方法取决于n的大小和voronoi图中的多边形数量。然而，基本上你需要迭代其中一个集合，并在另一个集合中找到与之交互的元素

因此，假设n小于多边形的数量，我会做如下操作：

// features is the collection of Voronoi polygons
// Points is the N points
Expression propertyName = filterFactory.property(features.getSchema()
    .getGeometryDescriptor()
    .getName());
for (Point p: points) {
    Filter filter = filterFactory.contains(propertyName,
        filterFactory.literal(p));
    SimpleFeatureCollection sub = features.subCollection(filter);
    //sub now contains your polygon
    //do some processing or save ID 
}

如果n大于多边形的数量-反转循环并使用within而不是包含来查找每个多边形中的所有点。