# Re: polygons

From: Dave Allured <dave.allured_at_nyahnyahspammersnyahnyah>
Date: Tue, 21 Jul 2009 12:52:46 -0600

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)
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
Received on Tue Jul 21 2009 - 12:52:46 MDT

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