Uninterruptible slow geo_ops.c
Hi,
A customer of ours hit some very slow code while running the
@>(polygon, polygon) operator with some big polygons. I'm not familiar
with this stuff but I think the problem is that the algorithm converges
too slowly to a solution and also has some pretty expensive calls
somewhere. (Perhaps there is also a problem that the algorithm *never*
converges for some inputs ...)
While I'm not familiar with the code itself, and can't post the exact
slow query just yet, I have noticed that it is missing a
CHECK_FOR_INTERRUPTS() call to enable cancelling the slow query. I'd
backpatch this all the way back. (The exact issue they hit is mutual
recursion between touched_lseg_between_poly and lseg_between_poly.
Since the latter also recurses on itself, the best way forward seem to
add a check for interrupts in the loop there.)
I will follow up on the actual slowness later, as warranted.
--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Attachments:
geo_ops-int.patchtext/x-diff; charset=us-asciiDownload
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index 6ef420d..77871b1 100644
--- a/src/backend/utils/adt/geo_ops.c
+++ b/src/backend/utils/adt/geo_ops.c
@@ -20,6 +20,7 @@
#include <ctype.h>
#include "libpq/pqformat.h"
+#include "miscadmin.h"
#include "utils/builtins.h"
#include "utils/geo_decls.h"
@@ -3894,6 +3895,8 @@ lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
{
Point *interpt;
+ CHECK_FOR_INTERRUPTS();
+
s.p[1] = poly->p[i];
if (on_ps_internal(t.p, &s))
On 11/12/15 18:48, Alvaro Herrera wrote:
Hi,
A customer of ours hit some very slow code while running the
@>(polygon, polygon) operator with some big polygons. I'm not familiar
with this stuff but I think the problem is that the algorithm converges
too slowly to a solution and also has some pretty expensive calls
somewhere. (Perhaps there is also a problem that the algorithm *never*
converges for some inputs ...)While I'm not familiar with the code itself, and can't post the exact
slow query just yet, I have noticed that it is missing a
CHECK_FOR_INTERRUPTS() call to enable cancelling the slow query. I'd
backpatch this all the way back. (The exact issue they hit is mutual
recursion between touched_lseg_between_poly and lseg_between_poly.
Since the latter also recurses on itself, the best way forward seem to
add a check for interrupts in the loop there.)I will follow up on the actual slowness later, as warranted.
I would add that it was not simply a slow computation, but more probably they hit a case where the algorithm doesn't converge at all.
I've killed it manually by calling ProcessInterrupts() through gdb after 7 days and half of CPU time (100% of one CPU).
The server CPU is an Intel(R) Xeon(R) CPU E5-2660 v2 @ 2.20GHz.
The query doesn't involve any table and is a simple call of @>(polygon, polygon) operator.
SELECT polygon 'poligon literal with 522 points' @> polygon 'poligon box'
I'm checking if we can share the full query.
Regards,
Marco
--
Marco Nenciarini - 2ndQuadrant Italy
PostgreSQL Training, Services and Support
marco.nenciarini@2ndQuadrant.it | www.2ndQuadrant.it
On 11/12/15 19:18, Marco Nenciarini wrote:
On 11/12/15 18:48, Alvaro Herrera wrote:
Hi,
A customer of ours hit some very slow code while running the
@>(polygon, polygon) operator with some big polygons. I'm not familiar
with this stuff but I think the problem is that the algorithm converges
too slowly to a solution and also has some pretty expensive calls
somewhere. (Perhaps there is also a problem that the algorithm *never*
converges for some inputs ...)While I'm not familiar with the code itself, and can't post the exact
slow query just yet, I have noticed that it is missing a
CHECK_FOR_INTERRUPTS() call to enable cancelling the slow query. I'd
backpatch this all the way back. (The exact issue they hit is mutual
recursion between touched_lseg_between_poly and lseg_between_poly.
Since the latter also recurses on itself, the best way forward seem to
add a check for interrupts in the loop there.)I will follow up on the actual slowness later, as warranted.
I would add that it was not simply a slow computation, but more probably they hit a case where the algorithm doesn't converge at all.
I've killed it manually by calling ProcessInterrupts() through gdb after 7 days and half of CPU time (100% of one CPU).
The server CPU is an Intel(R) Xeon(R) CPU E5-2660 v2 @ 2.20GHz.The query doesn't involve any table and is a simple call of @>(polygon, polygon) operator.
SELECT polygon 'poligon literal with 522 points' @> polygon 'poligon box'
I'm checking if we can share the full query.
The full query is attached.
Regards,
Marco
--
Marco Nenciarini - 2ndQuadrant Italy
PostgreSQL Training, Services and Support
marco.nenciarini@2ndQuadrant.it | www.2ndQuadrant.it
Attachments:
Alvaro Herrera wrote:
While I'm not familiar with the code itself, and can't post the exact
slow query just yet, I have noticed that it is missing a
CHECK_FOR_INTERRUPTS() call to enable cancelling the slow query. I'd
backpatch this all the way back. (The exact issue they hit is mutual
recursion between touched_lseg_between_poly and lseg_between_poly.
Since the latter also recurses on itself, the best way forward seem to
add a check for interrupts in the loop there.)
Pushed this part.
--
�lvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
[Replying to an old thread...]
A customer of ours hit some very slow code while running the
@>(polygon, polygon) operator with some big polygons. I'm not familiar
with this stuff but I think the problem is that the algorithm converges
too slowly to a solution and also has some pretty expensive calls
somewhere. (Perhaps there is also a problem that the algorithm *never*
converges for some inputs ...)
I believe there is a simple flaw on the algorithm that causes it loop
endlessly. It should stop looking at the other segments of the
polygon after finding the touching one. The attached patch fixes the
issue for the query posted to this thread. I suggest backpacking the
fix.
There are many code quality issues and bugs like this still unresolved
on geo_ops.c. I am trying to improve it. Any help appreciated:
Attachments:
0001-polygon-contains-lseg-loop-fix-v00.patchapplication/octet-stream; name=0001-polygon-contains-lseg-loop-fix-v00.patchDownload
From d792dca0cb25cc10f545427fe08b8acf171308e4 Mon Sep 17 00:00:00 2001
From: Emre Hasegeli <emre@hasegeli.com>
Date: Sun, 10 Dec 2017 15:27:28 +0100
Subject: [PATCH] polygon-contains-lseg-loop-fix-v00
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Fix endless loop on polygon @> polygon
A simple logic flaw on the algorithm was causing polygon contains
polygon operator to loop endlessly. The algorithm iterates through
the segments of the polygon and checks if they touch or intersect
with each other. When they do touch or intersect on the inner loop,
the result is found, but the algorithm was continuing to check the rest
of the segments.
The issue reported to the mailing list by Álvaro Herrera, and the test
case is posted by Marco Nenciarini.
Discussion: 20151211174826.GF2762@alvherre.pgsql
---
src/backend/utils/adt/geo_ops.c | 12 ++++++++++--
src/test/regress/expected/polygon.out | 6 ++++++
src/test/regress/sql/polygon.sql | 2 ++
3 files changed, 18 insertions(+), 2 deletions(-)
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index 9dbe5db2b2..826566739b 100644
--- a/src/backend/utils/adt/geo_ops.c
+++ b/src/backend/utils/adt/geo_ops.c
@@ -3874,37 +3874,45 @@ lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
s.p[1] = poly->p[i];
if (on_ps_internal(t.p, &s))
{
if (on_ps_internal(t.p + 1, &s))
return true; /* t is contained by s */
/* Y-cross */
res = touched_lseg_inside_poly(t.p, t.p + 1, &s, poly, i + 1);
+
+ break;
}
- else if (on_ps_internal(t.p + 1, &s))
+
+ if (on_ps_internal(t.p + 1, &s))
{
/* Y-cross */
res = touched_lseg_inside_poly(t.p + 1, t.p, &s, poly, i + 1);
+
+ break;
}
- else if ((interpt = lseg_interpt_internal(&t, &s)) != NULL)
+
+ if ((interpt = lseg_interpt_internal(&t, &s)) != NULL)
{
/*
* segments are X-crossing, go to check each subsegment
*/
intersection = true;
res = lseg_inside_poly(t.p, interpt, poly, i + 1);
if (res)
res = lseg_inside_poly(t.p + 1, interpt, poly, i + 1);
pfree(interpt);
+
+ break;
}
s.p[0] = s.p[1];
}
if (res && !intersection)
{
Point p;
/*
diff --git a/src/test/regress/expected/polygon.out b/src/test/regress/expected/polygon.out
index 2361274f9e..9523fe1ec7 100644
--- a/src/test/regress/expected/polygon.out
+++ b/src/test/regress/expected/polygon.out
@@ -177,20 +177,26 @@ SELECT '((1,1),(1,4),(5,4),(5,3),(2,3),(2,2),(5,2),(5,1))'::polygon @> '((3,2),(
-------
f
(1 row)
SELECT '((0,0),(0,3),(3,3),(3,0))'::polygon @> '((2,1),(2,2),(3,2),(3,1))'::polygon AS "true";
true
------
t
(1 row)
+SELECT polygon '((-880000000,419013470),(-880000000,419007240),(-880000000,419007240),(-880000000,418987250),(-880000000,418987250),(-880000000,418970240),(-880000000,418970240),(-880000000,418950990),(-880000000,418950990),(-880000000,418923770),(-880000000,418923770),(-880000000,418917630),(-880000000,418917630),(-880000000,418912100),(-880000000,418912100),(-880000000,418900410),(-880000000,418900410),(-880000000,418895420),(-880000000,418895420),(-880000000,418893450),(-880000000,418893450),(-880000000,418859340),(-880000000,418859340),(-880000000,418842280),(-880000000,418842280),(-880000000,418824820),(-880000000,418824820),(-880000000,418819820),(-880000000,418819820),(-880000000,418812320),(-880000000,418812320),(-880000000,418781690),(-880000000,418781690),(-880000000,418750360),(-880000000,418750360),(-880000000,418750000),(-880000000,418750000),(-879957280,418750000),(-879957280,418750000),(-879946700,418750000),(-879946700,418750000),(-879932880,418750000),(-879932880,418750000),(-879921140,418750000),(-879921140,418750000),(-879901800,418750000),(-879901800,418750000),(-879884730,418750000),(-879884730,418750000),(-879869770,418750000),(-879869770,418750000),(-879853620,418750000),(-879853620,418750000),(-879838680,418750000),(-879838680,418750000),(-879820670,418750000),(-879820670,418750000),(-879803830,418750000),(-879803830,418750000),(-879788600,418750000),(-879788600,418750000),(-879771820,418750000),(-879771820,418750000),(-879755740,418750000),(-879755740,418750000),(-879738740,418750000),(-879738740,418750000),(-879738580,418750000),(-879738580,418750000),(-879702620,418750000),(-879702620,418750000),(-879687560,418750000),(-879687560,418750000),(-879617590,418750000),(-879617590,418750000),(-879614270,418750000),(-879614270,418750000),(-879611560,418750000),(-89611560,418750000),(-879551870,418750000),(-879551870,418750000),(-879544600,418750000),(-879544600,418750000),(-879531980,418750000),(-879531980,418750000),(-879519330,418750000),(-879519330,418750000),(-879507350,418750000),(-879507350,418750000),(-879494370,418750000),(-879494370,418750000),(-879481570,418750000),(-879481570,418750000),(-879469050,418750000),(-879469050,418750000),(-879457200,418750000),(-879457200,418750000),(-879446660,418750000),(-879446660,418750000),(-879435070,418750000),(-879435070,418750000),(-879423630,418750000),(-879423630,418750000),(-879411030,418750000),(-879411030,418750000),(-879397520,418750000),(-879397520,418750000),(-879385310,418750000),(-879385310,418750000),(-879364550,418750000),(-879364550,418750000),(-879347030,418750000),(-879347030,418750000),(-879336090,418750000),(-879336090,418750000),(-879323380,418750000),(-879323380,418750000),(-87932310,418750000),(-879312310,418750000),(-879300290,418750000),(-879300290,418750000),(-879288280,418750000),(-879288280,418750000),(-879256170,418750000),(-879256170,418750000),(-879245250,418750000),(-879245250,418750000),(-879230540,418750000),(-879230540,418750000),(-879223070,418750000),(-879223070,418750000),(-879204650,418750000),(-879204650,418750000),(-879191420,418750000),(-879191420,418750000),(-879184480,418750000),(-879184480,418750000),(-879166660,418750000),(-879166660,418750000),(-879143370,418750000),(-879143370,418750000),(-879130620,418750000),(-879130620,418750000),(-879124800,418750000),(-879124800,418750000),(-879102120,418750000),(-879102120,418750000),(-879089020,418750000),(-879089020,418750000),(-879074480,418750000),(-879074480,418750000),(-879061510,418750000),(-879061510,418750000),(-879050380,418750000),(-879050380,418750000),(-879037450,418750000),(-87903740,418750000),(-879024420,418750000),(-879024420,418750000),(-879011310,418750000),(-879011310,418750000),(-878996680,418750000),(-878996680,418750000),(-878984750,418750000),(-878984750,418750000),(-878973830,418750000),(-878973830,418750000),(-878971200,418750000),(-878971200,418750000),(-878960420,418750000),(-878960420,418750000),(-878950440,418750000),(-878950440,418750000),(-878941460,418750000),(-878941460,418750000),(-878938940,418750000),(-878938940,418750000),(-878926680,418750000),(-878926680,418750000),(-878829580,418750000),(-878829580,418750000),(-878795610,418750000),(-878795610,418750000),(-878788760,418750000),(-878788760,418750000),(-878779580,418750000),(-878779580,418750000),(-878754070,418750000),(-878754070,418750000),(-878750000,418750000),(-878750000,418750000),(-878750000,418752180),(-878750000,418752180),(-878750000,418760470),(-878750000,418760470),(-878750000,18769720),(-878750000,418769720),(-878750000,418779190),(-878750000,418779190),(-878750000,418786480),(-878750000,418786480),(-878750000,418790300),(-878750000,418790300),(-878750000,418798740),(-878750000,418798740),(-878750000,418816300),(-878750000,418816300),(-878750000,418844860),(-878750000,418844860),(-878750000,418865960),(-878750000,418865960),(-878750000,418883640),(-878750000,418883640),(-878750000,418908300),(-878750000,418908300),(-878750000,418970530),(-878750000,418970530),(-878750000,418981300),(-878750000,418981300),(-878750000,418999260),(-878750000,418999260),(-878750000,419033610),(-878750000,419033610),(-878750000,419054300),(-878750000,419054300),(-878750000,419061710),(-878750000,419061710),(-878750000,419073300),(-878750000,419073300),(-878750000,419075570),(-878750000,419075570),(-878750000,419107300),(-878750000,419107300),(-878750000,419147630),(-878750000,41947630),(-878750000,419183810),(-878750000,419183810),(-878750000,419193030),(-878750000,419193030),(-878750000,419211120),(-878750000,419211120),(-878750000,419221010),(-878750000,419221010),(-878750000,419249210),(-878750000,419249210),(-878750000,419258180),(-878750000,419258180),(-878750000,419274580),(-878750000,419274580),(-878750000,419280160),(-878750000,419280160),(-878750000,419282060),(-878750000,419282060),(-878750000,419283210),(-878750000,419283210),(-878750000,419298260),(-878750000,419298260),(-878750000,419310570),(-878750000,419310570),(-878750000,419328300),(-878750000,419328300),(-878750000,419346300),(-878750000,419346300),(-878750000,419362580),(-878750000,419362580),(-878750000,419379090),(-878750000,419379090),(-878750000,419394980),(-878750000,419394980),(-878750000,419401000),(-878750000,419401000),(-878750000,419419300),(-878750000,419419300),(-878750000,419437300),(-878750000,419437300),(-878750000,419453300),(-878750000,419453300),(-878750000,419472300),(-878750000,419472300),(-878750000,419498300),(-878750000,419498300),(-878750000,419559040),(-878750000,419559040),(-878750000,419582630),(-878750000,419582630),(-878750000,419598600),(-878750000,419598600),(-878750000,419622410),(-878750000,419622410),(-878750000,419626020),(-878750000,419626020),(-878750000,419640970),(-878750000,419640970),(-878750000,419655930),(-878750000,419655930),(-878750000,419730790),(-878750000,419730790),(-878750000,419823550),(-878750000,419823550),(-878750000,419823890),(-878750000,419823890),(-878750000,419898030),(-878750000,419898030),(-878750000,419916320),(-878750000,419916320),(-878750000,419935610),(-878750000,419935610),(-878750000,419950660),(-878750000,419950660),(-878750000,419957710),(-878750000,419957710),(-878750000,419959690),(-878750000,419959690),(-878750000,419988310),(-878750000,419988310),(-878750000,419997300),(-878750000,419997300),(-878750000,420000000),(-878750000,420000000),(-878796170,420000000),(-878796170,420000000),(-878818300,420000000),(-878818300,420000000),(-878820850,420000000),(-878820850,420000000),(-878823480,420000000),(-878823480,420000000),(-878824760,420000000),(-878824760,420000000),(-878846130,420000000),(-878846130,420000000),(-878940170,420000000),(-878940170,420000000),(-878957520,420000000),(-878957520,420000000),(-879050000,420000000),(-879050000,420000000),(-879050680,420000000),(-879050680,420000000),(-879198660,420000000),(-879198660,420000000),(-879353110,420000000),(-879353110,420000000),(-879401990,420000000),(-879401990,420000000),(-879419650,420000000),(-879419650,420000000),(-879426990,420000000),(-879426990,420000000),(-879493560,420000000),(-879493560,420000000),(-879551870,420000000),(-879551870,420000000),(-879593170,420000000),(-879593170,420000000),(-879697840,420000000),(-879697840,420000000),(-879774750,420000000),(-879774750,420000000),(-879776710,420000000),(-879776710,420000000),(-879787770,420000000),(-879787770,420000000),(-879793080,420000000),(-879793080,420000000),(-879800680,420000000),(-879800680,420000000),(-879819820,420000000),(-879819820,420000000),(-879829680,420000000),(-879829680,420000000),(-879843500,420000000),(-879843500,420000000),(-879851680,420000000),(-879851680,420000000),(-879862570,420000000),(-879862570,420000000),(-879872680,420000000),(-879872680,420000000),(-879882290,420000000),(-879882290,420000000),(-879900290,420000000),(-879900290,420000000),(-879916020,420000000),(-879916020,420000000),(-879922620,420000000),(-879922620,420000000),(-879928780,420000000),(-879928780,420000000),(-879941520,420000000),(-879941520,420000000),(-879976180,420000000),(-879976180,420000000),(-880000000,420000000),(-880000000,420000000),(-880000000,419999750),(-880000000,419999750),(-880000000,419991890),(-880000000,419991890),(-880000000,419984270),(-880000000,419984270),(-880000000,419976010),(-880000000,419976010),(-880000000,419968610),(-880000000,419968610),(-880000000,419960980),(-880000000,419960980),(-880000000,419952750),(-880000000,419952750),(-880000000,419946490),(-880000000,419946490),(-880000000,419928250),(-880000000,419928250),(-880000000,419880720),(-880000000,419880720),(-880000000,419836270),(-880000000,419836270),(-880000000,419806440),(-880000000,419806440),(-880000000,419799470),(-880000000,419799470),(-880000000,419788040),(-880000000,419788040),(-880000000,419720125),(-880000000,419720125),(-880000000,419713973),(-880000000,419713973),(-880000000,419698630),(-880000000,419698630),(-880000000,419690110),(-880000000,419690110),(-880000000,419668360),(-880000000,419668360),(-880000000,419655290),(-880000000,419655290),(-880000000,419634540),(-880000000,419634540),(-880000000,419626370),(-880000000,419626370),(-880000000,419605310),(-880000000,419605310),(-880000000,419596260),(-880000000,419596260),(-880000000,419588180),(-880000000,419588180),(-880000000,419579330),(-880000000,419579330),(-880000000,419569810),(-880000000,419569810),(-880000000,419560780),(-880000000,419560780),(-880000000,419551140),(-880000000,419551140),(-880000000,419543610),(-880000000,419543610),(-880000000,419533820),(-880000000,419533820),(-880000000,419524880),(-880000000,419524880),(-880000000,419475170),(-880000000,419475170),(-880000000,419447260),(-880000000,419447260),(-880000000,419423860),(-880000000,419423860),(-880000000,419414890),(-880000000,419414890),(-880000000,419369550),(-880000000,419369550),(-880000000,419335010),(-880000000,419335010),(-880000000,419322290),(-880000000,419322290),(-880000000,419313350),(-880000000,419313350),(-880000000,419306580),(-880000000,419306580),(-880000000,419290310),(-880000000,419290310),(-880000000,419289890),(-880000000,419289890),(-880000000,419272270),(-880000000,419272270),(-880000000,419264970),(-880000000,419264970),(-880000000,419255280),(-880000000,419255280),(-880000000,419240670),(-880000000,419240670),(-880000000,419236360),(-880000000,419236360),(-880000000,419221620),(-880000000,419221620),(-880000000,419218290),(-880000000,419218290),(-880000000,419195290),(-880000000,419195290),(-880000000,419154230),(-880000000,419154230),(-880000000,419142830),(-880000000,419142830),(-880000000,419133270),(-880000000,419133270),(-880000000,419107450),(-880000000,419107450),(-880000000,419087030),(-880000000,419087030),(-880000000,419077760),(-880000000,419077760),(-880000000,419077280),(-880000000,419077280),(-880000000,419064320),(-880000000,419064320),(-880000000,419056150),(-880000000,419056150),(-880000000,419048300),(-880000000,419048300),(-880000000,419034850),(-880000000,419034850),(-880000000,419023420),(-880000000,419023420),(-880000000,419013470))' @> polygon '((-880000000,418750000),(-878750000,418750000),(-878750000,420000000),(-880000000,420000000))' AS "true";
+ true
+------
+ t
+(1 row)
+
-- same
SELECT polygon '(2.0,0.0),(2.0,4.0),(0.0,0.0)' ~= polygon '(3.0,1.0),(3.0,3.0),(1.0,0.0)' AS false;
false
-------
f
(1 row)
-- overlap
SELECT polygon '(2.0,0.0),(2.0,4.0),(0.0,0.0)' && polygon '(3.0,1.0),(3.0,3.0),(1.0,0.0)' AS true;
true
diff --git a/src/test/regress/sql/polygon.sql b/src/test/regress/sql/polygon.sql
index 7ac8079465..80d2bf765a 100644
--- a/src/test/regress/sql/polygon.sql
+++ b/src/test/regress/sql/polygon.sql
@@ -92,20 +92,22 @@ SELECT polygon '(2.0,0.0),(2.0,4.0),(0.0,0.0)' <@ polygon '(3.0,1.0),(3.0,3.0),(
SELECT polygon '(2.0,0.0),(2.0,4.0),(0.0,0.0)' @> polygon '(3.0,1.0),(3.0,3.0),(1.0,0.0)' AS false;
SELECT '((0,4),(6,4),(1,2),(6,0),(0,0))'::polygon @> '((2,1),(2,3),(3,3),(3,1))'::polygon AS "false";
SELECT '((0,4),(6,4),(3,2),(6,0),(0,0))'::polygon @> '((2,1),(2,3),(3,3),(3,1))'::polygon AS "true";
SELECT '((1,1),(1,4),(5,4),(5,3),(2,3),(2,2),(5,2),(5,1))'::polygon @> '((3,2),(3,3),(4,3),(4,2))'::polygon AS "false";
SELECT '((0,0),(0,3),(3,3),(3,0))'::polygon @> '((2,1),(2,2),(3,2),(3,1))'::polygon AS "true";
+SELECT polygon '((-880000000,419013470),(-880000000,419007240),(-880000000,419007240),(-880000000,418987250),(-880000000,418987250),(-880000000,418970240),(-880000000,418970240),(-880000000,418950990),(-880000000,418950990),(-880000000,418923770),(-880000000,418923770),(-880000000,418917630),(-880000000,418917630),(-880000000,418912100),(-880000000,418912100),(-880000000,418900410),(-880000000,418900410),(-880000000,418895420),(-880000000,418895420),(-880000000,418893450),(-880000000,418893450),(-880000000,418859340),(-880000000,418859340),(-880000000,418842280),(-880000000,418842280),(-880000000,418824820),(-880000000,418824820),(-880000000,418819820),(-880000000,418819820),(-880000000,418812320),(-880000000,418812320),(-880000000,418781690),(-880000000,418781690),(-880000000,418750360),(-880000000,418750360),(-880000000,418750000),(-880000000,418750000),(-879957280,418750000),(-879957280,418750000),(-879946700,418750000),(-879946700,418750000),(-879932880,418750000),(-879932880,418750000),(-879921140,418750000),(-879921140,418750000),(-879901800,418750000),(-879901800,418750000),(-879884730,418750000),(-879884730,418750000),(-879869770,418750000),(-879869770,418750000),(-879853620,418750000),(-879853620,418750000),(-879838680,418750000),(-879838680,418750000),(-879820670,418750000),(-879820670,418750000),(-879803830,418750000),(-879803830,418750000),(-879788600,418750000),(-879788600,418750000),(-879771820,418750000),(-879771820,418750000),(-879755740,418750000),(-879755740,418750000),(-879738740,418750000),(-879738740,418750000),(-879738580,418750000),(-879738580,418750000),(-879702620,418750000),(-879702620,418750000),(-879687560,418750000),(-879687560,418750000),(-879617590,418750000),(-879617590,418750000),(-879614270,418750000),(-879614270,418750000),(-879611560,418750000),(-89611560,418750000),(-879551870,418750000),(-879551870,418750000),(-879544600,418750000),(-879544600,418750000),(-879531980,418750000),(-879531980,418750000),(-879519330,418750000),(-879519330,418750000),(-879507350,418750000),(-879507350,418750000),(-879494370,418750000),(-879494370,418750000),(-879481570,418750000),(-879481570,418750000),(-879469050,418750000),(-879469050,418750000),(-879457200,418750000),(-879457200,418750000),(-879446660,418750000),(-879446660,418750000),(-879435070,418750000),(-879435070,418750000),(-879423630,418750000),(-879423630,418750000),(-879411030,418750000),(-879411030,418750000),(-879397520,418750000),(-879397520,418750000),(-879385310,418750000),(-879385310,418750000),(-879364550,418750000),(-879364550,418750000),(-879347030,418750000),(-879347030,418750000),(-879336090,418750000),(-879336090,418750000),(-879323380,418750000),(-879323380,418750000),(-87932310,418750000),(-879312310,418750000),(-879300290,418750000),(-879300290,418750000),(-879288280,418750000),(-879288280,418750000),(-879256170,418750000),(-879256170,418750000),(-879245250,418750000),(-879245250,418750000),(-879230540,418750000),(-879230540,418750000),(-879223070,418750000),(-879223070,418750000),(-879204650,418750000),(-879204650,418750000),(-879191420,418750000),(-879191420,418750000),(-879184480,418750000),(-879184480,418750000),(-879166660,418750000),(-879166660,418750000),(-879143370,418750000),(-879143370,418750000),(-879130620,418750000),(-879130620,418750000),(-879124800,418750000),(-879124800,418750000),(-879102120,418750000),(-879102120,418750000),(-879089020,418750000),(-879089020,418750000),(-879074480,418750000),(-879074480,418750000),(-879061510,418750000),(-879061510,418750000),(-879050380,418750000),(-879050380,418750000),(-879037450,418750000),(-87903740,418750000),(-879024420,418750000),(-879024420,418750000),(-879011310,418750000),(-879011310,418750000),(-878996680,418750000),(-878996680,418750000),(-878984750,418750000),(-878984750,418750000),(-878973830,418750000),(-878973830,418750000),(-878971200,418750000),(-878971200,418750000),(-878960420,418750000),(-878960420,418750000),(-878950440,418750000),(-878950440,418750000),(-878941460,418750000),(-878941460,418750000),(-878938940,418750000),(-878938940,418750000),(-878926680,418750000),(-878926680,418750000),(-878829580,418750000),(-878829580,418750000),(-878795610,418750000),(-878795610,418750000),(-878788760,418750000),(-878788760,418750000),(-878779580,418750000),(-878779580,418750000),(-878754070,418750000),(-878754070,418750000),(-878750000,418750000),(-878750000,418750000),(-878750000,418752180),(-878750000,418752180),(-878750000,418760470),(-878750000,418760470),(-878750000,18769720),(-878750000,418769720),(-878750000,418779190),(-878750000,418779190),(-878750000,418786480),(-878750000,418786480),(-878750000,418790300),(-878750000,418790300),(-878750000,418798740),(-878750000,418798740),(-878750000,418816300),(-878750000,418816300),(-878750000,418844860),(-878750000,418844860),(-878750000,418865960),(-878750000,418865960),(-878750000,418883640),(-878750000,418883640),(-878750000,418908300),(-878750000,418908300),(-878750000,418970530),(-878750000,418970530),(-878750000,418981300),(-878750000,418981300),(-878750000,418999260),(-878750000,418999260),(-878750000,419033610),(-878750000,419033610),(-878750000,419054300),(-878750000,419054300),(-878750000,419061710),(-878750000,419061710),(-878750000,419073300),(-878750000,419073300),(-878750000,419075570),(-878750000,419075570),(-878750000,419107300),(-878750000,419107300),(-878750000,419147630),(-878750000,41947630),(-878750000,419183810),(-878750000,419183810),(-878750000,419193030),(-878750000,419193030),(-878750000,419211120),(-878750000,419211120),(-878750000,419221010),(-878750000,419221010),(-878750000,419249210),(-878750000,419249210),(-878750000,419258180),(-878750000,419258180),(-878750000,419274580),(-878750000,419274580),(-878750000,419280160),(-878750000,419280160),(-878750000,419282060),(-878750000,419282060),(-878750000,419283210),(-878750000,419283210),(-878750000,419298260),(-878750000,419298260),(-878750000,419310570),(-878750000,419310570),(-878750000,419328300),(-878750000,419328300),(-878750000,419346300),(-878750000,419346300),(-878750000,419362580),(-878750000,419362580),(-878750000,419379090),(-878750000,419379090),(-878750000,419394980),(-878750000,419394980),(-878750000,419401000),(-878750000,419401000),(-878750000,419419300),(-878750000,419419300),(-878750000,419437300),(-878750000,419437300),(-878750000,419453300),(-878750000,419453300),(-878750000,419472300),(-878750000,419472300),(-878750000,419498300),(-878750000,419498300),(-878750000,419559040),(-878750000,419559040),(-878750000,419582630),(-878750000,419582630),(-878750000,419598600),(-878750000,419598600),(-878750000,419622410),(-878750000,419622410),(-878750000,419626020),(-878750000,419626020),(-878750000,419640970),(-878750000,419640970),(-878750000,419655930),(-878750000,419655930),(-878750000,419730790),(-878750000,419730790),(-878750000,419823550),(-878750000,419823550),(-878750000,419823890),(-878750000,419823890),(-878750000,419898030),(-878750000,419898030),(-878750000,419916320),(-878750000,419916320),(-878750000,419935610),(-878750000,419935610),(-878750000,419950660),(-878750000,419950660),(-878750000,419957710),(-878750000,419957710),(-878750000,419959690),(-878750000,419959690),(-878750000,419988310),(-878750000,419988310),(-878750000,419997300),(-878750000,419997300),(-878750000,420000000),(-878750000,420000000),(-878796170,420000000),(-878796170,420000000),(-878818300,420000000),(-878818300,420000000),(-878820850,420000000),(-878820850,420000000),(-878823480,420000000),(-878823480,420000000),(-878824760,420000000),(-878824760,420000000),(-878846130,420000000),(-878846130,420000000),(-878940170,420000000),(-878940170,420000000),(-878957520,420000000),(-878957520,420000000),(-879050000,420000000),(-879050000,420000000),(-879050680,420000000),(-879050680,420000000),(-879198660,420000000),(-879198660,420000000),(-879353110,420000000),(-879353110,420000000),(-879401990,420000000),(-879401990,420000000),(-879419650,420000000),(-879419650,420000000),(-879426990,420000000),(-879426990,420000000),(-879493560,420000000),(-879493560,420000000),(-879551870,420000000),(-879551870,420000000),(-879593170,420000000),(-879593170,420000000),(-879697840,420000000),(-879697840,420000000),(-879774750,420000000),(-879774750,420000000),(-879776710,420000000),(-879776710,420000000),(-879787770,420000000),(-879787770,420000000),(-879793080,420000000),(-879793080,420000000),(-879800680,420000000),(-879800680,420000000),(-879819820,420000000),(-879819820,420000000),(-879829680,420000000),(-879829680,420000000),(-879843500,420000000),(-879843500,420000000),(-879851680,420000000),(-879851680,420000000),(-879862570,420000000),(-879862570,420000000),(-879872680,420000000),(-879872680,420000000),(-879882290,420000000),(-879882290,420000000),(-879900290,420000000),(-879900290,420000000),(-879916020,420000000),(-879916020,420000000),(-879922620,420000000),(-879922620,420000000),(-879928780,420000000),(-879928780,420000000),(-879941520,420000000),(-879941520,420000000),(-879976180,420000000),(-879976180,420000000),(-880000000,420000000),(-880000000,420000000),(-880000000,419999750),(-880000000,419999750),(-880000000,419991890),(-880000000,419991890),(-880000000,419984270),(-880000000,419984270),(-880000000,419976010),(-880000000,419976010),(-880000000,419968610),(-880000000,419968610),(-880000000,419960980),(-880000000,419960980),(-880000000,419952750),(-880000000,419952750),(-880000000,419946490),(-880000000,419946490),(-880000000,419928250),(-880000000,419928250),(-880000000,419880720),(-880000000,419880720),(-880000000,419836270),(-880000000,419836270),(-880000000,419806440),(-880000000,419806440),(-880000000,419799470),(-880000000,419799470),(-880000000,419788040),(-880000000,419788040),(-880000000,419720125),(-880000000,419720125),(-880000000,419713973),(-880000000,419713973),(-880000000,419698630),(-880000000,419698630),(-880000000,419690110),(-880000000,419690110),(-880000000,419668360),(-880000000,419668360),(-880000000,419655290),(-880000000,419655290),(-880000000,419634540),(-880000000,419634540),(-880000000,419626370),(-880000000,419626370),(-880000000,419605310),(-880000000,419605310),(-880000000,419596260),(-880000000,419596260),(-880000000,419588180),(-880000000,419588180),(-880000000,419579330),(-880000000,419579330),(-880000000,419569810),(-880000000,419569810),(-880000000,419560780),(-880000000,419560780),(-880000000,419551140),(-880000000,419551140),(-880000000,419543610),(-880000000,419543610),(-880000000,419533820),(-880000000,419533820),(-880000000,419524880),(-880000000,419524880),(-880000000,419475170),(-880000000,419475170),(-880000000,419447260),(-880000000,419447260),(-880000000,419423860),(-880000000,419423860),(-880000000,419414890),(-880000000,419414890),(-880000000,419369550),(-880000000,419369550),(-880000000,419335010),(-880000000,419335010),(-880000000,419322290),(-880000000,419322290),(-880000000,419313350),(-880000000,419313350),(-880000000,419306580),(-880000000,419306580),(-880000000,419290310),(-880000000,419290310),(-880000000,419289890),(-880000000,419289890),(-880000000,419272270),(-880000000,419272270),(-880000000,419264970),(-880000000,419264970),(-880000000,419255280),(-880000000,419255280),(-880000000,419240670),(-880000000,419240670),(-880000000,419236360),(-880000000,419236360),(-880000000,419221620),(-880000000,419221620),(-880000000,419218290),(-880000000,419218290),(-880000000,419195290),(-880000000,419195290),(-880000000,419154230),(-880000000,419154230),(-880000000,419142830),(-880000000,419142830),(-880000000,419133270),(-880000000,419133270),(-880000000,419107450),(-880000000,419107450),(-880000000,419087030),(-880000000,419087030),(-880000000,419077760),(-880000000,419077760),(-880000000,419077280),(-880000000,419077280),(-880000000,419064320),(-880000000,419064320),(-880000000,419056150),(-880000000,419056150),(-880000000,419048300),(-880000000,419048300),(-880000000,419034850),(-880000000,419034850),(-880000000,419023420),(-880000000,419023420),(-880000000,419013470))' @> polygon '((-880000000,418750000),(-878750000,418750000),(-878750000,420000000),(-880000000,420000000))' AS "true";
+
-- same
SELECT polygon '(2.0,0.0),(2.0,4.0),(0.0,0.0)' ~= polygon '(3.0,1.0),(3.0,3.0),(1.0,0.0)' AS false;
-- overlap
SELECT polygon '(2.0,0.0),(2.0,4.0),(0.0,0.0)' && polygon '(3.0,1.0),(3.0,3.0),(1.0,0.0)' AS true;
SELECT '((0,4),(6,4),(1,2),(6,0),(0,0))'::polygon && '((2,1),(2,3),(3,3),(3,1))'::polygon AS "true";
SELECT '((1,4),(1,1),(4,1),(4,2),(2,2),(2,4),(1,4))'::polygon && '((3,3),(4,3),(4,4),(3,4),(3,3))'::polygon AS "false";
SELECT '((200,800),(800,800),(800,200),(200,200))' && '(1000,1000,0,0)'::polygon AS "true";
--
2.14.3 (Apple Git-98)
Emre Hasegeli <emre@hasegeli.com> writes:
I believe there is a simple flaw on the algorithm that causes it loop
endlessly. It should stop looking at the other segments of the
polygon after finding the touching one. The attached patch fixes the
issue for the query posted to this thread. I suggest backpacking the
fix.
I think this fix is wrong, because it assumes that the answer of
touched_lseg_inside_poly is authoritative, which it clearly isn't;
the blind "return true" for noncollinear segments breaks it.
That is, if "a" is an interior point on the polygon's first segment,
but "b" is outside the polygon, then lseg_inside_poly's first
on_ps_internal call will succeed, its second will not, then it
will call touched_lseg_inside_poly. All four of the latter's
tests will fail and it'll return true. Your patch would have us
break out of the loop without looking at any subsequent segments,
which is wrong.
It's a bit difficult to demonstrate the error, because lseg_inside_poly
isn't exposed directly, only through poly_contain (maybe we should add
an operator that does expose it?). But after experimenting awhile
I found a counterexample:
select '(0,0),(10,0),(0,10)'::polygon @> '(6,0),(7,0),(6,6)'::polygon;
This surely should return false, and it does in HEAD, but your patch
makes it return true.
There are other things to be unhappy about. As written, lseg_inside_poly
and touched_lseg_inside_poly can mutually recurse to a depth equal to
the number of points in the polygon, which opens a stack-overflow hazard.
I'd like to get rid of the recursion; it seems unnecessary.
Also, while it's sadly underdocumented what touched_lseg_inside_poly is
meant to accomplish at all, I think what it's there for is to deal with
cases involving collinear polygon segments. That is, if we inject some
useless points into the polygon, say
'(0,0),(5,0),(10,0),(0,10)'::polygon
then it should still be true that the line segment '(1,0),(9,0)' is
"inside" this polygon, but we won't find that out if we just consider
the (0,0),(5,0) and (5,0),(10,0) polygon segments independently.
I am not, however, convinced that this coding fixes that problem if
there are multiple polygon segments we need to match up against.
What concerns me is that if the first collinear poly segment we come
to is an interior subset of the segment-under-test, say we're
considering line segment '(1,0),(9,0)' and we find a poly segment
'(3,0),(5,0)', then we need to separately detect whether each of
'(1,0),(3,0)' and '(5,0),(9,0)' are subsets of the rest of the
polygon ... and I don't see where this code can handle that.
I've not managed to build a weaponized test case though.
regards, tom lane