I'm trying to find a clever/efficient way to calculate the the farthest point from an origin, given a list of lat,lng points.

For example, if trying to find the closest point from an origin I could adapt this function that finds all nearby points:

def getNearby(origin_dict, geo_dict_list, radius_miles):
    # adapted from http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

    # this will create a lat+lng square
    # corners aren't technically correct, but the general idea:

    #    lat_1 ---> lng_1
    #      |          |
    #      |          |
    #      |          |
    #    lat_2 ---> lng_2

    # if geo point is inside our lat+lng square, then do expensive calculation of exact distance
    #   to see if it's inside the radius-circle w/in the square (circle not shown)

    # geo_dict_list = [ {'lat' : 1.234, 'lng' : 5.678}, ... ]

    offset = radius_miles / 69.1
    lat_1 = origin_dict['lat'] - offset
    lat_2 = origin_dict['lat'] + offset

    offset = radius_miles / abs( math.cos( math.radians(origin_dict['lat']) ) * 69.1 )
    lng_1 = origin_dict['lng'] - offset
    lng_2 = origin_dict['lng'] + offset

    return_indexes = []
    for index, geo_dict in enumerate(geo_dict_list):
        if (geo_dict['lat'] >= lat_1) and (geo_dict['lat'] <= lat_2) and (geo_dict['lng'] >= lng_1) and (geo_dict['lng'] <= lng_2):
            if getDistance(origin_dict, geo_dict, units="miles") <= radius_miles:
                return_indexes.append( index )

    return return_indexes

Is there a similar way to approach this for finding the farthest point from origin? Or maybe there's a way to structure the original list in a way that allows one to do some clever sorting?

  • 3
    "Calculate nearest" can use an index, but "calculate farthest" is like a NOT -- I don't see any way to avoid a full table scan, with algorithmic efficiency O(N) or worse . – Vince Jul 10 '15 at 18:43
  • That's what I was thinking; thanks for the confirm. – user2426679 Jul 10 '15 at 18:50
  • 2
    In PostGIS you could make an union of your dataset and a point at the origin and compute minimum bounding circle postgis.net/docs/ST_MinimumBoundingCircle.html. The circle must intersect your point at least if origin is not inside the point cloud. – user30184 Jul 11 '15 at 9:10
  • What is closest to origin is farthest from opposite corner of 'square', providing it is not entire globe you are talking about. – FelixIP Jul 12 '15 at 20:56

What is closest to origin is farthest from opposite corner of 'square', providing it is not entire globe you are talking about.

This has been tested on 10 degrees "square" using 100 random points:

enter image description here

  • Forgive my gis naivety, but how would I calculate the farthest point if the origin is not on one of the corners? Any way you could point me to an outside article or explain this in pseudo-code? – user2426679 Jul 13 '15 at 22:28
  • If it is a case, forget what I said – FelixIP Jul 14 '15 at 4:11
  • How about large offset and using if not (geo_dict['lat'] >= lat_1) ...):. This will select candidates from outside offset box only – FelixIP Jul 14 '15 at 5:22
  • I've considered it, but this would be an imperfect optimization because a point may lie in the space between the true, distance-capturing-circle and the outer box, and this point may be farther than a point on the outside of the box. example: i.imgur.com/XAEJdUq.png – user2426679 Jul 14 '15 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.