Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitedfeeff

Browse files
smonkewitzMarkus Nullmeier
authored and
Markus Nullmeier
committed
Fix incorrect query results with spatial indexes [#1011453]
The bounding box computation for ellipses, polygons, and pathsappeared to be broken. As these bounding boxes are used by theR-tree on-top-of GiST index implementation in pgsphere, the effectwas that some queries returned different results depending onwhether or not the optimizer chose to make use of an availablespatial index or not.I have attached a patch which fixes these problems as best as I can tell.http://pgfoundry.org/tracker/index.php?func=detail&aid=1011453&group_id=1000240&atid=914
1 parent97b5a21 commitedfeeff

File tree

4 files changed

+194
-33
lines changed

4 files changed

+194
-33
lines changed

‎Makefile‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ EXTENSION = pg_sphere
88
DATA_built = pg_sphere--1.0.sql
99
DOCS = README.pg_sphere COPYRIGHT.pg_sphere
1010
REGRESS = init tables points euler circle line ellipse poly path box index\
11-
contains_ops contains_ops_compat
11+
contains_ops contains_ops_compat bounding_box_gist
1212

1313
EXTRA_CLEAN = pg_sphere--1.0.sql$(PGS_SQL)
1414

‎expected/bounding_box_gist.out‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
CREATE TABLE bbox_ellipse (e sellipse not null);
2+
INSERT INTO bbox_ellipse VALUES ('<{10d, 0.1d}, (0d,0d), 0d>');
3+
SELECT spoint '(5d, 0d)' @ sellipse '<{10d, 0.1d}, (0d,0d), 0d>' AS inside;
4+
inside
5+
--------
6+
t
7+
(1 row)
8+
9+
SELECT COUNT(*) FROM bbox_ellipse WHERE spoint '(5d, 0d)' @ e;
10+
count
11+
-------
12+
1
13+
(1 row)
14+
15+
-- The ellipse has semi-major axis length of 10 degrees along the equator,
16+
-- so (lon,lat) = (5,0) should be inside.
17+
CREATE INDEX idx_bbox_ellipse ON bbox_ellipse USING gist (e);
18+
ANALYZE bbox_ellipse;
19+
SET enable_seqscan=false;
20+
SELECT COUNT(*) FROM bbox_ellipse WHERE spoint '(5d, 0d)' @ e;
21+
count
22+
-------
23+
1
24+
(1 row)
25+
26+
CREATE TABLE bbox_poly (p spoly not null);
27+
INSERT INTO bbox_poly VALUES ('{(40d,-40d), (0d,80d), (-40d,-40d)}');
28+
SELECT spoint '(0d, 0d)' @ spoly '{(40d,-40d), (0d,80d), (-40d,-40d)}' AS inside;
29+
inside
30+
--------
31+
t
32+
(1 row)
33+
34+
SELECT COUNT(*) FROM bbox_poly WHERE spoint '(0d, 0d)' @ p;
35+
count
36+
-------
37+
1
38+
(1 row)
39+
40+
CREATE INDEX idx_bbox_poly ON bbox_poly USING gist (p);
41+
ANALYZE bbox_poly;
42+
SET enable_seqscan=false;
43+
SELECT COUNT(*) FROM bbox_poly WHERE spoint '(0d, 0d)' @ p;
44+
count
45+
-------
46+
1
47+
(1 row)
48+
49+
CREATE TABLE bbox_path (p spath not null);
50+
INSERT INTO bbox_path VALUES ('{(-46d,0d), (-45d,80d), (-45d,0d), (80d,0d)}');
51+
SELECT sline(spoint '(0d, -10d)', spoint '(0d, 10d)') && spath '{(-46d,0d), (-45d,80d), (-45d,0d), (80d,0d)}' AS crossing;
52+
crossing
53+
----------
54+
t
55+
(1 row)
56+
57+
SELECT spoint '(0d, 0d)' @ spath '{(-46d,0d), (-45d,80d), (-45d,0d), (80d,0d)}' AS inside;
58+
inside
59+
--------
60+
t
61+
(1 row)
62+
63+
SELECT COUNT(*) FROM bbox_path WHERE sline(spoint '(0d, -10d)', spoint '(0d, 10d)') && p;
64+
count
65+
-------
66+
1
67+
(1 row)
68+
69+
SELECT COUNT(*) FROM bbox_path WHERE spoint '(0d, 0d)' @ p;
70+
count
71+
-------
72+
1
73+
(1 row)
74+
75+
CREATE INDEX idx_bbox_path ON bbox_path USING gist (p);
76+
ANALYZE bbox_path;
77+
SET enable_seqscan=false;
78+
SELECT COUNT(*) FROM bbox_path WHERE sline(spoint '(0d, -10d)', spoint '(0d, 10d)') && p;
79+
count
80+
-------
81+
1
82+
(1 row)
83+
84+
SELECT COUNT(*) FROM bbox_path WHERE spoint '(0d, 0d)' @ p;
85+
count
86+
-------
87+
1
88+
(1 row)
89+

‎key.c‎

Lines changed: 73 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -197,7 +197,7 @@ sphereellipse_gen_key(int32 *k, const SELLIPSE *e)
197197

198198
r[0]=sin(e->rad[0]);
199199
r[1]=sin(e->rad[1]);
200-
d=cos(e->rad[1]);
200+
d=cos(e->rad[0]);
201201

202202
v[0].x=d;
203203
v[0].y=-r[0];
@@ -341,21 +341,36 @@ sphereline_gen_key(int32 *k, const SLine *sl)
341341
for (i=0;i<4;i++)
342342
{
343343
euler_vector_trans(&vt,&v[i],&se);
344-
if (vt.x>=-1.0&&vt.x <=1.0)
344+
if (vt.x<-1.0)
345345
{
346-
vr[0].x=Min(vr[0].x,vt.x);
347-
vr[1].x=Max(vr[1].x,vt.x);
346+
vt.x=-1.0;
348347
}
349-
if (vt.y>=-1.0&&vt.y <=1.0)
348+
if (vt.y<-1.0)
350349
{
351-
vr[0].y=Min(vr[0].y,vt.y);
352-
vr[1].y=Max(vr[1].y,vt.y);
350+
vt.y=-1.0;
353351
}
354-
if (vt.z>=-1.0&&vt.z <=1.0)
352+
if (vt.z<-1.0)
355353
{
356-
vr[0].z=Min(vr[0].z,vt.z);
357-
vr[1].z=Max(vr[1].z,vt.z);
354+
vt.z=-1.0;
358355
}
356+
if (vt.x>1.0)
357+
{
358+
vt.x=1.0;
359+
}
360+
if (vt.y>1.0)
361+
{
362+
vt.y=1.0;
363+
}
364+
if (vt.z>1.0)
365+
{
366+
vt.z=1.0;
367+
}
368+
vr[0].x=Min(vr[0].x,vt.x);
369+
vr[1].x=Max(vr[1].x,vt.x);
370+
vr[0].y=Min(vr[0].y,vt.y);
371+
vr[1].y=Max(vr[1].y,vt.y);
372+
vr[0].z=Min(vr[0].z,vt.z);
373+
vr[1].z=Max(vr[1].z,vt.z);
359374
}
360375

361376
k[0]=vr[0].x*ks;
@@ -375,6 +390,7 @@ spherepoly_gen_key(int32 *key, const SPOLY *sp)
375390
{
376391
int32i;
377392
SLinel;
393+
SPointp;
378394
int32tk[6];
379395
boolstart= true;
380396

@@ -396,40 +412,65 @@ spherepoly_gen_key(int32 *key, const SPOLY *sp)
396412
key[4]=Max(key[4],tk[4]);
397413
key[5]=Max(key[5],tk[5]);
398414
}
415+
p.lng=0.0;
416+
p.lat=PIH;
417+
if (spoly_contains_point(sp,&p))
418+
{
419+
key[5]=MAXCVALUE;
420+
}
421+
p.lat=-PIH;
422+
if (spoly_contains_point(sp,&p))
423+
{
424+
key[2]=-MAXCVALUE;
425+
}
426+
p.lat=0.0;
427+
if (spoly_contains_point(sp,&p))
428+
{
429+
key[3]=MAXCVALUE;
430+
}
431+
p.lng=PI;
432+
if (spoly_contains_point(sp,&p))
433+
{
434+
key[0]=-MAXCVALUE;
435+
}
436+
p.lng=PIH;
437+
if (spoly_contains_point(sp,&p))
438+
{
439+
key[4]=MAXCVALUE;
440+
}
441+
p.lng=PI+PIH;
442+
if (spoly_contains_point(sp,&p))
443+
{
444+
key[1]=-MAXCVALUE;
445+
}
399446
}
400447
}
401448

