Voronoi Diagram of Google Map Places

June 4, 2018

3 min read

Voronoi Diagram of Google Map Places

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:

  1. Select a city.

    select a city
    select a city

  2. Select the type of place.

    select a place
    select a place

  3. Waiting for the construction of the Voronoi diagram.

    construction
    construction

  4. Observe the Voronoi diagram

    observe
    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>
)
view raw city-input.js hosted with ❤ by GitHub

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]] })))
}
}
view raw select-city.js hosted with ❤ by GitHub

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:

  1. Split the bounding box of the city into rectangles with an area of less than the magic number.
  2. 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())
}
}
view raw voronoi.js hosted with ❤ by GitHub

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>
)
}
view raw map.js hosted with ❤ by GitHub