# Shape matching on road maps

Geogrid is a rust library which approximately quantizes map data into a two-dimensional grid. I suggest such a representation has application for visualization or applying image processing to local geographic data. In my case I developed the library to enable me to match arbitrary shapes against a city’s road map.

Given some input data (for example from GeoJSON), the grid computes the
latitude/longitude boundaries and calculates the size of each grid square by
dividing into the requested grid height/width dimensions. The data structure
stores the bounds along with the resolution in units of meters per row/column
to provide translation between real coordinates and grid coordinates. Since
OpenStreetMap data defines road data as a list of map nodes which should be
connected by line segments, the `from_roads`

grid constructor also marks points
along the slope between consecutive road nodes. A future feature would be to
filter the roads used to optionally exclude types such as railroads and subway
tracks.

Having constructed such a grid, Geoshaper finds closest matches to arbitrary shapes using Chamfer matching. First, I compute the distance transform of the road grid, as illustrated in the following figure.

The distance transform computes at each location the distance to the closest nonzero point (in the grid road pixels are 1 and the rest is 0). Chamfer matching then filters this distance transform with a binary shape mask and finds the minimum point. This minimum point corresponds to the location on the map which minimizes total distance from the provided shape.

The reader may try out some cities in Geoshaper, which packages this algorithm in a web interface that allows shape drawing and results display. While the server is very slow, the code is available on github, and it includes a GPU-accelerated version which shows tremendous speedup with a capable processor.