Re: polygons

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.

gerry

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)
> http://cires.colorado.edu/science/centers/cdc/
> NOAA/ESRL/PSD, Climate Analysis Branch (CAB)
> http://www.cdc.noaa.gov/psd1/
>
> MICHAEL NOTARO wrote:
>> 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:
> http://mailman.ucar.edu/mailman/listinfo/ncl-talk

-- 
Gerry Creager -- gerry.creager_at_tamu.edu
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:
http://mailman.ucar.edu/mailman/listinfo/ncl-talk