[postgis-devel] ST_Line_Substring

Wed Sep 9 15:28:53 PDT 2009

Unfortunately I think the only way to compare the two approaches is to 
implement them both in the same system and then profile them on a set of 
test cases.  There may or may not be a clear winner.   It might be that 
they are each superior for a different kind of imput (e.g. overlapping 
BB versus widely separated.geometry).

It would definitely be interesting to see... When I have some time I 
might try coding up the segment-sorting-along-an-axis approach in JTS to 
see how it does with my test cases.

And Nicklas, I think I agree with you that the sorting-along-an-axis 
approach should be robust and complete.  The only thing that different 
geometric situations should affect is the performance.

Martin

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