[SCM] PostGIS branch stable-3.3 updated. 3.3.7-3-gbb7665db5
git at osgeo.org
git at osgeo.org
Tue Oct 1 02:35:06 PDT 2024
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, stable-3.3 has been updated
via bb7665db5d7d56d1ffb8baa5ba84e85adf505d6f (commit)
from fbc9c5bb9bc6f8dbc3a4a732e8bedcfd06d49868 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit bb7665db5d7d56d1ffb8baa5ba84e85adf505d6f
Author: Sandro Santilli <strk at kbt.io>
Date: Mon Sep 30 16:40:19 2024 +0200
Improve robustness of min distance calculation
References #5782 in 3.3 branch (3.3.8dev)
Includes regress tests
diff --git a/NEWS b/NEWS
index dacc57dec..282898a8f 100644
--- a/NEWS
+++ b/NEWS
@@ -1,4 +1,4 @@
-PostGIS 3.3.8
+PostGIS 3.3.8dev
2024-xx-xx
* Bug Fixes and Enhancements *
@@ -6,6 +6,9 @@ PostGIS 3.3.8
- #5785, [raster] ST_MapAlgebra segfaults when expression references
a supernumerary rast argument (Dian M Fay)
+* Enhancements *
+
+ - #5782, Improve robustness of min distance calculation (Sandro Santilli)
PostGIS 3.3.7
2024-09-05
diff --git a/liblwgeom/measures.c b/liblwgeom/measures.c
index ac2ddac46..1e9ad4440 100644
--- a/liblwgeom/measures.c
+++ b/liblwgeom/measures.c
@@ -28,6 +28,9 @@
#include <string.h>
#include <stdlib.h>
+#include "../postgis_config.h"
+//#define POSTGIS_DEBUG_LEVEL 5
+
#include "measures.h"
#include "lwgeom_log.h"
@@ -344,8 +347,10 @@ lw_dist2d_recursive(const LWGEOM *lwg1, const LWGEOM *lwg2, DISTPTS *dl)
{
if (!lw_dist2d_distribute_bruteforce(g1, g2, dl))
return LW_FALSE;
+ LWDEBUGF(2, "Distance so far: %.15g (%.15g tolerated)", dl->distance, dl->tolerance);
if (dl->distance <= dl->tolerance && dl->mode == DIST_MIN)
return LW_TRUE; /*just a check if the answer is already given*/
+ LWDEBUG(2, "Not below tolerance yet");
}
}
}
@@ -1133,9 +1138,13 @@ lw_dist2d_pt_ptarray(const POINT2D *p, POINTARRAY *pa, DISTPTS *dl)
start = getPoint2d_cp(pa, 0);
+ LWDEBUG(2, "lw_dist2d_pt_ptarray enter");
+
if (!lw_dist2d_pt_pt(p, start, dl))
return LW_FALSE;
+ LWDEBUGF(2, "lw_dist2d_pt_ptarray: distance from first point ? : %.15g", dl->distance);
+
for (uint32_t t = 1; t < pa->npoints; t++)
{
dl->twisted = twist;
@@ -1143,6 +1152,8 @@ lw_dist2d_pt_ptarray(const POINT2D *p, POINTARRAY *pa, DISTPTS *dl)
if (!lw_dist2d_pt_seg(p, start, end, dl))
return LW_FALSE;
+ LWDEBUGF(2, "lw_dist2d_pt_ptarray: distance from seg %lu ? : %.15g", t, dl->distance);
+
if (dl->distance <= dl->tolerance && dl->mode == DIST_MIN)
return LW_TRUE; /*just a check if the answer is already given*/
start = end;
@@ -2304,11 +2315,17 @@ To get this points it was necessary to change and it also showed to be about 10%
int
lw_dist2d_pt_seg(const POINT2D *p, const POINT2D *A, const POINT2D *B, DISTPTS *dl)
{
- POINT2D c;
double r;
+
+ LWDEBUG(2, "lw_dist2d_pt_seg called");
+
/*if start==end, then use pt distance */
if ((A->x == B->x) && (A->y == B->y))
+ {
+ LWDEBUG(2, "lw_dist2d_pt_seg found first and last segment points being the same");
return lw_dist2d_pt_pt(p, A, dl);
+ }
+
/*
* otherwise, we use comp.graphics.algorithms
@@ -2328,6 +2345,8 @@ lw_dist2d_pt_seg(const POINT2D *p, const POINT2D *A, const POINT2D *B, DISTPTS *
r = ((p->x - A->x) * (B->x - A->x) + (p->y - A->y) * (B->y - A->y)) /
((B->x - A->x) * (B->x - A->x) + (B->y - A->y) * (B->y - A->y));
+ LWDEBUGF(2, "lw_dist2d_pt_seg found r = %.15g", r);
+
/*This is for finding the maxdistance.
the maxdistance have to be between two vertexes, compared to mindistance which can be between two vertexes.*/
if (dl->mode == DIST_MAX)
@@ -2351,12 +2370,41 @@ lw_dist2d_pt_seg(const POINT2D *p, const POINT2D *A, const POINT2D *B, DISTPTS *
dl->p2 = *p;
}
- /*If the projection of point p on the segment is between A and B
- then we find that "point on segment" and send it to lw_dist2d_pt_pt*/
- c.x = A->x + r * (B->x - A->x);
- c.y = A->y + r * (B->y - A->y);
- return lw_dist2d_pt_pt(p, &c, dl);
+ /*
+ (2)
+ (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
+ s = -----------------------------
+ L^2
+
+ Then the distance from C to P = |s|*L.
+ */
+
+ double s = ((A->y - p->y) * (B->x - A->x) - (A->x - p->x) * (B->y - A->y)) /
+ ((B->x - A->x) * (B->x - A->x) + (B->y - A->y) * (B->y - A->y));
+
+ double dist = fabs(s) * sqrt(((B->x - A->x) * (B->x - A->x) + (B->y - A->y) * (B->y - A->y)));
+ if ( dist < dl->distance )
+ {
+ dl->distance = dist;
+ {
+ POINT2D c;
+ c.x = A->x + r * (B->x - A->x);
+ c.y = A->y + r * (B->y - A->y);
+ if (dl->twisted > 0)
+ {
+ dl->p1 = *p;
+ dl->p2 = c;
+ }
+ else
+ {
+ dl->p1 = c;
+ dl->p2 = *p;
+ }
+ }
+ }
+
+ return LW_TRUE;
}
/** Compares incoming points and stores the points closest to each other or most far away from each other depending on
diff --git a/regress/core/knn_recheck.sql b/regress/core/knn_recheck.sql
index 313bb80e3..f08b7f0d6 100644
--- a/regress/core/knn_recheck.sql
+++ b/regress/core/knn_recheck.sql
@@ -1,4 +1,4 @@
--- create table
+-- create table
CREATE TABLE knn_recheck_geom(gid serial primary key, geom geometry);
INSERT INTO knn_recheck_geom(gid,geom)
SELECT ROW_NUMBER() OVER(ORDER BY x,y) AS gid, ST_Point(x*0.777,y*0.887) As geom
@@ -227,3 +227,15 @@ FROM test_wo ORDER BY geo <->
('0101000020E610000092054CE0D6DDE5BFCDCCCCCCCCAC4A40'::geometry);
DROP TABLE test_wo;
set enable_seqscan to default;
+
+-- #5782
+CREATE TABLE t5782 ( l text, g geometry );
+INSERT INTO t5782 VALUES
+ ('A', 'LINESTRING(18.00678831099686 69.0404811833497,18.006784630996860 69.04045431334970,18.00677727099686 69.0404005833497)'),
+ ('B', 'LINESTRING(18.00677727099686 69.0404005833497,18.006780950996863 69.04042744334969,18.00678831099686 69.0404811833497)');
+CREATE INDEX ON t5782 USING GIST(g);
+ANALYZE t5782;
+SET enable_seqscan = false;
+SELECT '#5782', l FROM t5782 ORDER BY g <-> 'POINT(18.006691126034692 69.04048768506776)'::geometry;
+DROP TABLE t5782;
+SET enable_seqscan to default;
diff --git a/regress/core/knn_recheck_expected b/regress/core/knn_recheck_expected
index dda412123..226f99ed7 100644
--- a/regress/core/knn_recheck_expected
+++ b/regress/core/knn_recheck_expected
@@ -105,3 +105,5 @@
#3573|8
#3418|0.3318238|0.3318238
#3418|0.5500000|0.5500000
+#5782|A
+#5782|B
diff --git a/regress/core/measures.sql b/regress/core/measures.sql
index 58072ca67..e57abade3 100644
--- a/regress/core/measures.sql
+++ b/regress/core/measures.sql
@@ -290,3 +290,15 @@ SELECT '#4328.3', ST_Intersects('TIN(((0 0,1 0,0 1,0 0)))'::geometry, 'TRIANGLE(
SELECT '#4328.4', ST_Intersects('TIN(((0 0,1 0,0 1,0 0)))'::geometry, 'POLYGON((.1 .1, .2 .2, .2 .1, .1 .1))'::geometry), ST_3DIntersects('TIN(((0 0,1 0,0 1,0 0)))'::geometry, 'POLYGON((.1 .1, .2 .2, .2 .1, .1 .1))'::geometry);
SELECT '#4328.5', ST_Intersects('TIN(((0 0,3 0,0 3,0 0)))'::geometry, 'CIRCULARSTRING(1.1 1.1, 1.2 1.2, 1.2 1.1)'::geometry), ST_3DIntersects('TIN(((0 0,3 0,0 3,0 0)))'::geometry, 'CIRCULARSTRING(1.1 1.1, 1.2 1.2, 1.2 1.1)'::geometry);
SELECT '#4328.6', ST_Intersects('TIN(((0 0,3 0,0 3,0 0)))'::geometry, 'CURVEPOLYGON(CIRCULARSTRING(1.1 1.1, 1.2 1.2, 1.2 1.1, 1.2 1.2, 1.1 1.1))'::geometry), ST_3DIntersects('TIN(((0 0,3 0,0 3,0 0)))'::geometry, 'CURVEPOLYGON(CIRCULARSTRING(1.1 1.1, 1.2 1.2, 1.2 1.1, 1.2 1.2, 1.1 1.1))'::geometry);
+
+-- #5782
+WITH inp AS (
+ SELECT
+ 'LINESTRING(18.00678831099686 69.0404811833497,18.006784630996860 69.04045431334970,18.00677727099686 69.0404005833497)'::geometry a,
+ 'LINESTRING(18.00677727099686 69.0404005833497,18.006780950996863 69.04042744334969,18.00678831099686 69.0404811833497)'::geometry b,
+ 'POINT(18.006691126034692 69.04048768506776)'::geometry q
+)
+SELECT
+ '#5782',
+ ST_Distance(a,q) < ST_Distance(b,q)
+FROM inp;
diff --git a/regress/core/measures_expected b/regress/core/measures_expected
index 7ff9f1307..babdd90fc 100644
--- a/regress/core/measures_expected
+++ b/regress/core/measures_expected
@@ -79,3 +79,4 @@ NOTICE: One or both of the geometries is missing z-value. The unknown z-value w
#4328.5|t|t
NOTICE: One or both of the geometries is missing z-value. The unknown z-value will be regarded as "any value"
#4328.6|t|t
+#5782|t
diff --git a/topology/test/regress/topogeo_addlinestring.sql b/topology/test/regress/topogeo_addlinestring.sql
index 8ddf5c914..485ccb9a5 100644
--- a/topology/test/regress/topogeo_addlinestring.sql
+++ b/topology/test/regress/topogeo_addlinestring.sql
@@ -513,3 +513,44 @@ SELECT 't5568', 'invalidities at start', array_agg((v)) FROM validatetopology('t
SELECT NULL FROM topology.TopoGeo_addLinestring('t5568','01020000000200000084CBFA5C7A7824405CC705259CEE4D407A6873CA73782440DE38B01D9CEE4D40');
SELECT 't5568', 'invalidities at end', array_agg(error) FROM validatetopology('t5568') v;
ROLLBACK;
+
+
+
+-- See https://trac.osgeo.org/postgis/ticket/5782
+BEGIN;
+SELECT NULL FROM topology.CreateTopology ('t5782');
+SELECT NULL FROM topology.TopoGeo_addLinestring('t5782',
+'LINESTRING(
+18.006852310996862 69.0403992633497,
+18.00677727099686 69.0404005833497,
+18.006780950996863 69.04042744334969,
+18.00678831099686 69.0404811833497,
+18.00686335099686 69.04047986334969,
+18.006864423681307 69.04048768506776)'
+);
+SELECT NULL FROM topology.TopoGeo_addLinestring('t5782',
+'LINESTRING(18.006864423681307 69.04048768506776,
+18.00686335099686 69.04047986334969,
+18.00678831099686 69.0404811833497,
+18.00678463099686 69.0404543133497,
+18.00677727099686 69.0404005833497,
+18.006852310996862 69.0403992633497,
+18.00684863099686 69.04037239334968,
+18.00737395099686 69.04036317334969,
+18.00737333099686 69.0403586833497)'
+);
+SELECT '#5782', 'valid_before', * FROM topology.ValidateTopology('t5782');
+SELECT NULL FROM topology.TopoGeo_addLinestring('t5782',
+'LINESTRING(18.00737333099686 69.0403586833497,
+18.00721192099686 69.0403628733497,
+18.00705714099686 69.0403605633497,
+18.00689347099686 69.0403665833497,
+18.00667774099686 69.0403714433497,
+18.00653346099686 69.04039085334969,
+18.00647305099686 69.0403818633497,
+18.00657415099686 69.0404371833497,
+18.00668981099686 69.04048704334969,
+18.006691126034692 69.04048768506776)'
+);
+SELECT '#5782', 'valid_after', * FROM topology.ValidateTopology('t5782');
+ROLLBACK;
-----------------------------------------------------------------------
Summary of changes:
NEWS | 5 ++-
liblwgeom/measures.c | 60 ++++++++++++++++++++++---
regress/core/knn_recheck.sql | 14 +++++-
regress/core/knn_recheck_expected | 2 +
regress/core/measures.sql | 12 +++++
regress/core/measures_expected | 1 +
topology/test/regress/topogeo_addlinestring.sql | 41 +++++++++++++++++
7 files changed, 127 insertions(+), 8 deletions(-)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list