| Point/Polygon Routine [message #5401] |
Tue, 02 January 1996 00:00  |
cavanaug
Messages: 18
Registered: December 1994
|
Junior Member |
|
|
Does anyone have a routine that determines if a given 2-D point is inside a
given 2-D polygon?
Thanks in advance.
Charles Cavanaugh
--
Charles Cavanaugh | "Words are very unnecessary, they can only do harm"
cavanaug@ncar.ucar.edu | - Depeche Mode
NCAR Boulder, CO, USA | "Facts all come with points of view"
My opinions | - Talking Heads
|
|
|
|
| Re: Point/Polygon Routine [message #5573 is a reply to message #5401] |
Tue, 09 January 1996 00:00  |
tildes
Messages: 2
Registered: June 1993
|
Junior Member |
|
|
In article 760@ncar.ucar.edu, cavanaug@uars1.acd.ucar.edu (Charles Cavanaugh) writes:
>
> Does anyone have a routine that determines if a given 2-D point is inside a
> given 2-D polygon?
>
> Thanks in advance.
>
>
> Charles Cavanaugh
> --
> Charles Cavanaugh | "Words are very unnecessary, they can only do harm"
> cavanaug@ncar.ucar.edu | - Depeche Mode
> NCAR Boulder, CO, USA | "Facts all come with points of view"
> My opinions | - Talking Heads
I dont have any IDL code for doing this but I can outline a method that is
pretty straightforward.
Consider a line from the point in question to plus (or minus) infinity.
Count the intersections between this line and each of the edges of the polygon.
If the total count is zero or even then the point is outside the polygon.
If the total count is odd then the point is inside the polygon.
The only traps to watch out for are:
- where the point is on one of the edges or vertices.
- if the line to infinity goes through one of the vertices (you should only
count one end of each edge as being a part of that edge).
Good luck.
____________________________________________________________ __
Paul Tildesley
Remote Sensing Facility, CSIRO Division of Oceanography
voice : (002) 325-251 (international) +61 02 325251
fax : (002) 325-123 (international) +61 02 325123
email : Paul.Tildesley@ml.csiro.au
post : GPO Box 1538, Hobart, Tasmania 7001, AUSTRALIA
____________________________________________________________ __
|
|
|
|
| Re: Point/Polygon Routine [message #5596 is a reply to message #5401] |
Wed, 03 January 1996 00:00 |
jlaw
Messages: 11
Registered: November 1995
|
Junior Member |
|
|
In article 760@ncar.ucar.edu, cavanaug@uars1.acd.ucar.edu (Charles Cavanaugh) writes:
>
> Does anyone have a routine that determines if a given 2-D point is inside a
> given 2-D polygon?
I did have, but I left it behind when I changed jobs.
Are you any good at finite elements??( This is where I looked this up)
Consider a triangle of points I,J,K with coordinates
( Xi,Yi) , (Xj,Yj ) , (Xk,Yk).
the Area of the triangle is then
( 1 Xi Yi )
0.5 * det ( 1 Xj Yj )
( 1 Xk Yk )
Now take the point P at ( Xp, Yp ).
( Strictly, if P is inside the triangle) we can define "Area coordinates"
as follows:
Li = area(pjk) / area(ijk)
Lj = area(pki) / area(ijk)
Lk = area(pij) / area(ijk)
If P is indeed inside the triangle, all the area coordinates are positive.
But if P is outside the triangle, one or more is negative.
For a polygon, split it into a set of triangles. If the point is inside one
of the triangles, it must be inside the polygon.
I think this all depends on the points being placed in the correct sense
around the triangle ( ie clockwise or anticlockwise.)You had better experiment
a little, but that is the basic principle.
It is not actually many lines of code.
all the best
f.
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
