[postgis-devel] st_dwithin, st_within, st_dcompletlywithin

[Martin Davis]

Yes, in the general case Hausdorff distance is very complicated to 
compute - and the straightforward algorithms are o(n^3)

JTS/GEOS does not compute the full Hausdorff distance, but a discrete 
approximation.  For most purposes that seems sufficient.

nicklas.aven at jordogskog.no wrote:
> I have been looking some more on this Hausdorff Distance. I'm afraid I 
> have to take a step back. There are aspects that is not handled by my 
> original idea and I can't see how to deal with it. The problem I 
> didn't realize is that if the second geometry is "surrounding" the 
> first, we have to search for the most far away point between the 
> vertices. In the ordinary maxdistance-case we don't have to consider 
> that and the maxdistance is always between two vertices.
>  
> /Nicklas
>  
>  
>
> 2009-07-09 Paragon Corporation wrote:
>
> Oh that's what that is. Hmm and I think its already ported to PostGIS,
> >though would be interesting to compare the speeds and results. Since the
> >current one in trunk is a GEOS call and Nicklas' would be a native 
> PostGIS.
> >
> >http://trac.osgeo.org/postgis/ticket/209
> >
> >Paul are you hmm planning add this to the manual -- I see you closed 
> it? I
> >don't recall seeing it in the 1.5 docs or were we waiting for GEOS to be
> >patched first?
> >
> >Thanks,
> >Regina
> >
> >
> >-----Original Message-----
> >From: postgis-devel-bounces at postgis.refractions.net
> >[mailto:postgis-devel-bounces at postgis.refractions.net] On Behalf Of 
> Martin
> >Davis
> >Sent: Wednesday, July 08, 2009 6:14 PM
> >To: PostGIS Development Discussion
> >Subject: Re: [postgis-devel] st_dwithin, st_within, st_dcompletlywithin
> >
> >That distance metric is known as the Hausdorff Distance. It's implemented
> >in JTS, and probably in GEOS as well.
> >
> >nicklas.aven at jordogskog.no wrote:
> >>
> >>
> >> A function that gives the answer to for example:
> >> "How far away from France can you get in Belgia"
> >> To answer that we have to store compare the shortest distance to
> >> geometry2 from each vertex in geometry1 and finaly find wich vertex in
> >> geometry1 that has the highest "mindistance" to geometry2.
> >> Hope the idee is possible to understand. Is it of any use?
> >
> >--
> >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
> >
> >
> >
> >_______________________________________________
> >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