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> 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?
>
>
> <http://screencast.com/t/4jnQFx57>
>
>
> ------------------------------------------------------------------------------
> 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
>
>
------------------------------------------------------------------------------
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
