On 26 January 2012 17:16, Stephen Woodbridge <[email protected]> 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 _______________________________________________ postgis-users mailing list [email protected] http://postgis.refractions.net/mailman/listinfo/postgis-users