402449
void
403450
spherepath_gen_key(int32*key,constSPATH*sp)
404451
{
405-
int32i,
406-
k,
407-
r;
452+
int32i;
408453
SLinel;
409454
int32tk[6];
410455
boolstart= true;
411456

412-
for (i=0;i<sp->npts;i++)
457+
for (i=0;i<sp->npts-1;i++)
413458
{
414-
for (k=i+1;i<sp->npts;i++)
459+
sline_from_points(&l,&sp->p[i],&sp->p[i+1]);
460+
sphereline_gen_key(&tk[0],&l);
461+
if (start)
415462
{
416-
r= ((k==sp->npts) ? (0) : (k));
417-
sline_from_points(&l,&sp->p[i],&sp->p[r]);
418-
sphereline_gen_key(&tk[0],&l);
419-
if (start)
420-
{
421-
start= false;
422-
memcpy((void*)key, (void*)&tk[0],KEYSIZE);
423-
}
424-
else
425-
{
426-
key[0]=Min(key[0],tk[0]);
427-
key[1]=Min(key[1],tk[1]);
428-
key[2]=Min(key[2],tk[2]);
429-
key[3]=Max(key[3],tk[3]);
430-
key[4]=Max(key[4],tk[4]);
431-
key[5]=Max(key[5],tk[5]);
432-
}
463+
start= false;
464+
memcpy((void*)key, (void*)&tk[0],KEYSIZE);
465+
}
466+
else
467+
{
468+
key[0]=Min(key[0],tk[0]);
469+
key[1]=Min(key[1],tk[1]);
470+
key[2]=Min(key[2],tk[2]);
471+
key[3]=Max(key[3],tk[3]);
472+
key[4]=Max(key[4],tk[4]);
473+
key[5]=Max(key[5],tk[5]);
433474
}
434475
}
435476
}

