Spatial Indexing - 43

Example Images

Goals

Working with OpenStreet Map Data
Given a map of locations and amenities, to find the closest point or amenity of that type
CS concepts: 2D array addressing, using acceleration structures for efficient search

Description

Given a 2D location, the goal is to find the closest point (or amenity).

You are given a dataset that represents a region of map data, from OpenStreet Map. The data is in the form of a list of locations with Lat/Long values. Your goal is, given a 2D location (X, Y), to find the closest point on the map. Given that the data can contain tens of thousands of locations, you will use a uniform grid to accelerate the search.

Search Algorithm

You want an algorithm that is scalable to very large datasets; hence you will use a data structure to make this process efficient. A uniform grid overlaid on the search area will be used to hold the location data.

A uniform 2D grid of a specified size will be used to store the location data. Each of the location will be inserted into its appropriate 2D cell of the grid and held in a list. Locations within the cell will need to queried linearly.
Once the data is in the search structure, the algorithm starts by locating the cell containing the query point. All points within the cell are queried to compute the distance to the query point and the closest point and distance is retained. Note that the cell may not contain any points.
The algorithm next identifies the cells neighboring the cell containing the query point. Points within these cells are searched for the closest point.
Step 3 can be furhter accelerated by firs determined the orthogonal distance to neighboring cells (to row above and below, columns to the left and right) and only if this distance is smaller the currently stored smallest distance would the correponding cells need to be searched.
As needed, the algorithm proceeds layer by layer starting from the query cell. See the two figures above that illustrates the layers generated (step 3), displayed in a ColorGrid.
If a layer results in no updates to the closest point, then the algorithm can be terminated.

Tasks

Get the OpenStreet map data. The BRIDGES API will be used to obtain this data. Note that the data size has limitations, requiring the bounding box specified to be reduced.
Display the are using BRIDGES (this can be visualized as a graph).
Write a function to identify the cells of a layer. Layer 0 contains the cell of the query point, its immediate neighors (neighbors of the red cell in the above figures) are layer 0, and its neighbors are layer 1, etc.
Given the query point, write functions to compute the distance to the current layer's rows and columns. This will be needed to determine if these cells need to be examined for closer points. Note that the row or column might be outside the bounds of the grid and should be ignored in that case.
Combine steps 3 and 4 into the algorithm and return the closest point and distance.
Verification: Write up a brute force algorithm, i.e., no uniform grid to find the closest point to check to ensure your algorithm's output matches. Depending on the data size, this test might need to be done a smaller dataset.
[Optional:] You may augment your algorithm to display the cells queried by the algorithm by recording the cell indices and display them (colored cells) in a ColorGrid. This is also a good way to verify your layers are being computed correctly (link to 2D assignment).

Extensions

One can make extensions to this assignment:

Instead of just looking at Lat/Long data, you might retrieve a set of resturant locations (say Macdonald's) and look for the closest Macdonalds from your location(home), or the nearest hospital, fire station, etc.