I work on spatial indexing and can suggest an idea. (I don’t know enough about
GeoTools to know whether it provides a solution.)
I work on z-order based spatial indexes. Suppose you have a space with integer
coordinates, a set of points, (x, y), and you want to find the k points nearest
to a given point (x0, y0). This can be done using a z-order index as follows:
1. For each point, (x, y), compute the z-value, z, by interleaving the bits of
x and y.
2. Load the (z, x, y) data into an ordered index, an in-memory sorted array if
possible, or a b-tree on disk for a large data set.
3. Compute the z-value of your query point, z0, by interleaving the bits of x0
and y0.
4. Do a random access into your index (from step 2), using z0, and find the k
nearest records by z. These will all be adjacent in the index.
5. For each retrieved (z, x, y) record, compute the distance from (x, y) to
(x0, y0). The maximum of these distances is an upper bound on the radius in
which the k nearest neighbors to (x0, y0) can be found.
6. Search the spatial index using a circle of this max radius, centered at (x0,
y0).
7. Sort by distance and keep the top k.
You can use the index from step 2 for each point in your second data set.
(I think this algorithm is by David Abel, but I don't have the reference handy.)
The generalization to finding the k nearest non-point neighbors is pretty easy.
I have a few open source packages implementing z-order spatial indexes:
- Java: https://github.com/geophile/geophile
- C++: https://github.com/geophile/geophile.c
- SQL: https://github.com/geophile/spacesuit
These don't have k nearest neighbors built in, but it would be a simple
addition.
Jack Orenstein
On Jul 17, 2014, at 8:27 AM, Brett Antonides <brett.antoni...@lmnsolutions.com>
wrote:
> Hi All,
>
> I've been looking through the GeoTools documentation and search, but haven't
> been able to find much on a k-NearestNeighbor algorithm. I'm really hoping
> someone can point me in the right direction.
>
> What I need to do is find the k nearest features in a feature collection to a
> point. For instance, find the 5 closest features in a shapefile to a single
> point. Even better would be a way to find the 5 closest features in a
> shapefile to each point in a different shapefile. Is there anything in
> GeoTools that can help do this? It would need to work Point-Point,
> Point-Line, and Point-Polygon. I'm hoping there is something already and
> that it leverages a spatial index to make the query faster since I have to
> run this operation a large number of times.
>
> Thanks very much for you help! Hope all is well.
>
> Cheers,
> Brett
>
> Sorry if this got posted twice
>
>
> Brett Antonides
> 703-673-9526 ext 760
> ------------------------------------------------------------------------------
> Want fast and easy access to all the code in your enterprise? Index and
> search up to 200,000 lines of code with a free copy of Black Duck
> Code Sight - the same software that powers the world's largest code
> search on Ohloh, the Black Duck Open Hub! Try it now.
> http://p.sf.net/sfu/bds_______________________________________________
> GeoTools-GT2-Users mailing list
> GeoTools-GT2-Users@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
------------------------------------------------------------------------------
Want fast and easy access to all the code in your enterprise? Index and
search up to 200,000 lines of code with a free copy of Black Duck
Code Sight - the same software that powers the world's largest code
search on Ohloh, the Black Duck Open Hub! Try it now.
http://p.sf.net/sfu/bds
_______________________________________________
GeoTools-GT2-Users mailing list
GeoTools-GT2-Users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
