What it amounts to, is to check which latitudes and longtitudes are inside a given box.
Is there a good dep that does this for you? Not that I know of right now.
However, building this yourself should be rather straightforward:
The algorithm to compare two-dimensional (or even n-dimensional) is very widely used and quite simple to understand. In most cases, using PostGIS is not required (depending on how much data you have; it probably has the same algorithms but with an implementation that compiles to bare metal).
You have a circle (cx, cy, cr
) and a list of points (each with a px, py
). You can check for each of these points in O(n) (linear time) if they are in the circle using the squared euclidean distance: ((cx - px)² + (cy - py)² < cr²
)
First thing to note here is that we donât perform a square root each time, which greatly improves the speed of the algorithm (weâre only interested in if it is inside the radius, not what the actual distance is). Obviously, cr²
can be precomputed outside of the iteration.
However, it can be further sped up (by a constant factor) by comparing each point with a bounding box instead of a bounding circle, since the algorithm then becomes:
bx1 = cx - cr
bx2 = cr + cr
by1 = cy - cr
by2 = cy + cr
for each point:
px > bx1 && px < bx2
&& py > by1 && py < by2
After checking if it is inside the box, you can still filter on only the things inside the circle (But for many implementations, it is actually not a problem if locations inside a box instead of a circle are picked and then you can leave this extra step of complexity out).
If you donât have that much data, youâre now done.
If you do have much data, you can go one step further and store your points in a so-called Quadtree or K-d tree. This is what e.g. PostGIS also uses internally. These trees allow you to find all close points in O(log n) (logarithmic time).