Package micycle.pgs.commons

Class MultiplicativelyWeightedVoronoi

java.lang.Object
micycle.pgs.commons.MultiplicativelyWeightedVoronoi
public class MultiplicativelyWeightedVoronoi extends Object
Multiplicatively Weighted Voronoi Diagrams

MWVDs are a generalisation of Voronoi diagrams where each site has a weight associated with it. These weights influence the boundaries between cells in the diagram. Instead of being equidistant from generator points, the boundaries are defined by the ratio of distances to the weighted generator points. This results in characteristically curved cell boundaries, unlike the straight line boundaries seen in standard Voronoi diagrams.

For two sites a,b the region of a's "dominance" over b is defined as the Apollonius circle made from a,b. This circle's perimeter represents the set of all points where the ratio of distances to a and b is equal to the ratio of their weights. The MWV cell for a site is then formed by the geometric intersection of all the Apollonius circles it forms with every other site in the diagram. In other words, it is the region where that site "dominates" (in terms of distance-weighting) all other sites.

The intersection of Apollonius circles provides a very good approximation to the geometrically "true" MWVD; this approach is considerably simpler both conceptually and in implementation than alternative approaches such as wavefront propagation.

Author:
Michael Carleton

  • Method Details

    • getMWVFromPVectors

      public static List<org.locationtech.jts.geom.Geometry> getMWVFromPVectors(List<processing.core.PVector> vectors, double[] bounds)
      Computes Multiplicatively Weighted Voronoi (MWV) diagram from a list of weighted points.
      Parameters:
      vectors - List of PVectors where: x, y are coordinates of the site, and z is the weight.
      bounds - [minX, minY, maxX, maxY] array defining the rectangular extent. for the voronoi diagram. This should enclose all points.
      Returns:
      List of Polygons representing MWV regions.