Cleaning up a very messy linear collection

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

Cleaning up a very messy linear collection

aaime
Administrator
Hi,
say I have a very messy MultiLinestring, made basically of straight
segments, most of which end up where the next start, some defining
alterative paths (yes, it's another bus route), some simply almost
overlapping with other in the same set (with sub meter differences,
in which I'm not really interested).
I would like to get a clean linework out of that... the line merger
does not help due to all the overlaps. I was thinking probably the
easiest way is to draw a very small buffer and then grab the
skeleton of the polygon as the cleaned up linework but... I have
no idea of how to do the latter

Any smart suggestion?
Cheers
Andrea

--
Andrea Aime
OpenGeo - http://opengeo.org
Expert service straight from the developers.
_______________________________________________
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: Cleaning up a very messy linear collection

Larry Becker
HI Andrea,

  First you would need to get your very thin buffer to build, which is by no means easy for large complex MultiLinestrings.   It will probably be very slow and require tons of memory unless you use Martin's latest buffer code, and perhaps you might need to get his experimental incremental union buffer code too.  Make sure you don't specify a round end cap.  After you get the buffer, then conventional wisdom says you would need some skeletization code.  I have been searching for code that will do this myself with no luck.  I have an algorithm that finds road centerlines and works in some special cases, but nothing general.  Conceptually, it sounds fairly simple to derive the centerline of a buffer since it is of fixed width.  You could just walk around the edge of the buffer, saving offset lines.  This would capture the route, but would have gaps at the branching points unless you extended them to the intersection.

  I'm not really sure what your final goal is.  Are you looking for a topological noded list of linestrings (i.e. a conventional road network) that you can use to compute routes with, or are you looking for one complete linestring that represents the path of the bus?

regards,
Larry Becker

On Mon, Nov 3, 2008 at 5:49 AM, Andrea Aime <[hidden email]> wrote:
Hi,
say I have a very messy MultiLinestring, made basically of straight
segments, most of which end up where the next start, some defining
alterative paths (yes, it's another bus route), some simply almost
overlapping with other in the same set (with sub meter differences,
in which I'm not really interested).
I would like to get a clean linework out of that... the line merger
does not help due to all the overlaps. I was thinking probably the
easiest way is to draw a very small buffer and then grab the
skeleton of the polygon as the cleaned up linework but... I have
no idea of how to do the latter

Any smart suggestion?
Cheers
Andrea

--
Andrea Aime
OpenGeo - http://opengeo.org
Expert service straight from the developers.
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel



--
http://amusingprogrammer.blogspot.com/

_______________________________________________
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: Cleaning up a very messy linear collection

aaime
Administrator
Larry Becker ha scritto:

> HI Andrea,
>
>   First you would need to get your very thin buffer to build, which is
> by no means easy for large complex MultiLinestrings.   It will probably
> be very slow and require tons of memory unless you use Martin's latest
> buffer code, and perhaps you might need to get his experimental
> incremental union buffer code too.  Make sure you don't specify a round
> end cap.  After you get the buffer, then conventional wisdom says you
> would need some skeletization code.  I have been searching for code that
> will do this myself with no luck.  I have an algorithm that finds road
> centerlines and works in some special cases, but nothing general.  
> Conceptually, it sounds fairly simple to derive the centerline of a
> buffer since it is of fixed width.  You could just walk around the edge
> of the buffer, saving offset lines.  This would capture the route, but
> would have gaps at the branching points unless you extended them to the
> intersection.
>
>   I'm not really sure what your final goal is.  Are you looking for a
> topological noded list of linestrings (i.e. a conventional road network)
> that you can use to compute routes with, or are you looking for one
> complete linestring that represents the path of the bus?

A bit of both. I need to do proper labelling of that bus lines, but
without a clean linework, it's hard to do so, a dumb algorithm would
simply try to label each of the small elements in the big
multilinestring, as the big picture (the fact that all those little
sticks really do make up a visually single line is apparent to the
user, not much to the algorithms, at least not easily).

Cheers
Andrea

--
Andrea Aime
OpenGeo - http://opengeo.org
Expert service straight from the developers.
_______________________________________________
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: Cleaning up a very messy linear collection

Martin Davis
In reply to this post by aaime
I agree with Larry - the skeletonization route does not seem like a good
way to go.  Very complex, and not guaranteed to give you what you really
want, I don't think (i.e. the skeleton is more than likely to not track
your original lines very well).

If you *do* want to try this, you can check out the skeletonizer code
here: http://www.jump-project.org/project.php?PID=SK&SID=OVER  This
isn't being supported any more, but it did work well when it was built.

Here's how I'd approach the problem:
- Split the linestrings into their component segments.
- "Snap-round" the line segments to some tolerance.  This involves
snapping vertices together where they are close, and inserting nodes in
line segments where nodes are close.
- Dissolve any duplicate line segments
- Remerge the segments (using LineMerger)

I think this should work, although some further cleanup might be required.

This is a classic "internal conflation" problem.  Unfortunately
conflation often involves using heuristics which are tailored to the
problem space - in my experience it's rare that there is a simple,
theoretically clean approach which can clean up data in a single operation.

Andrea Aime wrote:

> Hi,
> say I have a very messy MultiLinestring, made basically of straight
> segments, most of which end up where the next start, some defining
> alterative paths (yes, it's another bus route), some simply almost
> overlapping with other in the same set (with sub meter differences,
> in which I'm not really interested).
> I would like to get a clean linework out of that... the line merger
> does not help due to all the overlaps. I was thinking probably the
> easiest way is to draw a very small buffer and then grab the
> skeleton of the polygon as the cleaned up linework but... I have
> no idea of how to do the latter
>
> Any smart suggestion?
> Cheers
> Andrea
>

--
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Cleaning up a very messy linear collection

Alvaro Zabala-2
Maybe some of gvSIG's topology tools ([1] or [2]), in developing process, could help you



[1] CLEAN geoprocess.  It detects non noded intersections, and remove them (by breaking intersecting lines).  http://subversion.gvsig.org/gvSIG/trunk/extensions/extGeoprocessingExtensions/src/com/iver/cit/gvsig/geoprocess/impl/topology/lineclean/fmap/LineCleanGeoprocess.java

[2] Automathic error fixes for topology rules violation.  http://subversion.gvsig.org/gvSIG/trunk/libraries/libTopology/src/org/gvsig/topology/errorfixes/

Best regards.


> Date: Mon, 3 Nov 2008 11:30:24 -0800
> From: [hidden email]
> To: [hidden email]
> Subject: Re: [jts-devel] Cleaning up a very messy linear collection
>
> I agree with Larry - the skeletonization route does not seem like a good
> way to go. Very complex, and not guaranteed to give you what you really
> want, I don't think (i.e. the skeleton is more than likely to not track
> your original lines very well).
>
> If you *do* want to try this, you can check out the skeletonizer code
> here: http://www.jump-project.org/project.php?PID=SK&SID=OVER This
> isn't being supported any more, but it did work well when it was built.
>
> Here's how I'd approach the problem:
> - Split the linestrings into their component segments.
> - "Snap-round" the line segments to some tolerance. This involves
> snapping vertices together where they are close, and inserting nodes in
> line segments where nodes are close.
> - Dissolve any duplicate line segments
> - Remerge the segments (using LineMerger)
>
> I think this should work, although some further cleanup might be required.
>
> This is a classic "internal conflation" problem. Unfortunately
> conflation often involves using heuristics which are tailored to the
> problem space - in my experience it's rare that there is a simple,
> theoretically clean approach which can clean up data in a single operation.
>
> Andrea Aime wrote:
> > Hi,
> > say I have a very messy MultiLinestring, made basically of straight
> > segments, most of which end up where the next start, some defining
> > alterative paths (yes, it's another bus route), some simply almost
> > overlapping with other in the same set (with sub meter differences,
> > in which I'm not really interested).
> > I would like to get a clean linework out of that... the line merger
> > does not help due to all the overlaps. I was thinking probably the
> > easiest way is to draw a very small buffer and then grab the
> > skeleton of the polygon as the cleaned up linework but... I have
> > no idea of how to do the latter
> >
> > Any smart suggestion?
> > Cheers
> > Andrea
> >
>
> --
> 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


Get news, entertainment and everything you care about at Live.com. Check it out!
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...