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

[Stephen Woodbridge]

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.

-Steve