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

[Nicolas Ribot]

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