Hi Martin,
There is a very fast algorithm for testing point in polygon by creating
a vector from the point to another point beyond the extents of the
polygon and counting the number of edge crossings. If the count is odd
then the point is in the polygon and if the count is even it is not. If
the vector is horizontal you can very rapidly reject all edges above or
below the vector and all edges east or west of the vector. Then a simple
intersection test on each of the remain edges will determine the count.
Given your extensive knowledge in computational geometry, I assume you
already are aware of this algorithm and it is not suitable for some
reason. But since this question on performance comes up pretty often, it
might have a place as long as people know what the potential limitations
are.
-Steve
On 12/20/2011 10:48 PM, Martin Davis wrote:
For more detail check out this thread on the same issue:
http://postgis.refractions.net/pipermail/postgis-users/2011-November/031345.html
On 12/20/2011 5:28 PM, Puneet Kishor wrote:
On Dec 20, 2011, at 7:21 PM, Paul Ramsey wrote:
Chop up the continents into smaller pieces.
hmmm... I am not sure I understand the above. And then what? UNION
each smaller piece query?
On Tue, Dec 20, 2011 at 4:35 PM, Puneet Kishor<punk.k...@gmail.com>
wrote:
This is probably a really basic question... my ST_Within or
ST_Intersects selecting points in a continent are way too slow (both
take upward of 200 secs).
SELECT Count(c_id)
FROM c, continents n
WHERE ST_Intersects(c.the_geom, n.the_geom) AND
n.continent = 'North America';
Both tables have gist indexes on the geometries. The above query has
the following plan
"Aggregate (cost=9.66..9.67 rows=1 width=4)"
" -> Nested Loop (cost=0.00..9.66 rows=1 width=4)"
" Join Filter: _st_intersects(c.the_geom, n.the_geom)"
" -> Seq Scan on continents n (cost=0.00..1.10 rows=1 width=32)"
" Filter: ((continent)::text = 'North America'::text)"
" -> Index Scan using pbdb__collections_the_geom on collections c
(cost=0.00..8.30 rows=1 width=104)"
" Index Cond: (c.the_geom&& n.the_geom)"
The table c has approx 120K rows, and the continents table has 8
rows.Suggestions on how I can improve this? Yes, the computer is
otherwise very swift and modern.
--
Puneet Kishor
_______________________________________________
postgis-users mailing list
postgis-users@postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-users
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2012.0.1890 / Virus Database: 2109/4692 - Release Date: 12/20/11
_______________________________________________
postgis-users mailing list
postgis-users@postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-users
_______________________________________________
postgis-users mailing list
postgis-users@postgis.refractions.net
http://postgis.refractions.net/mailman/listinfo/postgis-users
