Nearest Neighbour seems to be a hot topic all of a sudden.
I recently added NearestNeighbours functionality to the STRtree in JTS.
Hi,
I did not notice this addition, thanks Martin !
See here for the source code.
http://jts-topo-suite.svn.sourceforge.net/viewvc/jts-topo-suite/trunk/jts/java/src/com/vividsolutions/jts/index/strtree/STRtree.java?view=log
I think the approach I described before can give bad results in some
corner cases, due to the fact that a part of the searching is based on
rectangles (bounding boxes, STRtree nodes) which can give different
results from the strict distance between geometries.
Do you think it is the same for your STRtree based algorithm which seems
partly based on distances between STRtree nodes ?
This will come out in JTS 1.12.0 soon.
I'm monitoring your website to be sure to include it in OpenJUMP as soon
as it is released :-)
This code implements 1-NearestNeighbour - k-Nearest would be an
interesting addition.
I don't have use case for k-Nearest, but I have a somewhat related
matching problem
Find features a from A matching features b from B so that :
a) distance |ab| is alway < max
b) a can match only one feature from B and reciprocally
c1) if |ab| < |ab'|, a matches b, even if b' cannot match any other feature
c2) or matches as many features from A to B (and accept to match a to b'
where |ab'| < max, even if |ab'| > |ab|)
Just gave a quick thought to these problems, but they look like hard to
solve without proper algorithms.
Michaël
On 4/21/2011 7:25 AM, Michaël Michaud wrote:
Hi,
Interesting problem. Last time I had search nearest features around a
feature f, I wrote a script doing the following
1) index the dataset to search with STRtree
2) initiate the search with a small distance d
3) search for features in a bounding box equals to bounding box of f
+ distance d in all directions
if features are found, select the nearest of them (or k nearest)
by a linear search
else set d = 2d and reiterate 3)
Could be implemented as described above in OpenJUMP, but I suspect
there are better algorithms which could take place in JTS itself
See also
http://en.wikipedia.org/wiki/Nearest_neighbor_search
and the interesting discussion started today on JTS list
Michaël
Le 20/04/2011 16:21, Rahkonen Jukka a écrit :
Hi,
I am just thinking what could be cool to have, I do not have any
immediate need right now myself. However, I would say that the
answer in both. I have some ideas about improving the OpenJUMP GPS
extension for making OJ into a nice vector based moving map
program. N nearest items from a point would suit that use case. I
mean queries like Find the closest gas station / restaurant /
streetname / maxspeed limit from my current GPS location etc.
For more serious work with vector data sets, risk analysis and that
sort of things the N items nearest to selected item would probably
be more useful. And of course the selected item can be a point as
well. Your description makes me think that you have a ready tool
for the latter use case. It would be interesting to test it.
-Jukka Rahkonen-
------------------------------------------------------------------------
Larry Becker wrote:
Hi Jukka,
Do you want to find the N items nearest to a point or another
item? I have a tool that looks out a specified distance from a
selected feature and creates a new layer containing lines with
arrowheads between all of the features. It puts the length in
an attribute so you can use it as a label. You can then sort by
the length attribute to get the N nearest.
regards,
Larry B.
On Wed, Apr 20, 2011 at 7:44 AM, Rahkonen Jukka
<jukka.rahko...@mmmtike.fi <mailto:jukka.rahko...@mmmtike.fi>>
wrote:
Hi,
I can find nearest features by having a source layer and
a mask layer and doing a spatial query "is within distance"
by incrementally increasing the distance parameter. It would
be nice to have a tool or script for doing this
automatically. Even better if the number of features to be
found could be given with another parameter and the actual
distance would be written into the attribute table of the
result layer. Has anybody done this yet?
The selection tool "Select Items by Circle from Selected
Layers" might be usable also if it could be done dynamic so
that user could click at the centre point and drag for
giving the radius before OJ performs the query.
I know I can do what I wand with PostGIS and I guess it is
doable in a similar way with Spatialite but sometimes it
would be handy to search nearest features from shapefiles
simply from OJ map window.
-Jukka Rahkonen-
------------------------------------------------------------------------------
Benefiting from Server Virtualization: Beyond Initial Workload
Consolidation -- Increasing the use of server virtualization
is a top
priority.Virtualization can reduce costs, simplify
management, and improve
application availability and disaster protection. Learn more
about boosting
the value of server virtualization.
http://p.sf.net/sfu/vmware-sfdev2dev
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
<mailto:Jump-pilot-devel@lists.sourceforge.net>
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
------------------------------------------------------------------------------
Benefiting from Server Virtualization: Beyond Initial Workload
Consolidation -- Increasing the use of server virtualization is a top
priority.Virtualization can reduce costs, simplify management, and improve
application availability and disaster protection. Learn more about boosting
the value of server virtualization.http://p.sf.net/sfu/vmware-sfdev2dev
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
------------------------------------------------------------------------------
Benefiting from Server Virtualization: Beyond Initial Workload
Consolidation -- Increasing the use of server virtualization is a top
priority.Virtualization can reduce costs, simplify management, and improve
application availability and disaster protection. Learn more about boosting
the value of server virtualization.http://p.sf.net/sfu/vmware-sfdev2dev
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
No virus found in this message.
Checked by AVG - www.avg.com <http://www.avg.com>
Version: 10.0.1209 / Virus Database: 1500/3587 - Release Date: 04/21/11
------------------------------------------------------------------------------
Benefiting from Server Virtualization: Beyond Initial Workload
Consolidation -- Increasing the use of server virtualization is a top
priority.Virtualization can reduce costs, simplify management, and improve
application availability and disaster protection. Learn more about boosting
the value of server virtualization. http://p.sf.net/sfu/vmware-sfdev2dev
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
------------------------------------------------------------------------------
Benefiting from Server Virtualization: Beyond Initial Workload
Consolidation -- Increasing the use of server virtualization is a top
priority.Virtualization can reduce costs, simplify management, and improve
application availability and disaster protection. Learn more about boosting
the value of server virtualization. http://p.sf.net/sfu/vmware-sfdev2dev
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
