Voronoi: A solution to proximity based problems

In computational geometry, Voronoi diagram is a partitioning of a plane with n points into n convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. GeoVoronoi is an extension of Voronoi optimized for geo locations.

To dive deeper into Voronoi geometry, read chapter seven of Computational Geometry: Algorithms and Applications. Or maybe play with this cool demo.

If you're working on any proximity-based problem, Voronoi diagram can be a lot of help. In layman's language, Voronoi diagram divides a 2-D plane with n sites into n zones, one for each sites, such that any point inside the zone is nearer to the site that owns the zone as compared to any other sites. In the above Voronoi diagram, 'a' is a site and 'v(a)' is its zone.

In my particular use case, I've been creating a proximity based mobile app that needs to know which site is nearest to the device during each location update. The zone information provided by Voronoi diagram saves me from polling among distances from each site upon each location update. Now I just need to check which zone the device is currently inside of and would poll among the zones only if the device moves out of the current zone. This optimizes the process multiple folds.

I'm extending this Javascript implementation of Voronoi diagram. Although it works perfectly for a normal X-Y plane, it wouldn't quite fit in for geo locations. So, I've written a geo wrapper over it, namely, GeoVoronoi which basically does the following patch-work:

1. Longitudes don't stay linear near the international date line. They discontinue and go like '..., 178, 179, -179, -178,...'. GeoVoronoi would take care of this.
2. Auto-boxing super area of sites with optimal padding. (Bbox in code).
3. Keeping latitude-longitudes sanitized in terms of range and decimal places.

Usage

Input an array of sites(latitude-longitudes) and a voronoi-graph will be returned to you. The information inside voronoi graph can be used to do calculations, to determine zones and even to draw the Voronoi diagram on a plane, Google Map, etc.

I've created an npm package for geovoronoi here. To install this package use the following command:
npm install geovoronoi

Above code will generate voronoi-graph data. This voronoiGraph object contains following three major objects and a key-value for execution time:

1. cells: This contains information for all the polygons(zone) along with their owner sites. A polygon is represented by halfedges (called so as most of them are shared among two adjacent polygons). Each half-edge has start and end vertices called 'va' and 'vb' respectively. Set of start vertices of all half-edges will be all the vertices of the polygon. Information of cells is enough for basic calculations.
2. edges: This contains information about start and end points of all the edges in the resulting Voronoi diagram.
3. vertices: This contains information about all the vertices in the resulting Voronoi diagram.

Please refer to this README for the data inside cells.

If you found this post interesting go explore more about Voronoi. Leave a comment about your use case. You might also want to take a look at my post about Ray casting. It will help in determining whether a point lies inside a polygon or not.

by achin