[postgis-tickets] r15400 - New function ST_FrechetDistance (patch from Shinichi Sugiyama)
Regina Obe
lr at pcorp.us
Mon May 22 21:39:56 PDT 2017
Author: robe
Date: 2017-05-22 21:39:55 -0700 (Mon, 22 May 2017)
New Revision: 15400
Added:
trunk/regress/frechet.sql
trunk/regress/frechet_expected
Modified:
trunk/NEWS
trunk/doc/reference_measure.xml
trunk/postgis/lwgeom_geos.c
trunk/postgis/postgis.sql.in
trunk/regress/Makefile.in
trunk/utils/postgis_restore.pl.in
Log:
New function ST_FrechetDistance (patch from Shinichi Sugiyama)
Closes #3677
Closes https://github.com/postgis/postgis/pull/120
Modified: trunk/NEWS
===================================================================
--- trunk/NEWS 2017-05-22 16:36:11 UTC (rev 15399)
+++ trunk/NEWS 2017-05-23 04:39:55 UTC (rev 15400)
@@ -8,6 +8,7 @@
- #3689, Add orientation checking and forcing functions (Dan Baston)
- #3753, Gist penalty speed improvements for 2d and nd points
(Darafei Praliaskouski)
+ - #3677, ST_FrechetDistance (Shinichi Sugiyama)
* Bug Fixes *
- #3682, Boolean (FTLogical) should be 1 byte not 2 bytes
Modified: trunk/doc/reference_measure.xml
===================================================================
--- trunk/doc/reference_measure.xml 2017-05-22 16:36:11 UTC (rev 15399)
+++ trunk/doc/reference_measure.xml 2017-05-23 04:39:55 UTC (rev 15400)
@@ -2598,8 +2598,84 @@
</programlisting>
</refsection>
+ <refsection>
+ <title>See Also</title>
+
+ <para><xref linkend="ST_FrechetDistance" /></para>
+ </refsection>
</refentry>
+ <refentry id="ST_FrechetDistance">
+ <refnamediv>
+ <refname>ST_FrechetDistance</refname>
+
+ <refpurpose>Returns the Fréchet distance between two geometries. This is a measure of similarity between curves that takes into account the location
+ and ordering of the points along the curves. Units are in the units of the spatial reference system of the geometries.</refpurpose>
+ </refnamediv>
+
+ <refsynopsisdiv>
+ <funcsynopsis>
+ <funcprototype>
+ <funcdef>float <function>ST_FrechetDistance</function></funcdef>
+
+ <paramdef><type>geometry </type>
+ <parameter>g1</parameter></paramdef>
+
+ <paramdef><type>geometry </type>
+ <parameter>g2</parameter></paramdef>
+
+ <paramdef><type>float</type>
+ <parameter>densifyFrac = -1</parameter></paramdef>
+ </funcprototype>
+ </funcsynopsis>
+ </refsynopsisdiv>
+
+ <refsection>
+ <title>Description</title>
+
+ <para>Implements algorithm for computing the Fréchet distance restricted to discrete points for both geometries, based on <ulink url="http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf">Computing Discrete Fréchet Distance</ulink>.
+ The Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. Therefore it is often better than the Hausdorff distance. </para>
+ <para>
+When the optional densifyFrac is specified, this function performs a segment densification before computing the discrete Fréchet 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>
+The smaller densifyFrac we specify, the more acurate Fréchet distance we get. But, the computation time and the memory usage increase with the square of the number of subsegments.
+ </para>
+ </note>
+ <para>Availability: 2.4.0 - requires GEOS >= 3.7.0</para>
+
+ </refsection>
+
+ <refsection>
+ <title>Examples</title>
+ <programlisting>postgres=# SELECT st_frechetdistance('LINESTRING (0 0, 100 0)'::geometry, 'LINESTRING (0 0, 50 50, 100 0)'::geometry);
+ st_frechetdistance
+--------------------
+ 70.7106781186548
+(1 row)
+ </programlisting>
+ <programlisting>SELECT st_frechetdistance('LINESTRING (0 0, 100 0)'::geometry, 'LINESTRING (0 0, 50 50, 100 0)'::geometry, 0.5);
+ st_frechetdistance
+--------------------
+ 50
+(1 row)
+ </programlisting>
+
+ </refsection>
+ <refsection>
+ <title>See Also</title>
+
+ <para><xref linkend="ST_HausdorffDistance" /></para>
+ </refsection>
+ </refentry>
+
<refentry id="ST_MaxDistance">
<refnamediv>
<refname>ST_MaxDistance</refname>
Modified: trunk/postgis/lwgeom_geos.c
===================================================================
--- trunk/postgis/lwgeom_geos.c 2017-05-22 16:36:11 UTC (rev 15399)
+++ trunk/postgis/lwgeom_geos.c 2017-05-23 04:39:55 UTC (rev 15400)
@@ -99,6 +99,7 @@
Datum coveredby(PG_FUNCTION_ARGS);
Datum hausdorffdistance(PG_FUNCTION_ARGS);
Datum hausdorffdistancedensify(PG_FUNCTION_ARGS);
+Datum ST_FrechetDistance(PG_FUNCTION_ARGS);
Datum ST_UnaryUnion(PG_FUNCTION_ARGS);
Datum ST_Equals(PG_FUNCTION_ARGS);
Datum ST_BuildArea(PG_FUNCTION_ARGS);
@@ -279,8 +280,83 @@
PG_RETURN_FLOAT8(result);
}
+/**
+ * @brief Compute the Frechet distance with optional densification thanks to the corresponding GEOS function
+ * @example ST_FrechetDistance {@link #frechetdistance} - SELECT ST_FrechetDistance(
+ * 'LINESTRING (0 0, 50 200, 100 0, 150 200, 200 0)'::geometry,
+ * 'LINESTRING (0 200, 200 150, 0 100, 200 50, 0 0)'::geometry, 0.5);
+ */
+
+PG_FUNCTION_INFO_V1(ST_FrechetDistance);
+Datum ST_FrechetDistance(PG_FUNCTION_ARGS)
+{
+#if POSTGIS_GEOS_VERSION < 37
+ lwpgerror("The GEOS version this PostGIS binary "
+ "was compiled against (%d) doesn't support "
+ "'GEOSFechetDistance' function (3.7.0+ required)",
+ POSTGIS_GEOS_VERSION);
+ PG_RETURN_NULL();
+#else /* POSTGIS_GEOS_VERSION >= 37 */
+ GSERIALIZED *geom1;
+ GSERIALIZED *geom2;
+ GEOSGeometry *g1;
+ GEOSGeometry *g2;
+ double densifyFrac;
+ double result;
+ int retcode;
+
+ geom1 = PG_GETARG_GSERIALIZED_P(0);
+ geom2 = PG_GETARG_GSERIALIZED_P(1);
+ densifyFrac = PG_GETARG_FLOAT8(2);
+
+ if ( gserialized_is_empty(geom1) || gserialized_is_empty(geom2) )
+ PG_RETURN_NULL();
+
+ initGEOS(lwpgnotice, lwgeom_geos_error);
+
+ g1 = (GEOSGeometry *)POSTGIS2GEOS(geom1);
+ if ( 0 == g1 ) /* exception thrown at construction */
+ {
+ HANDLE_GEOS_ERROR("First argument geometry could not be converted to GEOS");
+ PG_RETURN_NULL();
+ }
+
+ g2 = (GEOSGeometry *)POSTGIS2GEOS(geom2);
+ if ( 0 == g2 ) /* exception thrown at construction */
+ {
+ HANDLE_GEOS_ERROR("Second argument geometry could not be converted to GEOS");
+ GEOSGeom_destroy(g1);
+ PG_RETURN_NULL();
+ }
+
+ if (densifyFrac <= 0.0)
+ {
+ retcode = GEOSFrechetDistance(g1, g2, &result);
+ }
+ else
+ {
+ retcode = GEOSFrechetDistanceDensify(g1, g2, densifyFrac, &result);
+ }
+
+ GEOSGeom_destroy(g1);
+ GEOSGeom_destroy(g2);
+
+ if (retcode == 0)
+ {
+ HANDLE_GEOS_ERROR("GEOSFrechetDistance");
+ PG_RETURN_NULL(); /*never get here */
+ }
+
+ PG_FREE_IF_COPY(geom1, 0);
+ PG_FREE_IF_COPY(geom2, 1);
+
+ PG_RETURN_FLOAT8(result);
+
+#endif /* POSTGIS_GEOS_VERSION >= 37 */
+}
+
/**
* @brief This is the final function for GeomUnion
* aggregate. Will have as input an array of Geometries.
Modified: trunk/postgis/postgis.sql.in
===================================================================
--- trunk/postgis/postgis.sql.in 2017-05-22 16:36:11 UTC (rev 15399)
+++ trunk/postgis/postgis.sql.in 2017-05-23 04:39:55 UTC (rev 15400)
@@ -3452,6 +3452,14 @@
LANGUAGE 'c' IMMUTABLE STRICT _PARALLEL
COST 100; -- Guessed cost
+-- Requires GEOS >= 3.7.0
+-- Availability: 2.4.0
+CREATE OR REPLACE FUNCTION ST_FrechetDistance(geom1 geometry, geom2 geometry, float8 default -1)
+ RETURNS FLOAT8
+ AS 'MODULE_PATHNAME', 'ST_FrechetDistance'
+ LANGUAGE 'c' IMMUTABLE STRICT _PARALLEL
+ COST 100; -- Guessed cost
+
-- PostGIS equivalent function: difference(geom1 geometry, geom2 geometry)
CREATE OR REPLACE FUNCTION ST_Difference(geom1 geometry, geom2 geometry)
RETURNS geometry
Modified: trunk/regress/Makefile.in
===================================================================
--- trunk/regress/Makefile.in 2017-05-22 16:36:11 UTC (rev 15399)
+++ trunk/regress/Makefile.in 2017-05-23 04:39:55 UTC (rev 15400)
@@ -167,6 +167,13 @@
regress_buffer_params
endif
+ifeq ($(shell expr $(POSTGIS_GEOS_VERSION) ">=" 37),1)
+ # GEOS-3.7 adds:
+ # ST_FrechetDistance
+ TESTS += \
+ frechet
+endif
+
ifeq ($(shell expr $(POSTGIS_GEOS_VERSION) ">=" 33),1)
# GEOS-3.3 adds:
# ST_RelateMatch, ST_IsValidDetail, ST_SharedPaths ,
Added: trunk/regress/frechet.sql
===================================================================
--- trunk/regress/frechet.sql (rev 0)
+++ trunk/regress/frechet.sql 2017-05-23 04:39:55 UTC (rev 15400)
@@ -0,0 +1,31 @@
+-- tests for Frechet distances
+
+-- linestring and linestring
+SELECT 'frechet_ls_ls', st_frechetdistance(
+ 'LINESTRING (0 0, 2 1)'::geometry
+ , 'LINESTRING (0 0, 2 0)'::geometry);
+-- 1.0
+
+-- other linestrings
+SELECT 'frechet_ls_ls_2', st_frechetdistance(
+ 'LINESTRING (0 0, 2 0)'::geometry,
+ 'LINESTRING (0 1, 1 2, 2 1)'::geometry);
+-- 2.23606797749979
+
+-- linestring and multipoint
+SELECT 'frechet_ls_mp', st_frechetdistance(
+ 'LINESTRING (0 0, 2 0)'::geometry,
+ 'MULTIPOINT (0 1, 1 0, 2 1)'::geometry);
+-- 1.0
+
+-- another linestring and linestring
+SELECT 'frechet_ls_ls_3', st_frechetdistance(
+ 'LINESTRING (0 0, 100 0)'::geometry,
+ 'LINESTRING (0 0, 50 50, 100 0)'::geometry);
+-- 70.7106781186548
+
+-- rechet with densification
+SELECT 'frechetdensify_ls_ls', st_frechetdistance(
+ 'LINESTRING (0 0, 100 0)'::geometry,
+ 'LINESTRING (0 0, 50 50, 100 0)'::geometry, 0.5);
+-- 50.0
Added: trunk/regress/frechet_expected
===================================================================
--- trunk/regress/frechet_expected (rev 0)
+++ trunk/regress/frechet_expected 2017-05-23 04:39:55 UTC (rev 15400)
@@ -0,0 +1,5 @@
+frechet_ls_ls|1
+frechet_ls_ls_2|2.23606797749979
+frechet_ls_mp|1
+frechet_ls_ls_3|70.7106781186548
+frechetdensify_ls_ls|50
Modified: trunk/utils/postgis_restore.pl.in
===================================================================
--- trunk/utils/postgis_restore.pl.in 2017-05-22 16:36:11 UTC (rev 15399)
+++ trunk/utils/postgis_restore.pl.in 2017-05-23 04:39:55 UTC (rev 15400)
@@ -899,6 +899,10 @@
COMMENT FUNCTION st_force_4d(geometry)
COMMENT FUNCTION st_force_collection(geometry)
COMMENT FUNCTION st_forcerhr(geometry)
+COMMENT FUNCTION st_frechetdistance(geom1 geometry,geom2 geometry)
+COMMENT FUNCTION st_frechetdistance(geom1 geometry,geom2 geometry,double precision)
+COMMENT FUNCTION st_frechetdistance(geometry,geometry)
+COMMENT FUNCTION st_frechetdistance(geometry,geometry,double precision)
COMMENT FUNCTION st_gdaldrivers(OUTidxinteger,OUTshort_nametext,OUTlong_nametext,OUTcreate_optionstext)
COMMENT FUNCTION st_geogfromtext(text)
COMMENT FUNCTION st_geogfromwkb(bytea)
More information about the postgis-tickets
mailing list