<p>Although it's hard to discern a precise question here, evidently it concerns spatial data structures for efficient local searches of objects.  Hanan Samet's books on the subject are classics and almost encyclopedic.  He wrote a brief overview of the subject available <a href="http://www.cs.umd.edu/~hjs/pubs/kim.pdf" rel="nofollow">here</a>.  I suspect a simple <strong>quadtree</strong> would be an attractive solution.  In many cases, exploiting a pre-sorting by one of the coordinates provides fine performance and is simple to code.</p>

CC BY-SA 2.5
2010-12-09T07:48:58.707Z
good reference ! Samet's book is quite comprehensive.
Suresh Venkat
CC BY-SA 2.5
2010-12-09T02:49:35.297Z
2010-12-09T02:49:35.297Z
whuber
<p>It might be useful to store the data in a graph of nodes corresponding to the <a href="http://en.wikipedia.org/wiki/Delaunay_triangulation" rel="nofollow">Delaunay Triangulation</a> of the geometric data points.  Then if you wanted to query an area you could do so by starting with a vertex in your region and then growing a subgraph of the triangulation.</p>

CC BY-SA 2.5
2010-12-08T20:51:25.730Z
2010-12-08T20:51:25.730Z
Andrew D. King
<p>You should check out R-tree indexes: <a href="http://en.wikipedia.org/wiki/R-tree" rel="nofollow">http://en.wikipedia.org/wiki/R-tree</a></p>

<p>There are a number of implementations that are available.  You would probably want to traverse the tree in a custom manner.  Maybe cut the tree at some level and process each subtree in distance from user to bounding box order.</p>

CC BY-SA 2.5
2010-12-08T21:29:14.237Z
2010-12-08T21:29:14.237Z
algoriffic
<p>I was playing with geolocation on maps and stumbled on an interesting problem: 
I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes sense as long as I don't use a combination of paging and map browsing, at which point the dataset no longer makes sense. Since the data on the map will be represented in concentric circles, if a user starts browsing the map needs to zoom out in order to accommodate for changing pages. 
So I thought a better way of sorting data would be by elements' proximity to each other, rather than the user, which is a logical representation of a map I guess (in a geographical sense). But how then given any point on this map can we retrieve an equivalent 1D array that would convey this information?</p>

<p><strong>EDIT:</strong> Thanks for your comments. I think it may be that my problem isn't as theoretical as you answers, it's been a few years since I had to cram for my algorithm exams and I've forgotten a whole lot. I'll to give some details, perhaps that will make it clearer:</p>

<p>In this particular case I am looking at around 350 points on the map, and page of around 10. (I think that makes <em>k</em> in Suresh's comment about 20, because on/after the second page distance from <em>q</em> - in this case position of user's query - is not the only relevant factor)</p>

<p>I had a, possibly a not so smart an idea, which I would like to try to explain with the of a crudely drawn diagram in paint:</p>

<p><a href="https://i.sstatic.net/2Brgb.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2Brgb.png" alt="enter image description here"></a></p>

<p>So diagram <strong>A</strong> is what I have now, where concentric red circles represent paged results as points get further and further away from the centre red dot. I'd like to be able to drag the map, so that paged results get updated with what's currently closest to the centre of the screen (much like Google results) but with current sorting it's impossible without zooming out to accommodate all the points. 
A possible solution is to apply some clustering to get a bunch of probably overlapping areas that represent pages as shown in diagram <strong>B</strong>. That would mean there is some duplication in the returned dataset, but the duplication factor could be tweaked. The green spiral in both diagram indicates roughly increase in distance.</p>

<p>Having said all that, I'm now beginning to think it would be much easier to just use viewport to determine what's currently visible to the user and simply show the results on the page as that. :S</p>

CC BY-SA 2.5
2010-12-08T15:43:47.483Z
I think you want to look at http://en.wikipedia.org/wiki/Nearest_neighbor_search However, I cannot really understand the question.
Radu GRIGore
CC BY-SA 2.5
2010-12-08T15:45:15.713Z
You may want to check the literature on geometric clustering.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-08T16:02:37.407Z
What you probably need is a $k$-NN query where $k$ is appropriately large. In general, if your query result is *all* the points in the table sorted by increasing distance from the query, then that's a lot harder. What would k be in your example ? (i.e how many points would you need to return before the vantage point changes ? )
Suresh Venkat
CC BY-SA 2.5
2010-12-08T17:14:27.223Z
(in response to your edit): I was going to suggest using a kd-tree-like structure, which might respond well to viewport queries, after which you could then do a local sort.
Suresh Venkat
<cg.comp-geom><sorting>
Sorting array of distances by proximity to each other
Shagglez
# Sorting array of distances by proximity to each other

