0

tl;dr: "Am I, with any given location, inside of any number of circles with varying radii"

Assume you have a database full of locations (coordinates) with arbitrary radii. Now the user enters and provides the backend with their current location.

How would the backend efficiently figure out which locations to return?

I'm having a hard time wrapping my head around this and all my googling turns up is the opposite of this (the user location provides the radius and we search for any items in the user circle).

What am I not thinking of? Do I need more coffee?

  • did you consider approximating circles with squares of similar size? do your precision requirements allow such an approximation? – gnat Jun 29 '16 at 14:39
  • I could use squares (precision isn't too critical) but I'm still not sure how I would go about doing that. I think I'm missing something conceptual – pmilla1606 Jun 29 '16 at 14:48
  • squares simplify proximity estimation. Instead of euclidean distance formula, you could use simpler one which subtracts coordinates – gnat Jun 29 '16 at 14:50
  • Does your database have geospatial functions? – Tulains Córdova Jun 29 '16 at 15:52
1

More coffee is always good!

As was suggested, there's almost certainly a geospatial extension for your database, but that may be overkill for what you want. I would base it on squares, rather than circles, and then later refine the selection.

  1. The 'proper' method

    SELECT * FROM LOCATIONS WHERE ?1 >= X - RADIUS AND ?1 <= X + RADIUS AND ?1 >= Y - RADIUS AND ?1 <= Y + RADIUS
    
  2. Manhattan distance

    SELECT * FROM LOCATIONS WHERE ABS(?1 - X) + ABS(?2 - Y) <= RADIUS*1.5
    

    The 1.5 (or rather, sqrt(2)) is because this distance is always greater than (or equal to) the true distance.

  3. Store the bounding rectangle rather than the location and radius?

    SELECT * FROM LOCATIONS WHERE ?1 >= X_MIN AND ?1 <= X_MAX AND ?2 >= Y_MIN AND ?2 <= Y_MAX
    

    As an added bonus, you could probably create an index on (X_MIN, X_MAX, Y_MIN, Y_MAX) and speed things up.

  4. Create a view for the bounding rectangle if you want to keep location/radius as it is.

  5. Probably lots of other things one can do...

  • "As an added bonus, you could probably create an index on (X_MIN, X_MAX, Y_MIN, Y_MAX) and speed things up." I think this is the key - instead of querying everything in the database, query only (X < MAX_RADIUS) – pmilla1606 Jun 29 '16 at 16:25
  • Combine two of the approaches - query by bounding box to get an initial candidate set, then do the radius intersection only on the results of the faster query. That's what (good) implementations of geographic databases do for queries like SELECT * FROM locations WHERE ST_Contains(geom,ST_Point(X,Y)). – Toby Speight Jun 29 '16 at 16:44

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.