http://www.perlmonks.org?node_id=1224777

in reply to searching polygons not merged

How can I generate an example polygon collection? (i.e., what does "10000 EA" mean?)

I wouldn't be surprised if searching for overlapping polygons in a database of indexed polygons would be fast. If you had an example of "not that good performance and stupid way", I could see if a database search would indeed be better and "less stupid".

Replies are listed 'Best First'.
Re^2: searching polygons not merged
by LanX (Archbishop) on Oct 27, 2018 at 21:23 UTC
How do you represent polygons in a database, such that searching for overlaps becomes "fast"?

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

To illustrate polygon (a standard postgresql data type), polygon-comparison (here: overlap), and polygon-indexing (with which my practical experience is pretty much zero - caveat emptor!), I lifted some sql from the standard regression tests in the postgres source tree ( src/test/regress/sql/polygon.sql ), and messed about with it a bit, and added comments:

Note: the postgres polygon overlap operator is &&

```#!/bin/bash

echo "
drop   table if exists quad_poly_tbl ;
create table           quad_poly_tbl (id int, p polygon);
select (x - 1) * 100 + y, polygon(circle(point(x * 10, y * 10), 1 +
+(x + y) % 10))
from generate_series(1, 100) x, generate_series(1, 100) y ;
select i, polygon '((200, 300),(210, 310),(230, 290))'
from generate_series(10001, 11000) AS i ;

-- search for overlap with this polygon:
select * from quad_poly_tbl where p && '((22,640),(23.0717967697245,64
+4),(26,646.928203230275),(30,648),(34,646.928203230275),(36.928203230
+2755,644),(38,640))'::polygon ;

--> Time: 1.382 ms  -- Seq Scan on quad_poly_tbl (3 MB)

-- search again for overlap with this polygon but now WITH the polygon
+-index present:
select * from quad_poly_tbl where p && '((22,640),(23.0717967697245,64
+4),(26,646.928203230275),(30,648),(34,646.928203230275),(36.928203230
+2755,644),(38,640))'::polygon ;

--> Time: 0.271 ms  -- Bitmap Index Scan on quad_poly_tbl_idx (1 MB)

" | psql -qa
```--> Time: 1.382 ms  -- Seq Scan on quad_poly_tbl (3 MB)