Thread: Point inside/outside area constructed by an expanded path

  On 10/14/10 12:00 PM, Josi Perez (3T Systems) wrote:
> Hi,
>
> I use postgreSQL.8.4.2 and don't have postGIS installed.
> I have a geometric type polygon and I know that it is possible to
> determine if a point it is inside or not of this polygon, using
> anything like that:
> select
> polygon('(-23.5672,-46.6510),(-23.5670,-46.65095),(-23.5672,-46.6508),(-23.5672,-46.6510)')
> @> point('-23.567534,-46.64942')
>
> The question:
> Anyone knows an algorithm or have ideas how to determine if a point it
> is inside an area constructed by geometric type path expanded for a
> known distance?
> Graphically:
>
> the path
>             x=========x=======x
>
> the path expanded by a distance
>
>             |         | A     |
>             |         |       |
>      -------x=========x=======x-------  C
>             |         |       |
>         B   |         |       |
>
> the points A and B are inside and the point C are outside .

that's pretty tricky.    are the 'end caps' on that expansion
rectangular or circular?  if circular is acceptable,  you could perhaps
calculate the shortest distance of your point from the path (non trivial
if the path is complex), then if that distance is < your 'expansion',
its 'inside'.  probably be a good idea to use an overall bounding box to
reject points that are far away to save a lot of overhead.

On Thu, Oct 14, 2010 at 3:00 PM, Josi Perez (3T Systems)
<josiperez3t@gmail.com> wrote:
> Hi,
>
> I use postgreSQL.8.4.2 and don't have postGIS installed.
> I have a geometric type polygon and I know that it is possible to determine
> if a point it is inside or not of this polygon, using anything like that:
> select
> polygon('(-23.5672,-46.6510),(-23.5670,-46.65095),(-23.5672,-46.6508),(-23.5672,-46.6510)')
> @> point('-23.567534,-46.64942')
>
> The question:
> Anyone knows an algorithm or have ideas how to determine if a point it is
> inside an area constructed by geometric type path expanded for a known
> distance?
> Graphically:
>
> the path
>             x=========x=======x
>
> the path expanded by a distance
>
>             |         | A     |
>             |         |       |
>      -------x=========x=======x-------  C
>             |         |       |
>         B   |         |       |
>
> the points A and B are inside and the point C are outside .

hm -- if the number of points in the path aren't terribly large, you
can bust this down to a a smaller number of components using available
tools in postgres.  For *each* path segment, construct a rectangle and
two circles at the end points:

   CRRRRC

If the point is inside the rectangle or either circle (both of those
operations can be solved conventionally in postgres), it's in your
area. If there are a lot of points or you are working with big data,
you should be looking at geometric library to do the work for you.

merlin