3
$\begingroup$

let's say that I have:

  • M - Main point - given by coordinates (lat, long)
  • C - Collection of points - also given by coordinates (lat, long)
  • R - Radius - maximum search distance

I'm trying to find all points that are within a radius from main point (neighbors). algorithm(main_point, collection_of_points, radius) --> neighbors

Obvious solution is to calculate distances and select those points, where distance is equal or smaller than R, but I believe there are better options with better performance.

Do you know any possible solutions? I'm open for every idea (not only the best one).

EDIT:

I should add that I'm looking for solution where points are strongly dynamic (every point is mobile phone or car). I'd like to update point when it's neccessary (it has been moved) so frequency of updates depends on amount of connected devices (so as queries). Let's say that server will get update request every 5 second and query request every 20 second.

Visualisation

Visualisation

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This is a well-explored topic. What research have you done? $\endgroup$
    – Raphael
    Commented Oct 14, 2016 at 10:38
  • $\begingroup$ @Raphael, I've found a lot of information about R-trees, but it seems overly complicated for my problem (but of course I'm going to read more about them). I like idea of GeoHash (for example Redis database is using it), but this solution has few edge cases. I've asked here, because there is maybe some good solution, that I don't know. $\endgroup$
    – pfff
    Commented Oct 14, 2016 at 10:55
  • $\begingroup$ Define "overly complicated". In general, you will have to trade off different cost measures. $\endgroup$
    – Raphael
    Commented Oct 14, 2016 at 12:08
  • $\begingroup$ @Raphael If I understood correctly the idea of R-trees, every insertion action depends on state of tree, so (my data are dynamic) every change will result in the need to rebuild the tree. I don't know if it's a good idea in my situation. $\endgroup$
    – pfff
    Commented Oct 16, 2016 at 14:29

3 Answers 3

Reset to default
2
$\begingroup$

You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that allows for quick lookup times. Then you don't have to calculate the distances to all points to see which are too far away, you can restrict your search to points in the same (or adjacent) boxes.

But note that the naive approach is actually pretty good in this case, even if it's asymptotically not optimal. CPUs are really good at summing squares and it's trivial to throw more cores at the problem if you need more speed. So unless you're dealing with many points, it will be hard to beat.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Is it good idea to use such a structure when points are dynamic? Let's say that every point represents mobile phone or car. $\endgroup$
    – pfff
    Commented Oct 14, 2016 at 11:55
  • $\begingroup$ @pfff Depends on the ratio of updates and queries, obviously. If you can make any assumptions on that, please add them to the question. That said, in a mobile setting you are unlikely to use global information, anyway; just rely on transmission range limits and find close nodes locally. $\endgroup$
    – Raphael
    Commented Oct 14, 2016 at 12:09
  • $\begingroup$ @pfff If your points are reasonably uniformly distributed you can go with a very simple grid instead of a tree structure. $\endgroup$
    – adrianN
    Commented Oct 14, 2016 at 12:19
  • $\begingroup$ @Raphael, > If you can make any assumptions on that, please add them to the question. Added. > just rely on transmission range limits and find close nodes locally. Can you elaborate? > you can go with a very simple grid instead of a tree structure So this solution will be similar to GeoHash, right? $\endgroup$
    – pfff
    Commented Oct 14, 2016 at 12:56
  • $\begingroup$ @pfff Connect every node with all others it can reach. Simple. Depends on what your semantics of "close" is, of course. $\endgroup$
    – Raphael
    Commented Oct 14, 2016 at 13:47
1
$\begingroup$

Depending on your practical situation, once you have examined all the points you might not just determine if they are within the radius, but how long it would at least take for them to either leave or enter the radius. Then you only re-examine a point after that time interval has gone by, and classify it again.

For example, if the radius is 1km, and a car is 2km away, you might figure out that it would take 41 seconds to enter the radius (while not exceeding the speed limit excessively), so if you check every five seconds, you check that car after 45 seconds.

Improve this answer
$\endgroup$
-2
$\begingroup$

https://en.wikipedia.org/wiki/Spatial_database#Spatial_index

This link describes most popular ways to index spacial data.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Links change or break; please make your answer self-contained. $\endgroup$
    – Raphael
    Commented Oct 14, 2016 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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