[postgis-users] points in polygon
Josh Livni
josh at livniconsulting.com
Fri Mar 31 15:49:40 PST 2006
Yeah - that does seem a bit slow for 8k points. For what it's worth, I
found a similar PIP query that had about a half million points sped up
almost an order of magnitude when I changed my .conf from the default,
and to use more memory.
-Josh
Ethan Alpert wrote:
> Since when is 8,000 points a s*** load? Something's not right here it
> shouldn't take that long. Something must be wrong with the spatial
> index. I'd like to see his explain output from the query below.
>
> -e
> -----Original Message-----
> From: postgis-users-bounces at postgis.refractions.net
> [mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of Paul
> Ramsey
> Sent: Friday, March 31, 2006 4:08 PM
> To: PostGIS Users Discussion
> Subject: Re: [postgis-users] points in polygon
>
> It's not hackish, it is the solution. The problem is that he clearly
> has a s***load of points inside LA, so even with the index taking out
> all the non-candidates, there are an *awfully* large number of tests
> to be run with full topological correctness by Contains().
>
> This brings up a short-circuit we had discussed previously for the
> point-in-polygon case, which is to recognize that case when it arises
> and do the far cheaper PIP test instead of the full topological test.
>
> A true "hack" which is approximately equivalent is this:
>
> SELECT point.id
> FROM point, polygon
> WHERE (polygon.fips = '0644000')
> AND point.the_geom && polygon.the_geom
> AND distance(polygon.the_geom, point.the_geom) < 0.001;
>
> It will still not take milliseconds, because there are still scads
> and scads of points being run through the Distance() function, but it
> will be somewhat faster than Contains(). Really, Josh's solution is
> the real one for things like this: pre-calculate the answer. If your
> points are dynamic (I doubt your city boundary is) then add a trigger
> to the points table that re-calculates the city containment
> information on update/insert.
>
> Paul
>
> On 31-Mar-06, at 2:17 PM, Josh Livni wrote:
>
>
>>This does not answer your question of speedy spatial calcuation,
>>but assuming your points are fairly static, you could add a field
>>like in_polygon, run for all points, index on that field, and query
>>on that, saving you from needing to run the spatial query each time.
>>
>>If you get new points, you could have a couple queries, running the
>>spatial one just on those with no set value in that field.
>>
>>I know it's hackish, and again not a direct answer to your
>>question, but I find pre-calculating on mostly static datasets gets
>>me a great boost in speed for many scenarios.
>>
>>Regards,
>>
>> -Josh
>>
>>Young Kim wrote:
>>
>>>thanks all for your responses.
>>>the solution that you all provided did work, but my main problem is
>>>that i need the query to run FAST.
>>>BOX, WITHIN and INTERSECTS all runs in 140000~170000 ms ranges.
>>>I tried with smaller cities, and they run in good time.
>>>"santa monica" runs in 130 ms.
>>>Is it then the area that i'm joining against is too large or too
>>>complex?
>>>With all the gist indices on "the_geom" columns in place and "vacuum
>>>analyze" run, I would think it should not take 3 minuts to run a
>>>query.
>>>On 3/31/06, Bruce Rindahl <rindahl at lrcwe.com> wrote:
>>>
>>>>I don't this is even that complicated.
>>>>Try
>>>>SELECT point.id
>>>>FROM point, polygon
>>>>WHERE (polygon.fips = '0644000')
>>>> AND point.the_geom && polygon.the_geom
>>>> AND intersects(polygon.the_geom, point.the_geom);
>>>>
>>>>
>>>>The first clause checks for only LA county.
>>>>The next clause checks if the bounding box of the point is within
>>>>the
>>>>bounding box of the polygon. (very fast if the GIST indexes are
>>>>set)
>>>>Finally anything that matches the first two is checked for an actual
>>>>intersection.
>>>>
>>>>Bruce Rindahl
>>>>
>>>>-----Original Message-----
>>>>From: postgis-users-bounces at postgis.refractions.net
>>>>[mailto:postgis-users-bounces at postgis.refractions.net] On Behalf Of
>>>>Matthew Perry
>>>>Sent: Friday, March 31, 2006 12:03 PM
>>>>To: PostGIS Users Discussion
>>>>Subject: Re: [postgis-users] points in polygon
>>>>
>>>>Perhaps you can try WITHIN instead of CONTAINS?
>>>>
>>>>"""
>>>>Within(geometry A, geometry B)
>>>>
>>>> Returns 1 (TRUE) if Geometry A is "spatially within" Geometry B.
>>>>"""
>>>>
>>>>- matt
>>>>
>>>>On 3/31/06, Young Kim <youngkkim at gmail.com> wrote:
>>>>
>>>>
>>>>>Thanks for your prompt response.
>>>>>
>>>>>I have tried :
>>>>>SELECT point.id
>>>>>FROM point, polygon
>>>>>WHERE (polygon.fips = '0644000')
>>>>> and point.the_geom && SetSRID('BOX3D(-118.668411254883
>>>>>33.7045364379883,-117.753349304199 34.3367500305176)'::box3d,-1)
>>>>> AND (contains(polygon.the_geom, point.the_geom));
>>>>>
>>>>>got ~146000ms.
>>>>>
>>>>>could not get "makebox2d" to work. syntax errors. i'm very new to
>>>>
>>>>postgis.
>>>>
>>>>
>>>>>thanks.
>>>>>
>>>>>
>>>>>On 3/31/06, David Bitner <osgis.lists at gmail.com> wrote:
>>>>>
>>>>>
>>>>>>Have you tried creating a bounding box out of the x, y pair you
>>>>>>are
>>>>>>using and then using the && operator on that rather than using the
>>>>>>x>,y> statements.
>>>>>>
>>>>>>See MakeBox2D in http://postgis.refractions.net/docs/ch06.html
>>>>>>
>>>>>>On 3/31/06, Young Kim <youngkkim at gmail.com> wrote:
>>>>>>
>>>>>>
>>>>>>>hello all,
>>>>>>>
>>>>>>>looking to select points in a polygon FAST. Seems like a simple
>>>>>>>problem, but could not find good doc anywhere.
>>>>>>>
>>>>>>>Thanks in advance.
>>>>>>>
>>>>>>>
>>>>>>>BACKGROUND:
>>>>>>>points - 8663 points in greater los angeles area.
>>>>>>> - has "gist" index on "the_geom"
>>>>>>>polygon - city of los angeles
>>>>>>> - has "gist" index on "the_geom"
>>>>>>> - has "btree" index on "fips"
>>>>>>>also ran "vaccum analyze"
>>>>>>>
>>>>>>>
>>>>>>>PROBLEM:
>>>>>>>looking to select all points in city of los angeles.
>>>>>>>out of 8663, 3248 points are contained in city of los angeles
>>>>
>>>>polygon.
>>>>
>>>>
>>>>>>>it takes ~163000 ms. that's roughly 3 minutes.
>>>>>>>How can I make this faster?
>>>>>>>
>>>>>>>
>>>>>>>QUERY (x,y values are extent of polygon):
>>>>>>>SELECT point.id
>>>>>>>FROM point, polygon
>>>>>>>WHERE (x >= -118.668411254883)
>>>>>>> AND (y >= 33.7045364379883)
>>>>>>> AND (x <= -117.753349304199)
>>>>>>> AND (y <= 34.3367500305176)
>>>>>>> AND (polygon.fips = '0644000')
>>>>>>> AND point.the_geom && polygon.the_geom
>>>>>>> AND (contains(polygon.the_geom, point.the_geom))
>>>>>>>
>>>>>>>
>>>>>>>Aggregate (cost=9.08..9.09 rows=1 width=4) (actual
>>>>>>>time=162893.411..162893.411 rows=1 loops=1)
>>>>>>> -> Nested Loop (cost=0.00..9.05 rows=9 width=4) (actual
>>>>>>>time=4137.275..162885.507 rows=3248 loops=1)
>>>>>>> Join Filter: contains("outer".the_geom, "inner".the_geom)
>>>>>>> -> Index Scan using idx_polygon_fips on polygon
>>>>>>>(cost=0.00..3.01 rows=1 width=9414) (actual time=0.013..0.017
>>>>
>>>>rows=1
>>>>
>>>>
>>>>>>>loops=1)
>>>>>>> Index Cond: ((fips)::text = '0644000'::text)
>>>>>>> -> Index Scan using idx_point_the_geom on point
>>>>>>>(cost=0.00..6.02 rows=1 width=25) (actual time=62.512..17889.149
>>>>>>>rows=7050 loops=1)
>>>>>>> Index Cond: (point.the_geom && "outer".the_geom)
>>>>>>> Filter: ((point.x >= -118.668411254883) AND
>>>>
>>>>(point.y >=
>>>>
>>>>
>>>>>>>33.7045364379883) AND (point.x <= -117.753349304199) AND (point.y
>>>>
>>>><=
>>>>
>>>>
>>>>>>>34.3367500305176) AND (point.the_geom && "outer".the_geom))
>>>>>>>Total runtime: 162893.483 ms
>>>>>>>_______________________________________________
>>>>>>>postgis-users mailing list
>>>>>>>postgis-users at postgis.refractions.net
>>>>>>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>>>>
>>>>>>
>>>>>>_______________________________________________
>>>>>>postgis-users mailing list
>>>>>>postgis-users at postgis.refractions.net
>>>>>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>>>
>>>>>
>>>>>_______________________________________________
>>>>>postgis-users mailing list
>>>>>postgis-users at postgis.refractions.net
>>>>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>>
>>>>
>>>>
>>>>--
>>>>Matt Perry
>>>>perrygeo at gmail.com
>>>>http://www.perrygeo.net
>>>>_______________________________________________
>>>>postgis-users mailing list
>>>>postgis-users at postgis.refractions.net
>>>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>
>>>>_______________________________________________
>>>>postgis-users mailing list
>>>>postgis-users at postgis.refractions.net
>>>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>>>>
>>>
>>>_______________________________________________
>>>postgis-users mailing list
>>>postgis-users at postgis.refractions.net
>>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>>
>>
>>_______________________________________________
>>postgis-users mailing list
>>postgis-users at postgis.refractions.net
>>http://postgis.refractions.net/mailman/listinfo/postgis-users
>
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
More information about the postgis-users
mailing list