[postgis-devel] ST_Line_Substring

[nicklas.aven at jordogskog.no]

2009-09-10 Martin Davis  wrote:

By the way, you are already using Branch-and-Bound in your algorithm! 
>That's the formal name for the approach of "pruning off" sets of tests 
>when you know a priori that they will not be better than the current 
>best candidate solution.  In your algorithm, you can avoid testing pairs 
>of segments when you know via their sort distance that they are further 
>than the best pair that has been found.
>
>Also, I think in your algorithm you should be thinking about testing 
>points against line segments, not just other points.  The closest 
>distance between two segments does not always occur at a pair of 
>endpoints (although it will include an endpoint of at least one of the 
>segments)
>

If I don't missunderstand you, I do calculate point-segment distance.
starting at line 196 in
http://trac.osgeo.org/postgis/browser/spike/nicklas/distcalc/liblwgeom/measures.c

But I rewrote it a little from the function now in postgis,because I want to find the point on the segment, not just the distance. That is because of the function shortestline, wich gives you the line from where the mindistance is calculated.


The next thing I have planned to do is handling subgeoms before calculating distances between the actual geometries. To iterate through all subgeoms and sort them on their boundingboxes maxdistances from eachother and then only calculate distances for subgeoms having mindistances between their boundingboxes smaller than the current mindistance between the real geometries.