CODEWITHSUNDEEP
arraysgisgeotoolsvoronoijts
bskaggs
bskaggs

Reputation: 1494

How do I build a Voronoi diagram over a grid of points?

I have a two-dimensional array of doubles that implicitly define values on a two-dimensional bounded integer lattice. Separately, I have n 2D seed points (possibly with non-integer coordinates). I'd like to identify each grid point with its closest seed point, and then sum up the values of the grid points identified with each seed point.

What's the most efficient way to do with with JTS/Geotools? I've gotten as far as building a Voronoi diagram with VoronoiDiagramBuilder, but I'm not sure how to efficiently assign all the grid points based on it.

Upvotes: 1

Views: 1445

Answers (1)

Ian Turton
Ian Turton

Reputation: 10976

The best way to do this depends on the size of n and the number of polygons in your voronoi diagram. However basically you need to iterate of one of the sets and find the element in the other set that interacts with it.

So assuming that n is less than the number of polygons, I'd do something like:

// 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 
}

If n is larger than number of polygons - reverse the loops and use within instead of contains to find all the points in each polygon.

Upvotes: 1

Related Questions