[SCM] PostGIS branch master updated. 3.5.0-13-g290fffd11
git at osgeo.org
git at osgeo.org
Tue Oct 1 01:46:04 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, master has been updated
via 290fffd11dac294431056e6d152098ac0afe60de (commit)
from 1d33935cd7586b00a66e5bd79c95882291fd2b30 (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 290fffd11dac294431056e6d152098ac0afe60de
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 master branch (3.6.0dev)
Includes regress tests
diff --git a/liblwgeom/measures.c b/liblwgeom/measures.c
index 74a25b212..2a1f73ec3 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 vertices, compared to mindistance which can be between two vertices.*/
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 705789cdc..3e01f5175 100644
--- a/regress/core/measures.sql
+++ b/regress/core/measures.sql
@@ -315,3 +315,15 @@ SELECT 'st_lineextend.3', ST_AsText(ST_SnapToGrid(ST_LineExtend('LINESTRING(0 0,
SELECT 'st_lineextend.4', ST_AsText(ST_SnapToGrid(ST_LineExtend('LINESTRING(0 0,1 1,1 1,1 1)'::geometry, 1), 0.001), 3);
SELECT 'st_lineextend.5', ST_AsText(ST_SnapToGrid(ST_LineExtend('LINESTRING EMPTY'::geometry, 1), 0.001), 3);
SELECT 'st_lineextend.6', ST_AsText(ST_SnapToGrid(ST_LineExtend('POINT EMPTY'::geometry, 1), 0.001), 3);
+
+-- #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 09878b4a0..e0b654476 100644
--- a/regress/core/measures_expected
+++ b/regress/core/measures_expected
@@ -101,3 +101,4 @@ st_lineextend.3|LINESTRING(0 0,1 1,1.707 1.707)
st_lineextend.4|LINESTRING(0 0,1 1,1.707 1.707)
st_lineextend.5|
ERROR: Argument must be LINESTRING geometry
+#5782|t
diff --git a/topology/test/regress/topogeo_addlinestring.sql b/topology/test/regress/topogeo_addlinestring.sql
index 6068bac30..79bdc4b84 100644
--- a/topology/test/regress/topogeo_addlinestring.sql
+++ b/topology/test/regress/topogeo_addlinestring.sql
@@ -514,3 +514,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:
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 +++++++++++++++++
6 files changed, 123 insertions(+), 7 deletions(-)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list