Changeset 4208

Timestamp:

06/24/09 15:08:33 (3 years ago)

Author:

pramsey

Message:

Add support for hausdorff distance calculations. Requires GEOS 3.2+. (#209) From Vincent Picavet.
If you are working off of GEOS trunk, svn up, compile and install!

Location:

trunk

Files:

• doc/reference.xml (modified) (1 diff)
• postgis/lwgeom_geos.c (modified) (2 diffs)
• postgis/postgis.sql.in.c (modified) (1 diff)
• postgis/uninstall_postgis.sql.in.c (modified) (1 diff)
• regress/hausdorff_expected (added)
• regress/hausdorff.sql (added)
• regress/Makefile.in (modified) (1 diff)

trunk/doc/reference.xml

@@ -9819 +9819 @@
         </refentry>
 
+        <refentry id="ST_HausdorffDistance">
+          <refnamediv>
+                <refname>ST_HausdorffDistance</refname>
+
+                <refpurpose>Returns the Hausdorff distance between two geometries.</refpurpose>
+          </refnamediv>
+
+          <refsynopsisdiv>
+                <funcsynopsis>
+                  <funcprototype>
+                        <funcdef>float <function>ST_HausdorffDistance</function></funcdef>
+
+                        <paramdef><type>geometry </type>
+                        <parameter>g1</parameter></paramdef>
+
+                        <paramdef><type>geometry </type>
+                        <parameter>g2</parameter></paramdef>
+                  </funcprototype>
+                  <funcprototype>
+                        <funcdef>float <function>ST_HausdorffDistance</function></funcdef>
+
+                        <paramdef><type>geometry </type>
+                        <parameter>g1</parameter></paramdef>
+
+                        <paramdef><type>geometry </type>
+                        <parameter>g2</parameter></paramdef>
+
+                        <paramdef><type>float</type>
+                        <parameter>densifyFrac</parameter></paramdef>
+                  </funcprototype>
+                </funcsynopsis>
+          </refsynopsisdiv>
+
+          <refsection>
+                <title>Description</title>
+
+                <para>Implements algorithm for computing a distance metric which can be thought of as the "Discrete Hausdorff Distance".
+This is the Hausdorff distance restricted to discrete points for one of the geometries.</para>
+                <para>
+When densifyFrac is specified, this function performs a segment densification before computing the discrete hausdorff distance. The densifyFrac parameter sets the fraction by which to densify each segment. Each segment will be split into a number of equal-length subsegments, whose fraction of the total length is closest to the given fraction.
+                </para>
+
+                <note>
+                        <para>
+The current implementation supports only vertices as the discrete locations. This could be extended to allow an arbitrary density of points to be used. 
+                        </para>
+                </note>
+                <note>
+                        <para>
+                                This algorithm is NOT equivalent to the standard Hausdorff distance. However, it computes an approximation that is correct for a large subset of useful cases.
+                        One important part of this subset is Linestrings that are roughly parallel to each other, and roughly equal in length.  This is a useful metric for line matching.
+                        </para>
+                </note>
+
+          </refsection>
+
+          <refsection>
+                <title>Examples</title>
+
+                        <programlisting>postgis=# SELECT st_HausdorffDistance(
+                'LINESTRING (0 0, 2 0)'::geometry,
+                'MULTIPOINT (0 1, 1 0, 2 1)'::geometry);
+ st_hausdorffdistance
+ ----------------------
+                     1
+(1 row)
+                        </programlisting>
+                        <programlisting>postgis=# SELECT st_hausdorffdistance('LINESTRING (130 0, 0 0, 0 150)'::geometry, 'LINESTRING (10 10, 10 150, 130 10)'::geometry, 0.5);
+ st_hausdorffdistance
+ ----------------------
+                    70
+(1 row)
+                        </programlisting>
+
+          </refsection>
+        </refentry>
+
         <refentry id="ST_Distance_Sphere">
           <refnamediv>

trunk/postgis/lwgeom_geos.c

@@ -63 +63 @@
 Datum linemerge(PG_FUNCTION_ARGS);
 Datum coveredby(PG_FUNCTION_ARGS);
+Datum hausdorffdistance(PG_FUNCTION_ARGS);
+Datum hausdorffdistancedensify(PG_FUNCTION_ARGS);
 
 Datum pgis_union_geometry_array_old(PG_FUNCTION_ARGS);
@@ -89 +91 @@
         memcpy(VARDATA(result), ver, strlen(ver));
         PG_RETURN_POINTER(result);
