Re: polygons

From: Gerry Creager <gerry.creager_at_nyahnyahspammersnyahnyah>
Date: Wed, 22 Jul 2009 08:28:38 -0500

Vertex crossings are treated as a "0" or even crossing. Zero can be
defined as "even"

Nice summary. The GIS geeks try to claim the algorithm as their own.


Dave Allured wrote:
> Michael,
> I vaguely recall the following algorithm from computer graphics.
> Extend a line from a given test point in the plane, to infinity.
> Count the number of times that it crosses an outline segment of the
> given polygon. If the final count is an odd integer, then the point
> is within the polygon. If the count is even, then the point is outside.
> The advantage is that this algorithm works for polygons of any
> complexity, including concave and disjoint polygons (i.e. multiple
> regions). There are details about crossing at vertices and
> computational efficiency that I can't speak to. See if you can find
> a better description elsewhere.
> If you would like, I can post a working NCL example that converts a
> polygon to a grid mask. It uses a different algorithm which works
> *only* for simple convex polygons that are not disjoint. I am
> afraid that this will not be adequate for your tree mapping polygons.
> Dave Allured
> CU/CIRES Climate Diagnostics Center (CDC)
> NOAA/ESRL/PSD, Climate Analysis Branch (CAB)
>> I have a shapefile with a bunch of individual polygons and the associated
>> lat/lons for many points defining each polygon. I have already been able
>> to reach those values into NCL. They define the area of N. America
>> covered by a specific tree specie.
>> Now I want to generate a 0.25x0.25 degree grid with 1's if the tree is found
>> there and 0's if the tree is not. So, basically I need to know if each 0.25 degree
>> grid cell is within these polygons, meaning the tree is found there.
>> Could anyone recommend a method to do this? I have some ideas but none that
>> seem very satisfactory or won't take forever to run (actually I need to do this
>> for 170 tree species). The main challenge is knowing if a grid cell is within a polygon
>> of points and then repeating this for each grid cell and all polygons.
>> Thanks, Michael
> _______________________________________________
> ncl-talk mailing list
> List instructions, subscriber options, unsubscribe:

Gerry Creager --
Texas Mesonet -- AATLT, Texas A&M University	
Cell: 979.229.5301 Office: 979.458.4020 FAX: 979.862.3983
Office: 1700 Research Parkway Ste 160, TAMU, College Station, TX 77843
ncl-talk mailing list
List instructions, subscriber options, unsubscribe:
Received on Wed Jul 22 2009 - 07:28:38 MDT

This archive was generated by hypermail 2.2.0 : Thu Jul 23 2009 - 08:02:42 MDT