Making a small Website and an Android app for finding the nearest point to a list of points.
The idea was simple : finding the best point in a map for n peoples to meet, called the barycenter there.
I first made the mean of the sum of latitudes and longitudes, but that was obviously not the good solution (the distance between 2 longitudes depends on the latitude,...). So later I used the Great Circle distance (I could use the Vincenty's formula but that's a little bit overkill).
The mean of the sum of latitudes and longitudes that was enough to use as test for the distance in a small app, so I discovered the google map api platform and usage of the Maps in Android.
I developped a technique that throw a lot of points in the map, check the best found and then throw a list of point in a smaller area around it (kinda like a genetic algorithm, but only the best of each generation is kept (if the "cost" have only one local minimum and is continuous that's not a problem) and the mutations reduce over time).
That find the point with the smallest value for the equation of the distance to all the input points.
Another goal was added, the point should be in the lands.
I had some difficulties to make a 3 color gradient, having fun results.
But I finally made the program working and made with a little editing to add the map this graphic :
- From blue to red the cost increasing
- In green to dark purple the points that search the barycenter in a smaller area at each operation
- In pink the points in lands searched in an area increasing from the barycenter previously found
To target more devices I also decided to switch to a Website.
Now I work on theses things :
- Finding a way to reduce lands file size from this land and water area dataset (actually 4Mo file for ~5km precision is used)
- Finding the "Travel Barycenter", the destination that make all people use the less time in car transport to meet, using distance matrix apis (Actually working, but improvements are needed to reduce and optimize api calls, and to show all the routes and the times on the map too)
- Prove and fine tuning the algorithm
- Use OpenLayers to avoid usage of proprietary google apis
- Make travels easily sharable and time aware