[postgis-devel] ST_Line_Substring

nicklas.aven at jordogskog.no nicklas.aven at jordogskog.no
Thu Sep 10 01:36:49 PDT 2009


just a correction of myself: it of course should have been: 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 maxdistances between their boundingboxes smaller than the current mindistance between the real geometries.

/Nicklas
2009-09-10 nicklas.aven at jordogskog.no wrote:


>
> 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.
>
> From that it would be possible to just collect a bunch of geometries and put in to get the nearest neighbour in a fast way.
>
> The problem I think is to avoid to much overhead when calculating smaller and single geometries.
>
> /Nicklas
>
>
>
>
>
>
>
> >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
> >> >>>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
> >> >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
> >
> >_______________________________________________
> >postgis-devel mailing list
> >postgis-devel at postgis.refractions.net
> >postgis.refractions.net/mailman/listinfo/postgis-devel
> >
> > 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20090910/3e226855/attachment.html>


More information about the postgis-devel mailing list