Quantcast

LineString gap repair and noding

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

LineString gap repair and noding

Björn Harrtell
Hi,

I'm using JTS to repair collections of 2D LineString geometries that
have gaps. To to this I use the LineStringSnapper class looping
through all lines against all coordinates for all linestrings. At
first I experimented with the snap rounding noders, but afaik their
purpose is not to repair gaps below a certain tolerance as in my case.

LineStringSnapper seem to do what I want but since it seem to be brute
force it is understandably slow with large datasets.

Is there any obvious way to to what I want to get done in a more
effective manner or should I try to improve the LineStringSnapper with
indexing?

Also, since I'm noding the result I have been wondering if should dig
into the noders of JTS instead of using "cascading" unions for
performance reasons?

With regards,

/Björn Harrtell
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: LineString gap repair and noding

Sunburned Surveyor
How do you know that a LineString has a gap, and isn't two (2)
linestrings? Do you consider any two (2) endpoints within a tolerance
a gap, and not an actual separation?

You wrote: "Is there any obvious way to to what I want to get done in a more
effective manner or should I try to improve the LineStringSnapper with
indexing?"

I believe using a spatial index would certainly speed things up. You
only need to compare the coordinates of endpoints very nearby your
subject LineString, not with every LineString in your set of data. JTS
comes with a couple of spatial index implementations you could use.

I'd imagine this would really speed things up, but maybe you are
already using a spatial index and meant something else. If not, check
our this class:

http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/index/quadtree/Quadtree.html

The Sunburned Surveyor

2009/8/31 Björn Harrtell <[hidden email]>:

> Hi,
>
> I'm using JTS to repair collections of 2D LineString geometries that
> have gaps. To to this I use the LineStringSnapper class looping
> through all lines against all coordinates for all linestrings. At
> first I experimented with the snap rounding noders, but afaik their
> purpose is not to repair gaps below a certain tolerance as in my case.
>
> LineStringSnapper seem to do what I want but since it seem to be brute
> force it is understandably slow with large datasets.
>
> Is there any obvious way to to what I want to get done in a more
> effective manner or should I try to improve the LineStringSnapper with
> indexing?
>
> Also, since I'm noding the result I have been wondering if should dig
> into the noders of JTS instead of using "cascading" unions for
> performance reasons?
>
> With regards,
>
> /Björn Harrtell
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: LineString gap repair and noding

Björn Harrtell
With gaps I actually meant between *any* two vertices (not only
endpoints) within a tolerance value in the collection of LineString
processed. Normally the end result is splitted LineStrings (after the
noding).

I did mean a spatial index but I've yet to understand how to use them
in JTS and before delving into them I wanted to know if it would be
worth it - it's quite clear from your explanation that it is. Thanks!

/Björn

2009/9/1 Sunburned Surveyor <[hidden email]>:

> How do you know that a LineString has a gap, and isn't two (2)
> linestrings? Do you consider any two (2) endpoints within a tolerance
> a gap, and not an actual separation?
>
> You wrote: "Is there any obvious way to to what I want to get done in a more
> effective manner or should I try to improve the LineStringSnapper with
> indexing?"
>
> I believe using a spatial index would certainly speed things up. You
> only need to compare the coordinates of endpoints very nearby your
> subject LineString, not with every LineString in your set of data. JTS
> comes with a couple of spatial index implementations you could use.
>
> I'd imagine this would really speed things up, but maybe you are
> already using a spatial index and meant something else. If not, check
> our this class:
>
> http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/index/quadtree/Quadtree.html
>
> The Sunburned Surveyor
>
> 2009/8/31 Björn Harrtell <[hidden email]>:
>> Hi,
>>
>> I'm using JTS to repair collections of 2D LineString geometries that
>> have gaps. To to this I use the LineStringSnapper class looping
>> through all lines against all coordinates for all linestrings. At
>> first I experimented with the snap rounding noders, but afaik their
>> purpose is not to repair gaps below a certain tolerance as in my case.
>>
>> LineStringSnapper seem to do what I want but since it seem to be brute
>> force it is understandably slow with large datasets.
>>
>> Is there any obvious way to to what I want to get done in a more
>> effective manner or should I try to improve the LineStringSnapper with
>> indexing?
>>
>> Also, since I'm noding the result I have been wondering if should dig
>> into the noders of JTS instead of using "cascading" unions for
>> performance reasons?
>>
>> With regards,
>>
>> /Björn Harrtell
>> _______________________________________________
>> jts-devel mailing list
>> [hidden email]
>> http://lists.refractions.net/mailman/listinfo/jts-devel
>>
>
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: LineString gap repair and noding

Martin Davis
In reply to this post by Björn Harrtell
Adding some indexing would probably make an improvement.  
LineStringSnapper was not designed for bulk operations on large sets of
geometries, so it doesn't necessarily take the most efficient approach
in this situation.

Since you'll be modifying the geometries which are in the index, you'll
have to take some care in how you implement this.  You could either
index the geometries with a bounding box which is enlarged by the
maximum tolerance you might modify geometries, or use an updatable index
like Quadtree and replace the geometries when they are modified.

Using a noder rather than a cascaded union would also probably make a
difference.  The cascaded union is likely doing a lot of repeat indexing
and noding, which using a noder directly would avoid.

Since you're dealing with linestrings you have a relatively easy task -
they do not have the same requirements for topological consistency as
would polygons.  So it should be straightforward for you to implement
the above changes.

Martin

Björn Harrtell wrote:

> Hi,
>
> I'm using JTS to repair collections of 2D LineString geometries that
> have gaps. To to this I use the LineStringSnapper class looping
> through all lines against all coordinates for all linestrings. At
> first I experimented with the snap rounding noders, but afaik their
> purpose is not to repair gaps below a certain tolerance as in my case.
>
> LineStringSnapper seem to do what I want but since it seem to be brute
> force it is understandably slow with large datasets.
>
> Is there any obvious way to to what I want to get done in a more
> effective manner or should I try to improve the LineStringSnapper with
> indexing?
>
> Also, since I'm noding the result I have been wondering if should dig
> into the noders of JTS instead of using "cascading" unions for
> performance reasons?
>
> With regards,
>
> /Björn Harrtell
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...