# Re: polygons

From: Michael Notaro <mnotaro_at_nyahnyahspammersnyahnyah>
Date: Tue, 21 Jul 2009 14:06:34 -0500

Thanks

On Jul 21, 2009, at 1:52 PM, 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)
> 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

_______________________________________________
ncl-talk mailing list
List instructions, subscriber options, unsubscribe:
http://mailman.ucar.edu/mailman/listinfo/ncl-talk
Received on Tue Jul 21 2009 - 13:06:34 MDT

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