[postgis-devel] ST_Line_Substring

Wed Sep 9 15:36:28 PDT 2009

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)

nicklas.aven at jordogskog.no wrote:
> I have tried some of the more unusual cases, but I don't think I have 
> tried that, with the center outside the boundary. My first thought is 
> that i don't think that is a problem because the calculated values 
> along the line between the centers will still be comparable. It should 
> just be a matter of performance. the more this center-center line 
> direction differs from the direction of the line the shortest distance 
> is measured along, the more iteration it will take. That is because 
> the function don't stop until it has tested all vertexes closer than 
> the current min-distance in the direction of the center-center line.
>
> I don't think the function is heuristic in the way that it shouldn't 
> always give an exact answer.
>
> Now I saw Martins answer, interesting!
> I don't understand "branch-and-boun'd but if it gives a more general 
> solution it must be very interesting.
>  
> Is there some way to compare the performance of the approaches.
>
> Thanks
> Nicklas
>
>
> 2009-09-09 Paul Ramsey wrote:
>
> Thanks Nicklas, that's a nice write-up. In future, remember to attach
> >in open formats, like PDF or OpenOffice. And now that I see your
> >implementation is a bolt-on enhancement ot distance calculations
> >rather than a replacement I feel more comfortable with it. It seems
> >like you could have some degenerate conditions if the bbox center is
> >quite a ways outside the actual polygon boundary, though, have you
> >tested that?
> >
> >Another approach to the problem would be to build an internal index of
> >the edges of both polygons, then traverse that index. It would have
> >the advantage of being cacheable and more general (works for all
> >cases) but would probably not have nearly the real-world improvement
> >your heuristic has.
> >
> >I'm interested to hear what a real geometer thinks of your approach, I
> >wonder if Martin would comment?
> >
> >P.
> >
> >On Wed, Sep 9, 2009 at 1:32 PM, wrote:
> >> thanks
> >>
> >> about the distance-calculations don't miss the dist.doc in ticket #231.
> >> That might save you some time to see the idea behind the new
> >> distance-calculation of polygons and linestrings that don't have
> >> intersecting bounding boxes.
> >>
> >> /Nicklas
> >>
> >>
> >>
> >> 2009-09-09 Paul Ramsey wrote:
> >>
> >> Niklas,
> >>>
> >>>There are at least three different implementations of line substring
> >>>hanging around, a couple that are bound to the old functions and one I
> >>>did for the elevationbetween functions. The whole conjunction calls
> >>>out for a cleaning and consolidation, frankly, but I've been leaving
> >>>it alone on the basis of not touching things that are working.
> >>>
> >>>Attach your patch for 3D to a ticket so it doesn't get lost. I've got
> >>>reviewing your distance ticket on my list too so don't give up hope on
> >>>that.
> >>>
> >>>P.
> >>>
> >>>On Sun, Aug 30, 2009 at 1:17 PM, wrote:
> >>>> The function ST_Line_Substring is some mixture between 2D and 3D. It
> >>>> preserves the z-value but don't use it in calculation. The 
> documentation
> >>>> describes this but the note that the function supports 3D I think is
> >>>> false.
> >>>>
> >>>> Why not make it real 3D so it considers the third dimmension in the
> >>>> calculation.
> >>>>
> >>>> Now this query:
> >>>> select st_asewkt(ST_Line_Substring(the_geom,0.2, 0.8))
> >>>>  from
> >>>> (SELECT ST_GeomFromEWKT('SRID=4269;LINESTRING(1 1 1,1 1 3, 1 1 5, 1 1
> >>>> 8)')
> >>>> as the_geom ) a;
> >>>> gives the little bit strange result:
> >>>> "SRID=4269;LINESTRING(1 1 3,1 1 5)"
> >>>>
> >>>> I think t would be much better to make it fully 3D-supportive. 
> Then the
> >>>> result of this query is:
> >>>> "SRID=4269;LINESTRING(1 1 2.4,1 1 3,1 1 5,1 1 6.6)"
> >>>>
> >>>> I have attached a patch that makes this.
> >>>>
> >>>> The reason I started to look at this was that I wanted a function 
> that
> >>>> takes
> >>>> distances instead of fraction of the total length.
> >>>> I hve a working finction that takes the startdistance and 
> end-distance
> >>>> from
> >>>> the start of the line to pull out the substring-line. In some 
> cases that
> >>>> is
> >>>> more straight on than going via the fractions. Should I post it 
> or will
> >>>> there be to many functions too little difference?
> >>>> The question is if I should put effort in writing the 
> documentation and
> >>>> regression-tests.
> >>>>
> >>>> Greetings
> >>>> Nicklas
> >>>>
> >>>> _______________________________________________
> >>>> postgis-devel mailing list
> >>>> postgis-devel at postgis.refractions.net
> >>>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >>>>
> >>>>
> >>>_______________________________________________
> >>>postgis-devel mailing list
> >>>postgis-devel at postgis.refractions.net
> >>>http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >>>
> >>>
> >> _______________________________________________
> >> postgis-devel mailing list
> >> postgis-devel at postgis.refractions.net
> >> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >>
> >>
> >_______________________________________________
> >postgis-devel mailing list
> >postgis-devel at postgis.refractions.net
> >http://postgis.refractions.net/mailman/listinfo/postgis-devel
> >
> >
> ------------------------------------------------------------------------
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>   

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022