If a picture is uploaded within a certain radius of a previously uploaded pic, retrieve category suggestions from cache to prevent making redundant calls to the MediaWiki API. A 3rd party library is likely to be required for this task. Library that we plan on using: https://github.com/varunpant/Quadtree , which is the Java implementation of a Quadtree.
Having gone through the QuadTree documentation and associated articles about quadtrees, my impression of how I would go about this task is:
- Construct a QuadTree
public QuadTree(double minX, double minY, double maxX, double maxY)
with min/max values according to
http://stackoverflow.com/questions/15965166/what-is-the-maximum-length-of-latitude-and-longitude
- Latitude : max/min +90 to -90
- Longitude : max/min +180 to -180
Where longitude = X and latitude = Y.
- For each picture uploaded that has GPS coordinates, set a point in that QuadTree using the method
public void set(double x, double y, Object value)
The Object value is the List of categories that were previously found for that picture.
- For each picture uploaded that has GPS coordinates, also
public Point[] searchWithin(final double xmin, final double ymin, final double xmax, final double ymax)
searchWithin(x-50, y-50, , x+50, y+50) of new point to see if there are any old points within that area. I will need to convert distance in metres to difference in decimal degrees for this. As accuracy is not that important for this task, I will convert using the formula at http://gis.stackexchange.com/questions/2951/algorithm-for-offsetting-a-latitude-longitude-by-some-amount-of-meters . It states that
111,111 meters (111.111 km) in the y direction is 1 degree (of latitude) and 111,111 * cos(latitude) meters in the x direction is 1 degree (of longitude).
Edit 7/1/16: Code for this task complete, pull request submitted.