Turning a partially self-overlapping line into non overlapping parts

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

Turning a partially self-overlapping line into non overlapping parts

aaime
Administrator
Hi,
I have quite a curious issue. I have a data model that represents
bus routes, usually a single line represents both the bus going
forward and coming back.
As you may imagine, this means most of the line overlaps with
itself, minus parts in which the path diverges on the way back
(taking a different road due to a one way or similar issues).

I need to find a way to split the line into parts so that
the overlaps are eliminated, and the eventual deviations
are represented as separate lines.

Trying some ascii art, if my input is this:

  /--------\
/          \___________________
\----------/    \_____/

I would like to get out the following non overlapping
lines:

  /--------\
/          \___________________
\----------/


                \_____/


Now, don't let be fooled by the drawing, it may also
be that forward segments and backwards segments do
not use the same vertices, even if they are describing
the same path, so trying to do a simple equality comparison
between segments won't do.

I'm really pulling my hairs out, no solutions so far.

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: Turning a partially self-overlapping line into non overlapping parts

Martin Davis
There's two different answers to this, depending on whether the out and
back paths are really *exactly* coincident, or whether they are only
approximately so (the latter seems more likely, if these are say GPS
traces).

If they're exactly coincident, can't you just difference one from the
other to get the non-overlapping parts?

If they're only approximate, then you're into a road network conflation
problem.  You might look at RoadMatcher, which is able to perform
approximate matching of linestrings and identify discrepancies.  
Alternatively, I can fill you in a little bit on some of the algorithms
used...

Andrea Aime wrote:

> Hi,
> I have quite a curious issue. I have a data model that represents
> bus routes, usually a single line represents both the bus going
> forward and coming back.
> As you may imagine, this means most of the line overlaps with
> itself, minus parts in which the path diverges on the way back
> (taking a different road due to a one way or similar issues).
>
> I need to find a way to split the line into parts so that
> the overlaps are eliminated, and the eventual deviations
> are represented as separate lines.
>
> Trying some ascii art, if my input is this:
>
>  /--------\
> /          \___________________
> \----------/    \_____/
>
> I would like to get out the following non overlapping
> lines:
>
>  /--------\
> /          \___________________
> \----------/
>
>
>                \_____/
>
>
> Now, don't let be fooled by the drawing, it may also
> be that forward segments and backwards segments do
> not use the same vertices, even if they are describing
> the same path, so trying to do a simple equality comparison
> between segments won't do.
>
> I'm really pulling my hairs out, no solutions so far.
>
> 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
Loading...