[postgis-users] points in polygon
Paul Ramsey
pramsey at refractions.net
Fri Mar 31 15:08:13 PST 2006
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
More information about the postgis-users
mailing list