[postgis] [Fwd: Points in circle alrogithm]

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[postgis] [Fwd: Points in circle alrogithm]

David Blasby-3
Doug,

Thanks for the info on point-in-circle info.  I'm forwarding it to the
list because others might be interested in it and it might stir up some
discussion - hope you dont mind.

If the query point it at (Px,Py), and the maximum distance is d, you
could do something like this query;

select * from <table> where inside_circle(<geom col>, Px,Py,d);

Or, using the index;

select * from <table> where point_inside_circle(<geom col>,Px,Py,d) and
<geom col> && 'BOX3D(Px-d,Py-d  ,  Px+d, Py+d)'::BOX3D;

That means only the point_inside_circle(GOEMETRY,double,double,double)
function needs to be written.  Its a fairly simple function; just use
your equations.

On the other hand, it would be better to have something a bit more
generic.  Ie.

select * from <table> where distance(<geom col>, 'POINT(Px,Py)')<d;

or, if we abstract a bit  and allow the 1st and 2nd argument to be any
type of geometry (instead of just points).

select * from <table> where distance(<geom col>, <test geom>) <d;

And, using the index;

select * from <table> where distance(<geom col>, <test geom>) <d and
<geom col> && expand_bbox(<test geom>,d);

Where expand_bbox(geometry, double) is a very simple function that takes
geometry's bbox and makes it 'bigger' in X and Y.

Here the distance(geometry A, geometry B) will find the minimum distance
between all the sub geometries in A and the sub geometries in B.  There
is an OpenGIS function for this, but I cannot find its name.

Unfortunately, distance(geometry, geometry) is difficult to write (but
extreamly useful).

I'm also trying to cut down the number of function (have few generic
functions instead of lots of specific functions) and stick to
OpenGIS-approved functions.

What do folk think?

dave
------------------------ Yahoo! Groups Sponsor ---------------------~-->
Secure your servers with 128-bit SSL encryption! Grab your copy of
VeriSign's FREE Guide "Securing Your Web Site for Business." Get it now!
http://www.verisign.com/cgi-bin/go.cgi?a=n094442340008000
http://us.click.yahoo.com/6lIgYB/IWxCAA/yigFAA/PhFolB/TM
---------------------------------------------------------------------~->

To unsubscribe from this group, send an email to:
[hidden email]

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 


Here is an algorithm to extend your existing postgis bounding rectangle
search.

1. Get X,Y coordinate and radius in native cartesian system from user.
2. Calculate MBR for query circle to be:
    minx=X-radius
    maxx=X+radius
    miny=Y-radius
    maxy=Y+radius
3. Perform pre-emptive fetch from postgis of point records in MBR
based on above rectangle dimensions.
4. A speed-enhancing step now, especially useful for very large
areas or dense selections, would be to first calculate the outer MBR
into a selected set, then subselect for the points that fall within a
square that fits within the circle. Points that fall within the inner
square
do not need to be further tested. Only the point records falling
outside the inner square and inside the outer square need to be tested!
This set is defined as:

(((X+D) > A > (X-D))AND((Y+D) > B > (Y-D)) ) AND
(((X+R) > A > (X-R))AND((Y+R) > B > (Y-R)))

5. Move through each selected record to determine if the point
falls within the radius, basically if the following is true, where A,B
represents the returned coordinates found in MBR, and X,Y is
the test centroid and R=Radius posed by the user. If the following
statement is true, then the points fall within the circle:

((A-X)^2 + (B-Y)^2) le (R^2)

where ^2 means squared.

6. The resulting rows would be in or on the perimeter of the circle.
Within test would be a less-than not a less-than-equals operator.

Now, the final trick in my world is that the coordinates are in lat
long, so my circle is not even close to a circle except at the Equator
so I'd need to have my data projected into an equal area projection
before the test, or convert my circle query into an approximate
polygon (or ellipse?) to perform the overlay...

Hope this helps.

Doug.

Reply | Threaded
Open this post in threaded view
|

[postgis] Re: Points in circle alrogithm

Paul Ramsey-2
Would implementing the trivial cases of the generic functions, and then
providing trivial stubs for the hard cases be a raasonable interim
approach? IE: implement the proper point-within-circle test, and
implement centroid-of-bbox-in-circle for the polygons and linestrings?
As long as we document this (dumbass) behavior properly it is better
than no behavior at all, yes?

> I'm also trying to cut down the number of function (have few generic
> functions instead of lots of specific functions) and stick to
> OpenGIS-approved functions.
>
> What do folk think?

To unsubscribe from this group, send an email to:
[hidden email]

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/