+}
+
+/**
+ *  @brief Compute the Hausdorff distance thanks to the corresponding GEOS function
+ *  @example hausdorffdistance {@link #hausdorffdistance} - SELECT st_hausdorffdistance(
+ *      'POLYGON((0 0, 0 2, 1 2, 2 2, 2 0, 0 0))'::geometry,
+ *      'POLYGON((0.5 0.5, 0.5 2.5, 1.5 2.5, 2.5 2.5, 2.5 0.5, 0.5 0.5))'::geometry);
+ */
+
+PG_FUNCTION_INFO_V1(hausdorffdistance);
+Datum hausdorffdistance(PG_FUNCTION_ARGS)
+{
+        PG_LWGEOM *geom1;
+        PG_LWGEOM *geom2;
+        GEOSGeometry *g1;
+        GEOSGeometry *g2;
+        double result;
+        int retcode;
+
+        POSTGIS_DEBUG(2, "hausdorff_distance called");
+
+        geom1 = (PG_LWGEOM *)  PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
+        geom2 = (PG_LWGEOM *)  PG_DETOAST_DATUM(PG_GETARG_DATUM(1));
+
+        initGEOS(lwnotice, lwnotice);
+
+        g1 = (GEOSGeometry *)POSTGIS2GEOS(geom1);
+        g2 = (GEOSGeometry *)POSTGIS2GEOS(geom2);
+        retcode = GEOSHausdorffDistance(g1, g2, &result);
+        GEOSGeom_destroy(g1);
+        GEOSGeom_destroy(g2);
+
+        if (retcode == 0)
+        {
+                elog(ERROR,"GEOS HausdorffDistance() threw an error!");
+                PG_RETURN_NULL(); /*never get here */
+        }
+
+        PG_FREE_IF_COPY(geom1, 0);
+        PG_FREE_IF_COPY(geom2, 0);
+
+        PG_RETURN_FLOAT8(result);
+}
+
+/**
+ *  @brief Compute the Hausdorff distance with densification thanks to the corresponding GEOS function
+ *  @example hausdorffdistancedensify {@link #hausdorffdistancedensify} - SELECT st_hausdorffdistancedensify(
+ *      'POLYGON((0 0, 0 2, 1 2, 2 2, 2 0, 0 0))'::geometry,
+ *      'POLYGON((0.5 0.5, 0.5 2.5, 1.5 2.5, 2.5 2.5, 2.5 0.5, 0.5 0.5))'::geometry, 0.5);
+ */
+
+PG_FUNCTION_INFO_V1(hausdorffdistancedensify);
+Datum hausdorffdistancedensify(PG_FUNCTION_ARGS)
+{
+        PG_LWGEOM *geom1;
+        PG_LWGEOM *geom2;
+        GEOSGeometry *g1;
+        GEOSGeometry *g2;
+        double densifyFrac;
+        double result;
+        int retcode;
+
+
+        geom1 = (PG_LWGEOM *)  PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
+        geom2 = (PG_LWGEOM *)  PG_DETOAST_DATUM(PG_GETARG_DATUM(1));
+        densifyFrac = *(double *)  PG_DETOAST_DATUM(PG_GETARG_DATUM(2));
+
+        initGEOS(lwnotice, lwnotice);
+
+        g1 = (GEOSGeometry *)POSTGIS2GEOS(geom1);
+        g2 = (GEOSGeometry *)POSTGIS2GEOS(geom2);
+        retcode = GEOSHausdorffDistanceDensify(g1, g2, densifyFrac, &result);
+        GEOSGeom_destroy(g1);
+        GEOSGeom_destroy(g2);
+
+        if (retcode == 0)
+        {
+                elog(ERROR,"GEOS HausdorffDistanceDensify() threw an error!");
+                PG_RETURN_NULL(); /*never get here */
+        }
+
+        PG_FREE_IF_COPY(geom1, 0);
+        PG_FREE_IF_COPY(geom2, 0);
+
+        PG_RETURN_FLOAT8(result);
 }
 

trunk/postgis/postgis.sql.in.c

@@ -3919 +3919 @@
 #endif
 
+#if POSTGIS_GEOS_VERSION >= 32
+-- Requires GEOS >= 3.2.0
+-- Availability: 1.5.0 
+CREATE OR REPLACE FUNCTION ST_HausdorffDistance(geometry, geometry)
+        RETURNS FLOAT8
+        AS 'MODULE_PATHNAME', 'hausdorffdistance'
+        LANGUAGE 'C' IMMUTABLE STRICT; 
+#endif
+
+#if POSTGIS_GEOS_VERSION >= 32
+-- Requires GEOS >= 3.2.0
+-- Availability: 1.5.0 
+CREATE OR REPLACE FUNCTION ST_HausdorffDistance(geometry, geometry, float8)
+        RETURNS FLOAT8
+        AS 'MODULE_PATHNAME', 'hausdorffdistancedensify'
+        LANGUAGE 'C' IMMUTABLE STRICT;
+#endif
+
 -- Deprecation in 1.2.3
 CREATE OR REPLACE FUNCTION difference(geometry,geometry)

trunk/postgis/uninstall_postgis.sql.in.c

@@ -400 +400 @@
 DROP FUNCTION ST_Intersection(geometry,geometry);
 DROP FUNCTION intersection(geometry,geometry);
+#if POSTGIS_GEOS_VERSION >= 32
+DROP FUNCTION ST_HausdorffDistance(geometry, geometry)
+#endif
+#if POSTGIS_GEOS_VERSION >= 32
+DROP FUNCTION ST_HausdorffDistance(geometry, geometry, float8)
+#endif
 
 

trunk/regress/Makefile.in

@@ -53 +53 @@
         regress_ogc \
         regress_bdpoly \
-        regress_proj
+        regress_proj \
+        hausdorff
 
 # Covers/CoveredBy only if GEOS >= 3.0