HI Elena,
A routing problem; it sounds like the classical travelling salesman problem
(TSP). (This assumption could be wrong)
The TSP is O(c^n), c > 1 [exponential] using dynamic programming or O(n!)
[factorial] using brute force. Unless you have some sort of domain specific
metric to cut through the complexity of the TSP, in your case, an O(n*n) sort
is manageable.
If you are getting results in milliseconds with ‘clean’ data then it sound like
you do have a domain specific metric to solve the TSP quickly. And the O(n*n)
sort is a problem.
But then again the TSP assumption could be wrong and what I have said is a
bunch of tripe!
Brett
From: Frank van der Hulst [mailto:drifter.fr...@gmail.com]
Sent: Wednesday, 3 September 2014 4:31 AM
To: Elena Pop
Cc: geotools geotools-gt2-users@lists. sourceforge. net
Subject: Re: [Geotools-gt2-users] Remove the isolated arcs from a graph
Hi Elena,
I ran into this in my project too.
My solution was to measure the distance from my tree to each of the candidate
LineStrings. Only if the distance is less than a specified threshold would the
new LineString be added. Depending on the quality of the source data, a
threshold of between 20m and 150m worked for me. You need that distance anyway,
because you need to find the nearest point of the tree to the new LineString,
so it will be added in the right place. You could even do a first run through
the data, deleting any LineString which doesn't connect to any other
LineString. But that will be another O(n*n) process.
One thing I did to improve speed (although I am only looking at a few hundred
LineStrings at most) was to sort the list so that (usually) the best candidate
would be found early. Criteria for the sort were things like the length of the
candidate, the distance in the right direction, the distance from the nearest
point on the tree to the destination.
Frank
On Tue, Sep 2, 2014 at 8:58 PM, Elena Pop
<elena0...@gmail.com<mailto:elena0...@gmail.com>> wrote:
I am using a shapefile downloaded from OpenStreetMap in order to calculate a
route between two points. The graph created contains some isolated arcs that
are messing up my routing like these ones http://screencast.com/t/4jnQFx57
Is there any way i can remove them in a fast way, before or after the graph
creation?
The way i am implementing the project is creating a List of linestrings read
from the shapefile and then iterating through the list and adding each
linestring to the graph. I did find a solution but it is not an optimal one
since it takes more than 1 hour to get results.
My solution looks to count the number of occurrences of the first and he last
point of a linestring in the other linestrings and if one of the nOccurrences
is >1 the linestring will get added to the graph.
Basically i will have to iterate twice through the list, but since the list has
more than 70000 linestrings it will do a O(n*n) program which will take forever
and i need to get results in ms not in hours.
Is there other way that i can do this?
------------------------------------------------------------------------------
Slashdot TV.
Video for Nerds. Stuff that matters.
http://tv.slashdot.org/
_______________________________________________
GeoTools-GT2-Users mailing list
GeoTools-GT2-Users@lists.sourceforge.net<mailto:GeoTools-GT2-Users@lists.sourceforge.net>
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
------------------------------------------------------------------------------
Slashdot TV.
Video for Nerds. Stuff that matters.
http://tv.slashdot.org/
_______________________________________________
GeoTools-GT2-Users mailing list
GeoTools-GT2-Users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