‎sql/bounding_box_gist.sql‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
CREATETABLEbbox_ellipse (e sellipsenot null);
2+
INSERT INTO bbox_ellipseVALUES ('<{10d, 0.1d}, (0d,0d), 0d>');
3+
SELECT spoint'(5d, 0d)' @ sellipse'<{10d, 0.1d}, (0d,0d), 0d>'AS inside;
4+
SELECTCOUNT(*)FROM bbox_ellipseWHERE spoint'(5d, 0d)' @ e;
5+
-- The ellipse has semi-major axis length of 10 degrees along the equator,
6+
-- so (lon,lat) = (5,0) should be inside.
7+
CREATEINDEXidx_bbox_ellipseON bbox_ellipse USING gist (e);
8+
ANALYZE bbox_ellipse;
9+
SET enable_seqscan=false;
10+
SELECTCOUNT(*)FROM bbox_ellipseWHERE spoint'(5d, 0d)' @ e;
11+
12+
CREATETABLEbbox_poly (p spolynot null);
13+
INSERT INTO bbox_polyVALUES ('{(40d,-40d), (0d,80d), (-40d,-40d)}');
14+
SELECT spoint'(0d, 0d)' @ spoly'{(40d,-40d), (0d,80d), (-40d,-40d)}'AS inside;
15+
SELECTCOUNT(*)FROM bbox_polyWHERE spoint'(0d, 0d)' @ p;
16+
CREATEINDEXidx_bbox_polyON bbox_poly USING gist (p);
17+
ANALYZE bbox_poly;
18+
SET enable_seqscan=false;
19+
SELECTCOUNT(*)FROM bbox_polyWHERE spoint'(0d, 0d)' @ p;
20+
21+
CREATETABLEbbox_path (p spathnot null);
22+
INSERT INTO bbox_pathVALUES ('{(-46d,0d), (-45d,80d), (-45d,0d), (80d,0d)}');
23+
SELECT sline(spoint'(0d, -10d)', spoint'(0d, 10d)') && spath'{(-46d,0d), (-45d,80d), (-45d,0d), (80d,0d)}'AS crossing;
24+
SELECT spoint'(0d, 0d)' @ spath'{(-46d,0d), (-45d,80d), (-45d,0d), (80d,0d)}'AS inside;
25+
SELECTCOUNT(*)FROM bbox_pathWHERE sline(spoint'(0d, -10d)', spoint'(0d, 10d)') && p;
26+
SELECTCOUNT(*)FROM bbox_pathWHERE spoint'(0d, 0d)' @ p;
27+
CREATEINDEXidx_bbox_pathON bbox_path USING gist (p);
28+
ANALYZE bbox_path;
29+
SET enable_seqscan=false;
30+
SELECTCOUNT(*)FROM bbox_pathWHERE sline(spoint'(0d, -10d)', spoint'(0d, 10d)') && p;
31+
SELECTCOUNT(*)FROM bbox_pathWHERE spoint'(0d, 0d)' @ p;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp