# Efficiently Calculating Farthest Point from Origin

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):

# 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}, ... ]

lat_1 = origin_dict['lat'] - offset
lat_2 = origin_dict['lat'] + offset

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?

• "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
• 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 