Finding the AP closest to a point

Talk about whatever

3 posts • Page 1 of 1

Postby siritinga » Sat Sep 07, 2013 3:45 pm

Hi all!

I was thinking about a query that Wigle doesn't support (yet). I'm not really asking to support it, I'm just wondering how it could be done.

The problem is as follows: given a coordinate P (as Lat/long), find the closest N AP to that point.

Obviously, you cannot compute the distance to every AP in the database and return the closest N.

I suppose that currently the lat/long of each AP is indexed, because you can query all the AP inside a Lat/long box, so I wonder if an algorithm like this may work:

- Create a small Lat/long box around the requested point P.
- Get all AP in the box. If there are zero, increase the box and ask again. If there are too many, decrease the box and ask again.
- Once a set of AP is obtained, compute the distance to them and sort them by distance.
- Increase the box, by an amount enough to cover the bounding circle around the first box, that is, compute the bounding box of the bounding circle of the first box. All this in Lat/long coordinates, that would increase the complexity.
- Get the AP in the new box, and compute the distance to them, and sort them by distance, together with the AP in the first box, but it is important to remember from which box they came (the first or the second).
- If the N closest points are all from box1, then we have finished and they are the requested points. If some of them are from box2, then we need to repeat the process of finding a box3 and getting the APs, until all N closest points come from any of the boxes except the last one.

May be this is unnecessary complicated and there are better ways to compute it.

What do you think?

Thanks!

Best regards.

Postby uhtu » Sat Sep 07, 2013 10:09 pm

could store the data in polar coordinates, re-translate the coordinates from P(polar) and just go off of the n-smallest radii.
it probably depends on what one would be optimising for (do you care about absolute accuracy, memory use, or speed of query results?)

if one was to keep it in cartesian lat/lon terms, i'd say:
overselect and then filter, rather than trying to cleverly expand the quantized search area.
Thanks for your answer.

I was thinking in smallest radii, and lat/long are already in polar. In any case, it is still too slow to apply to a huge database like Wigle's.

The adaptive boxing idea was to quickly find APs in any region, both populated cities and deserts.

I suppose that the best idea is just to implement it and see what happens, with a synthetic database...

Regards!

3 posts • Page 1 of 1

Return to “General Grabbag”

Who is online

Users browsing this forum: Google [Bot] and 15 guests