Directions/Routing Algorithm

[dgetu]

Utilize the Google Maps Directions API to determine an optimal path.
First pass at the pathfinding algorithm:

1. Define a cost algorithm for a path

• This includes the length of the path and the concentration of crime along the path.
• Define the crime density function [(lat, long) -> intensity] to be the sum of Gaussian curves centered on each crime datapoint

2. Generate a polyline which approximates a safe path

• Limit pathfinding algorithm to the circle which includes the starting and ending points on the diameter. This limits the path to pi times as long as the direct path (approximately)

3. Determine the cost of the polyline

• Weighted sum of the length of the polyline and line integral of the crime density function
• Weights of the sum are partially set in advance for good performance, but can be adjusted based on the user's tolerance for risk of crime

4. Minimize the cost

• Hill climbing/gradient descent algorithm

5. Pass the optimal polyline in encoded polyline form to the Directions API
6. Test the result for sufficiently low cost
7. Pass the result to the client