[postgis-users] How to match lines between two similar graphs?

[Stephen Woodbridge]

On 1/26/2012 12:05 PM, Nicolas Ribot wrote:
> On 26 January 2012 17:16, Stephen Woodbridge<woodbri at swoodbridge.com>  wrote:
>> On 1/26/2012 10:47 AM, Nicolas Ribot wrote:
>>>>
>>>> Hi All,
>>>>
>>>> I have an interesting problem I am trying to solve and would love some
>>>> feedback on how to best go about it.
>>>>
>>>> I have road data from two different vendor data sets. But this could also
>>>> be
>>>> one road network and a GPS track, so I think this is a pretty common use
>>>> case.
>>>>
>>>> Assumptions:
>>>>
>>>> o the networks are similar, ie: they have similar roadway coverage
>>>> o the two sets might be slightly misaligned, ie: shifted by some amount
>>>> o the segments in the two data sets do not have to be broken into
>>>> equivalent
>>>> segments, ie: one segment in A might be represented my multiple segments
>>>> in
>>>> B
>>>> o segments are not aligned end point wise, ie: a segment in A might go
>>>> from
>>>> mid-point one segment in B to the midpoint of a connected segment in B
>>>> o in many cases I will be working with a set of lines in one set that I
>>>> need
>>>> to match to the other to select a matching set of lines.
>>>>
>>>> So strategies for matching these:
>>>>
>>>> 1. take a segment from A and buffer it, then intersect the data in B and
>>>> select the longest intersected object. I can probably throw out any
>>>> pieces
>>>> smaller than the buffer distance.
>>>>
>>>> 2. Do the same but buffer and union the set of lines into a single
>>>> multipolygon, and intersect that with the other set.
>>>>
>>>> 3. ??? Other ideas?
>>>>
>>>> Thoughts on performance?
>>>>
>>>> Typically I will have a small set (1-20) of segments to compare against a
>>>> larger (100K-2M) set. Obvious a spatial index will will be used. But I'm
>>>> wondering what is the fast way to do this matching computationally. I
>>>> think
>>>> I will want to be able to compare 1-200 sets like this every 5 mins as
>>>> data
>>>> comes in from a feed, while supporting other queries.
>>>>
>>>
>>> With this small input set, maybe st_hausdorffDistance() could be
>>> useful to select good candidates in the larger set.
>>
>>
>> Hi Nicolas,
>>
>> Thank you for your insights and suggestions. I have not used
>> st_hausdorffDistance() and just read up on it. I agree this might be a good
>> option for initial segment selection.
>>
>>
>
> Stephen,
>
> another thought:
> Are your input segments connected and forming a longer linestring you
> want to "rebuild" against big dataset, or are they independent objects
> ?
>
> If the latter, distance search and segment orientation could give good
> results, assuming the big dataset segments orientations are
> pre-computed:
> If the segments are close to each other (in fact, it should be "if all
> their vertices are close enough") and the segments orientations are in
> a close range, then chances are good you found the right target
> segment.

Nicolas,

I am still waiting on the actual data. The input is a traffic disruption 
feed with ids to one dataset and I need to map the identified segments 
to the equivalent segments in a Navteq data set. I suspect that I will 
have a combination of connected segments that form a sub-network and not 
a single path. But some of the sample feed data I do have references a 
single segment, like the location of an accident. In other cases, like a 
major construction project that affects multiple segments on multiple 
streets it will be a sub-net.

-Steve