Why Voronoi Diagram
А 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. Once I was wondering how a Voronoi diagram could be useful to service businesses. Is it possible to use the visualization to find a place for a service that won't be cluttered by competitors? In this post, we'll see how to make an application that makes the first step to solve this task by allowing us to have a Voronoi diagram for the specific type of place in the city.
Application
User interactions in the application will consist of a few simple steps:
-
Select a city.
select a city -
Select the type of place.
select a place -
Waiting for the construction of the Voronoi diagram.
construction -
Observe the Voronoi diagram
observe
As a starter for this, we will use a modified version of create-react-app starter, as a components library — material-ui.
Select a Place
There is a lot of libraries that serve as a wrapper around google places API. I decided to use react-places-autocomplete. With the help of this library component to search city:
| ({ changeCityInputValue, cityInputValue, selectCity, city }) => ( | |
| <PlacesAutocomplete | |
| highlightFirstSuggestion | |
| value={cityInputValue} | |
| onChange={changeCityInputValue} | |
| onSelect={selectCity} | |
| searchOptions={{ types: ['(cities)']}} | |
| onError={() => changeCityInputValue('')} | |
| > | |
| {({ getInputProps, suggestions, getSuggestionItemProps, loading, ...rest }) => ( | |
| <Paper style={inputContainerStyle}> | |
| <TextField | |
| {...getInputProps({ | |
| placeholder: 'Search City ...', | |
| })} | |
| /> | |
| <List> | |
| {suggestions.map((suggestion) => ( | |
| <ListItem {...getSuggestionItemProps(suggestion)} key={suggestion.description} button> | |
| <ListItemText primary={suggestion.description}/> | |
| </ListItem> | |
| ))} | |
| </List> | |
| </Paper> | |
| )} | |
| </PlacesAutocomplete> | |
| ) |
Once a user selects a city, we execute a saga that will search for boundaries of the city. Since Google maps don’t have an API that will give you boundaries of the city, we will use open street maps service — Nominatim. Response from this service is an array of places. If the city inside of it, we move to the next part.
| export function* selectCity({ payload }) { | |
| const url = `https://nominatim.openstreetmap.org/search/${encodeURIComponent(payload)}?format=json&polygon_geojson=1&type=city` | |
| const places = yield call(get, url) | |
| const city = places.find(p => (p.type === 'city' || p.class === 'boundary') && ['MultiPolygon', 'Polygon'].includes(p.geojson.type)) | |
| if (!city) { | |
| yield put(toggleSnackbar('fail to find the boundaries')) | |
| yield put(startSearchingNewCity()) | |
| } else { | |
| const [minLng, maxLng, minLat, maxLat] = city.boundingbox.map(Number) | |
| yield put(receiveCity(({ ...city, boundingbox: [[minLat, minLng], [maxLat, maxLng]] }))) | |
| } | |
| } |
Voronoi Algorithm
After the user has chosen the type of place he is interested in - our task is to get all locations 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 us all the places of a particular type in the requested area. The API has a limit of giving 60 locations maximum in a response. We could use the magic number — 60000000 square meters(the maximum area to ask for).
The algorithm looks this way:
- Split the bounding box of the city into rectangles with an area of less than the magic number.
- Until there are no rectangles for investigation left, we keep making requests to the API. If you receive 60 places — high probability, there are more places of a specific type in the requested area. In such a case, you need to split the initial rectangle and put halves of it with other not investigated ones.
| const MAX_NUMBER_OF_PLACES = 60 | |
| const MAX_AREA_FOR_SEARCH = 60000000 | |
| const split = rectangle => { | |
| const firstDistance = turf.distance(...rectangle.slice(0, 2)) | |
| const secondDistance = turf.distance(...rectangle.slice(1, 3)) | |
| if (firstDistance > secondDistance) { | |
| const firstCenter = turf.midpoint(...rectangle.slice(0, 2)).geometry.coordinates | |
| const secondCenter = turf.midpoint(...rectangle.slice(2)).geometry.coordinates | |
| return [ | |
| [...rectangle[0], ...secondCenter ], | |
| [...firstCenter, ...rectangle[2]] | |
| ] | |
| } else { | |
| const firstCenter = turf.midpoint(...rectangle.slice(1, 3)).geometry.coordinates | |
| const secondCenter = turf.midpoint(rectangle[3], rectangle[0]).geometry.coordinates | |
| return [ | |
| [...rectangle[0], ...firstCenter ], | |
| [...secondCenter, ...rectangle[2]] | |
| ] | |
| } | |
| } | |
| export function* selectPlace({ payload }) { | |
| const { voronoi: { hiddenGoogleMap, cityBoundingBox }} = yield select() | |
| let researchedRects = [] | |
| let unresearchedRects = [cityBoundingBox.flatten_()] | |
| try { | |
| while(unresearchedRects.length) { | |
| const rect = unresearchedRects[0] | |
| unresearchedRects = unresearchedRects.slice(1) | |
| const bboxPolygon = turf.bboxPolygon(rect).geometry.coordinates[0].slice(0, 4) | |
| const area = turf.area(turf.bboxPolygon(rect)) | |
| if (area > MAX_AREA_FOR_SEARCH) { | |
| unresearchedRects = [ | |
| ...unresearchedRects, | |
| ...split(bboxPolygon) | |
| ] | |
| continue | |
| } | |
| const [minLat, minLng, maxLat, maxLng] = rect | |
| const request = { | |
| bounds: new google.maps.LatLngBounds( | |
| new google.maps.LatLng(minLng, minLat), | |
| new google.maps.LatLng(maxLng, maxLat), | |
| ), | |
| type: payload, | |
| } | |
| const service = new google.maps.places.PlacesService(hiddenGoogleMap) | |
| let placesReceived = false | |
| let rectPlaces = [] | |
| service.nearbySearch(request, (results, status, pagination) => { | |
| rectPlaces = [...rectPlaces, ...results] | |
| if(pagination.hasNextPage) { | |
| pagination.nextPage() | |
| } else { | |
| placesReceived = true | |
| } | |
| }) | |
| while(!placesReceived) { | |
| const { voronoi: { stage } } = yield select() | |
| if (stage !== STAGES.VORONOI) return | |
| yield call(delay, 500) | |
| } | |
| if (rectPlaces.length !== MAX_NUMBER_OF_PLACES) { | |
| const points = rectPlaces.map(p => new Point(p.geometry.location.lng(), p.geometry.location.lat())) | |
| const contour = new Contour(bboxPolygon.map(([ x, y ]) => new Point(x, y))) | |
| researchedRects = [...researchedRects, { | |
| contour, | |
| places: points, | |
| polygons: getPolygons(rect, points) | |
| }] | |
| yield put(updateResearchedRectangles(researchedRects)) | |
| } | |
| else { | |
| unresearchedRects = [ | |
| ...unresearchedRects, | |
| ...split(bboxPolygon) | |
| ] | |
| } | |
| } | |
| const bboxPolygon = turf.bboxPolygon(cityBoundingBox.flatten_()).geometry.coordinates[0].slice(0, 4) | |
| const contour = new Contour(bboxPolygon.map(([ x, y ]) => new Point(x, y))) | |
| const places = researchedRects.take_('places').flatten_() | |
| yield put(updateResearchedRectangles([{ | |
| contour, | |
| places, | |
| polygons: getPolygons(cityBoundingBox.flatten_(), places) | |
| }])) | |
| } catch(err) { | |
| yield put(toggleSnackbar('fail to build voronoi diagram')) | |
| yield put(startSearchingNewPlace()) | |
| } | |
| } |
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 the Voronoi diagram for the entire bounding box. To render the diagram upon the map, we will use the SVG layer of react-map-gl library.
| ... | |
| render() { | |
| const { | |
| pageWidth, | |
| pageHeight, | |
| zoom, | |
| latitude, | |
| longitude, | |
| updateMap, | |
| updateProjections, | |
| cityGeoJson, | |
| inFly | |
| } = this.props | |
| const mapProps = { | |
| ...MAP_OPTIONS, | |
| width: pageWidth, | |
| height: pageHeight, | |
| zoom, | |
| latitude, | |
| longitude, | |
| onViewportChange: updateMap | |
| } | |
| return ( | |
| <ReactMapGL {...mapProps} ref="reactMap"> | |
| {cityGeoJson && !inFly && | |
| <SVGOverlay | |
| redraw={this.redraw} | |
| updateProjections={updateProjections} | |
| /> | |
| } | |
| </ReactMapGL> | |
| ) | |
| } | |
| ... | |
| redraw = ({ project, unproject }) => { | |
| ... | |
| return ( | |
| <g> | |
| { | |
| rects.map(({ points }, index) => ( | |
| <Rectangle key={'rectangle' + index} points={points}/> | |
| )) | |
| } | |
| { | |
| cells.map(({ points }, index) => ( | |
| <Cell key={'cell' + index} points={points} /> | |
| )) | |
| } | |
| { | |
| specialCell && <SpecialCell key={'specialCell'} points={specialCell.points}/> | |
| } | |
| { | |
| places.map(({ x, y }, index) => ( | |
| <Place key={'place' + index} x={x} y={y} /> | |
| )) | |
| } | |
| { | |
| contoursPoints.map((points, index) => ( | |
| <Contour | |
| key={'contour' + index} | |
| points={points} | |
| /> | |
| )) | |
| } | |
| </g> | |
| ) | |
| } |