arrays - 如何在点网格上构建 Voronoi 图？

Question

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

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

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而不是 contains 来查找每个多边形中的所有点。