(Asked by: username_0 on 2010-12-08)

I was playing with geolocation on maps and stumbled on an interesting problem:
I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes sense as long as I don't use a combination of paging and map browsing, at which point the dataset no longer makes sense. Since the data on the map will be represented in concentric circles, if a user starts browsing the map needs to zoom out in order to accommodate for changing pages.
So I thought a better way of sorting data would be by elements' proximity to each other, rather than the user, which is a logical representation of a map I guess (in a geographical sense). But how then given any point on this map can we retrieve an equivalent 1D array that would convey this information?

**EDIT:** Thanks for your comments. I think it may be that my problem isn't as theoretical as you answers, it's been a few years since I had to cram for my algorithm exams and I've forgotten a whole lot. I'll to give some details, perhaps that will make it clearer:

In this particular case I am looking at around 350 points on the map, and page of around 10. (I think that makes *k* in Suresh's comment about 20, because on/after the second page distance from *q* - in this case position of user's query - is not the only relevant factor)

I had a, possibly a not so smart an idea, which I would like to try to explain with the of a crudely drawn diagram in paint:

[![enter image description here](https://i.sstatic.net/2Brgb.png)](https://i.sstatic.net/2Brgb.png)

So diagram **A** is what I have now, where concentric red circles represent paged results as points get further and further away from the centre red dot. I'd like to be able to drag the map, so that paged results get updated with what's currently closest to the centre of the screen (much like Google results) but with current sorting it's impossible without zooming out to accommodate all the points.
A possible solution is to apply some clustering to get a bunch of probably overlapping areas that represent pages as shown in diagram **B**. That would mean there is some duplication in the returned dataset, but the duplication factor could be tweaked. The green spiral in both diagram indicates roughly increase in distance.

Having said all that, I'm now beginning to think it would be much easier to just use viewport to determine what's currently visible to the user and simply show the results on the page as that. :S

**Tags:** cg.comp-geom, sorting
> **Comments:**
> **username_1**: I think you want to look at http://en.wikipedia.org/wiki/Nearest_neighbor_search However, I cannot really understand the question.  
> **username_2**: You may want to check the literature on geometric clustering.  
> **username_3**: What you probably need is a $k$-NN query where $k$ is appropriately large. In general, if your query result is *all* the points in the table sorted by increasing distance from the query, then that's a lot harder. What would k be in your example ? (i.e how many points would you need to return before the vantage point changes ? )  
> **username_3**: (in response to your edit): I was going to suggest using a kd-tree-like structure, which might respond well to viewport queries, after which you could then do a local sort.  

---

## 3 answers

### Answer by username_4 on 2010-12-09. Score: 3

Although it's hard to discern a precise question here, evidently it concerns spatial data structures for efficient local searches of objects. Hanan Samet's books on the subject are classics and almost encyclopedic. He wrote a brief overview of the subject available [here](http://www.cs.umd.edu/~hjs/pubs/kim.pdf). I suspect a simple **quadtree** would be an attractive solution. In many cases, exploiting a pre-sorting by one of the coordinates provides fine performance and is simple to code.

> **Comments:**
> **username_3**: good reference ! Samet's book is quite comprehensive.  

---

### Answer by username_5 on 2010-12-08. Score: 1

It might be useful to store the data in a graph of nodes corresponding to the [Delaunay Triangulation](http://en.wikipedia.org/wiki/Delaunay_triangulation) of the geometric data points. Then if you wanted to query an area you could do so by starting with a vertex in your region and then growing a subgraph of the triangulation.


---

### Answer by username_6 on 2010-12-08. Score: 1

You should check out R-tree indexes: <http://en.wikipedia.org/wiki/R-tree>

There are a number of implementations that are available. You would probably want to traverse the tree in a custom manner. Maybe cut the tree at some level and process each subtree in distance from user to bounding box order.


---

