А Voronoi diagram is an expressive tool to show how a plane can be optimally distributed between a set of points. It has applications in a large number of fields, such as natural sciences, health, engineering, geometry, civics, and informatics. One time I was interested in how a Voronoi diagram can be useful for service businesses to find a not so cluttered with competitors place in the city. Examples of such services can be gyms, gas stations, car washes or beauty salons. In this article, you will see how I made an application that makes the first step to solve this task by giving you an opportunity to have a Voronoi diagram for the specific type of place in the city.
User interactions in the application consist of a few simple steps:
- Select a city
2. Select the type of place
3. Waiting for the construction of the Voronoi diagram
4. Observe the Voronoi diagram
As a starter for this app used a modified version of create-react-app starter, as a components library — material-ui. At the end of the post, you will find links to the articles about which steps I make after running the create-react-app command.
Select a place
There is a lot of libraries which serves as a wrapper around google places API. I decided to use react-places-autocomplete. With the help of this library component to search city:
After the user has chosen the city saga for searching boundaries of the city will be executed. Since Google maps don’t have API which will give you boundaries of the city I decided to use open street maps service — Nominatim. Saga receives city name selected by a user and sends it in a request to Nominatim service. Response from this service it is an array of places. If the city inside of it we move to the next part.
After the user has chosen the type of place he interested in our task is to get all places of this type bounded by the bounding box of the city. And this is the trickiest part of the app since Google API won’t give you all the places of a particular type in the requested area. API has a limit of giving 60 places maximum in a response. I found the magic number — 60000000 square meters(maximum area to ask for).
The algorithm looks this way:
- Split bounding box of the city into rectangles with an area of less than the magic number.
- Until there are no rectangles for investigation left, make a request to API. If you receive exactly 60 places — high probability there are more places of a specific type in the requested area. In such case, you need to split the initial rectangle and put halves of it with other not investigated ones.
After we examined the rectangle it will appear on the map. When there are no rectangles for investigation left — it is time to merge results and build Voronoi diagram for the entire bounding box. To render the diagram upon the map, I use the SVG layer of react-map-gl lib.
I didn’t go into details so if you want to find the implementation of the specific part you can find them in the repository. Also, I will be glad to see in comments suggestions about in what direction this app can go.
Reach the next level of focus and productivity with increaser.org.