No subject
Tue Oct 7 10:08:30 PDT 2008
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
>> >>>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
>
>_______________________________________________
>postgis-devel mailing list
>postgis-devel at postgis.refractions.net
>http://postgis.refractions.net/mailman/listinfo/postgis-devel
>
>
--=_122330d47ef7236a5e565127debe7cc0
Content-Type: text/html; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<html>
<head>
</head>
<body><br />
<br />
2009-09-10 Martin Davis wrote:<br />
<br />
By the way, you are already using Branch-and-Bound in your algorithm! <br =
/>
=09
>That's the formal name for the approach of "pruning off" sets of tests <br=
/>
=09
>when you know a priori that they will not be better than the current <br /=
>
=09
>best candidate solution. In your algorithm, you can avoid testing pairs <=
br />
=09
>of segments when you know via their sort distance that they are further <b=
r />
=09
>than the best pair that has been found.<br />
=09
><br />
=09
>Also, I think in your algorithm you should be thinking about testing <br /=
>
=09
>points against line segments, not just other points. The closest <br />
=09
>distance between two segments does not always occur at a pair of <br />
=09
>endpoints (although it will include an endpoint of at least one of the <br=
/>
=09
>segments)<br />
=09
><br />
<br />
If I don't missunderstand you, I do calculate point-segment distance.<br /=
>
starting at line 196 in<br />
http://trac.osgeo.org/postgis/browser/spike/nicklas/distcalc/liblwgeom/mea=
sures.c<br />
<br />
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 mindista=
nce is calculated.<br />
<br />
<br />
The next thing I have planned to do is handling subgeoms before calculatin=
g distances between the actual geometries. To iterate through all subgeoms =
and sort them on their boundingboxes maxdistances from eachother and then o=
nly calculate distances for subgeoms having mindistances between their boun=
dingboxes smaller than the current mindistance between the real geometries.=
<br />
<br />
From that it would be possible to just collect a bunch of geometries and p=
ut in to get the nearest neighbour in a fast way.<br />
<br />
The problem I think is to avoid to much overhead when calculating smaller =
and single geometries.<br />
<br />
/Nicklas<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
=09
>nicklas.aven at jordogskog.no wrote:<br />
=09
>> I have tried some of the more unusual cases, but I don't think I have <b=
r />
=09
>> tried that, with the center outside the boundary. My first thought is <b=
r />
=09
>> that i don't think that is a problem because the calculated values <br /=
>
=09
>> along the line between the centers will still be comparable. It should <=
br />
=09
>> just be a matter of performance. the more this center-center line <br />
=09
>> direction differs from the direction of the line the shortest distance <=
br />
=09
>> is measured along, the more iteration it will take. That is because <br =
/>
=09
>> the function don't stop until it has tested all vertexes closer than <br=
/>
=09
>> the current min-distance in the direction of the center-center line.<br =
/>
=09
>><br />
=09
>> I don't think the function is heuristic in the way that it shouldn't <br=
/>
=09
>> always give an exact answer.<br />
=09
>><br />
=09
>> Now I saw Martins answer, interesting!<br />
=09
>> I don't understand "branch-and-boun'd but if it gives a more general <br=
/>
=09
>> solution it must be very interesting.<br />
=09
>> <br />
=09
>> Is there some way to compare the performance of the approaches.<br />
=09
>><br />
=09
>> Thanks<br />
=09
>> Nicklas<br />
=09
>><br />
=09
>><br />
=09
>> 2009-09-09 Paul Ramsey wrote:<br />
=09
>><br />
=09
>> Thanks Nicklas, that's a nice write-up. In future, remember to attach<br=
/>
=09
>> >in open formats, like PDF or OpenOffice. And now that I see your<br />
=09
>> >implementation is a bolt-on enhancement ot distance calculations<br />
=09
>> >rather than a replacement I feel more comfortable with it. It seems<br =
/>
=09
>> >like you could have some degenerate conditions if the bbox center is<br=
/>
=09
>> >quite a ways outside the actual polygon boundary, though, have you<br /=
>
=09
>> >tested that?<br />
=09
>> ><br />
=09
>> >Another approach to the problem would be to build an internal index of<=
br />
=09
>> >the edges of both polygons, then traverse that index. It would have<br =
/>
=09
>> >the advantage of being cacheable and more general (works for all<br />
=09
>> >cases) but would probably not have nearly the real-world improvement<br=
/>
=09
>> >your heuristic has.<br />
=09
>> ><br />
=09
>> >I'm interested to hear what a real geometer thinks of your approach, I<=
br />
=09
>> >wonder if Martin would comment?<br />
=09
>> ><br />
=09
>> >P.<br />
=09
>> ><br />
=09
>> >On Wed, Sep 9, 2009 at 1:32 PM, wrote:<br />
=09
>> >> thanks<br />
=09
>> >><br />
=09
>> >> about the distance-calculations don't miss the dist.doc in ticket #23=
1.<br />
=09
>> >> That might save you some time to see the idea behind the new<br />
=09
>> >> distance-calculation of polygons and linestrings that don't have<br /=
>
=09
>> >> intersecting bounding boxes.<br />
=09
>> >><br />
=09
>> >> /Nicklas<br />
=09
>> >><br />
=09
>> >><br />
=09
>> >><br />
=09
>> >> 2009-09-09 Paul Ramsey wrote:<br />
=09
>> >><br />
=09
>> >> Niklas,<br />
=09
>> >>><br />
=09
>> >>>There are at least three different implementations of line substring<=
br />
=09
>> >>>hanging around, a couple that are bound to the old functions and one =
I<br />
=09
>> >>>did for the elevationbetween functions. The whole conjunction calls<b=
r />
=09
>> >>>out for a cleaning and consolidation, frankly, but I've been leaving<=
br />
=09
>> >>>it alone on the basis of not touching things that are working.<br />
=09
>> >>><br />
=09
>> >>>Attach your patch for 3D to a ticket so it doesn't get lost. I've got=
<br />
=09
>> >>>reviewing your distance ticket on my list too so don't give up hope o=
n<br />
=09
>> >>>that.<br />
=09
>> >>><br />
=09
>> >>>P.<br />
=09
>> >>><br />
=09
>> >>>On Sun, Aug 30, 2009 at 1:17 PM, wrote:<br />
=09
>> >>>> The function ST_Line_Substring is some mixture between 2D and 3D. I=
t<br />
=09
>> >>>> preserves the z-value but don't use it in calculation. The <br />
=09
>> documentation<br />
=09
>> >>>> describes this but the note that the function supports 3D I think i=
s<br />
=09
>> >>>> false.<br />
=09
>> >>>><br />
=09
>> >>>> Why not make it real 3D so it considers the third dimmension in the=
<br />
=09
>> >>>> calculation.<br />
=09
>> >>>><br />
=09
>> >>>> Now this query:<br />
=09
>> >>>> select st_asewkt(ST_Line_Substring(the_geom,0.2, 0.8))<br />
=09
>> >>>> from<br />
=09
>> >>>> (SELECT ST_GeomFromEWKT('SRID=3D4269;LINESTRING(1 1 1,1 1 3, 1 1 5,=
1 1<br />
=09
>> >>>> 8)')<br />
=09
>> >>>> as the_geom ) a;<br />
=09
>> >>>> gives the little bit strange result:<br />
=09
>> >>>> "SRID=3D4269;LINESTRING(1 1 3,1 1 5)"<br />
=09
>> >>>><br />
=09
>> >>>> I think t would be much better to make it fully 3D-supportive. <br =
/>
=09
>> Then the<br />
=09
>> >>>> result of this query is:<br />
=09
>> >>>> "SRID=3D4269;LINESTRING(1 1 2.4,1 1 3,1 1 5,1 1 6.6)"<br />
=09
>> >>>><br />
=09
>> >>>> I have attached a patch that makes this.<br />
=09
>> >>>><br />
=09
>> >>>> The reason I started to look at this was that I wanted a function <=
br />
=09
>> that<br />
=09
>> >>>> takes<br />
=09
>> >>>> distances instead of fraction of the total length.<br />
=09
>> >>>> I hve a working finction that takes the startdistance and <br />
=09
>> end-distance<br />
=09
>> >>>> from<br />
=09
>> >>>> the start of the line to pull out the substring-line. In some <br /=
>
=09
>> cases that<br />
=09
>> >>>> is<br />
=09
>> >>>> more straight on than going via the fractions. Should I post it <br=
/>
=09
>> or will<br />
=09
>> >>>> there be to many functions too little difference?<br />
=09
>> >>>> The question is if I should put effort in writing the <br />
=09
>> documentation and<br />
=09
>> >>>> regression-tests.<br />
=09
>> >>>><br />
=09
>> >>>> Greetings<br />
=09
>> >>>> Nicklas<br />
=09
>> >>>><br />
=09
>> >>>> _______________________________________________<br />
=09
>> >>>> postgis-devel mailing list<br />
=09
>> >>>> postgis-devel at postgis.refractions.net<br />
=09
>> >>>> http://postgis.refractions.net/mailman/listinfo/postgis-devel<br />
=09
>> >>>><br />
=09
>> >>>><br />
=09
>> >>>_______________________________________________<br />
=09
>> >>>postgis-devel mailing list<br />
=09
>> >>>postgis-devel at postgis.refractions.net<br />
=09
>> >>>http://postgis.refractions.net/mailman/listinfo/postgis-devel<br />
=09
>> >>><br />
=09
>> >>><br />
=09
>> >> _______________________________________________<br />
=09
>> >> postgis-devel mailing list<br />
=09
>> >> postgis-devel at postgis.refractions.net<br />
=09
>> >> http://postgis.refractions.net/mailman/listinfo/postgis-devel<br />
=09
>> >><br />
=09
>> >><br />
=09
>> >_______________________________________________<br />
=09
>> >postgis-devel mailing list<br />
=09
>> >postgis-devel at postgis.refractions.net<br />
=09
>> >http://postgis.refractions.net/mailman/listinfo/postgis-devel<br />
=09
>> ><br />
=09
>> ><br />
=09
>> ------------------------------------------------------------------------=
<br />
=09
>><br />
=09
>> _______________________________________________<br />
=09
>> postgis-devel mailing list<br />
=09
>> postgis-devel at postgis.refractions.net<br />
=09
>> http://postgis.refractions.net/mailman/listinfo/postgis-devel<br />
=09
>> <br />
=09
><br />
=09
>-- <br />
=09
>Martin Davis<br />
=09
>Senior Technical Architect<br />
=09
>Refractions Research, Inc.<br />
=09
>(250) 383-3022<br />
=09
><br />
=09
>_______________________________________________<br />
=09
>postgis-devel mailing list<br />
=09
>postgis-devel at postgis.refractions.net<br />
=09
>http://postgis.refractions.net/mailman/listinfo/postgis-devel<br />
=09
><br />
=09
>
</body>
</html>
--=_122330d47ef7236a5e565127debe7cc0--