point_in_polygon test
Eric Mitchell
emitchell at altaira.com
Thu Nov 11 10:51:56 EST 1999
http://www.snippets.org is a decent online collection of public domain
source code. You may find what you are looking for in there.
If not, a calculus text should be able to provide you with the algorithm
for making such a determination. Something to do with integrating the
change in angular displacement as you follow the line segments around
the polygon, IIRC. If the total angular displacement around the polygon
is zero the point is outside, if it's 2*pi the point is inside. This
algorithm works with all manner of polygon paths, too.
tyshih at cc.nctu.edu.tw wrote:
>
> The journal, 'Computers and Geosciences', would be a good
> place to search for this type algorithms. Related codes are
> frequently availabe from the web page of the journal as well.
> I don't have the url handy, but it may be find from yahoo or
> other search engine. The latest article related to point-in-polygon
> on this journal is,
>
> Polygon intersections in spherical topology: application to plate tectonics
> Schettino A
> COMPUTERS & GEOSCIENCES
> 25: (1) 61-69 FEB 1999
>
> Abstract:
> This paper describes a set of algorithms for performing overlay operations on polygonal regions in spherical topology. A
> solution to the intersection problem for a polygonal region on the unit sphere with respect to a base set of polygons is
> proposed. The method is based upon a variant of the point-in-polygon procedure and has been successfully used to
> reconstruct ancient ocean-floor age maps and plate boundaries. (C) 1999 Elsevier Science Ltd. All rights reserved.
>
> Best regards.
>
> Shih, T.Y.
>
> > >On Wed, 10 Nov 1999, Robb Hill wrote:
> > >
> > >> Can anyone offer advice? Any good books on these types of algorithms or
> > >> code?
> > >
> > >Robb,
> > >
> > > That's an excellent question! I, too, would like to have such a reference
> > >available. The last I heard -- and this goes back a dozen years when I first
> > >worked with ARC/Info -- is that the algorithms are rather closely held by
> > >those (like Jack Dagerman) who developed them. After all, the
> > >point-in-polygon and similar problems are why ESRI is able to charge the
> > >extremely high prices they do. It's also the reason why there are more
> > >raster-based analytical GISes than vector-based analytical offerings.
> > >
> > > Please let me know what you find out. Have you posted to GIS-L?
> > >
> > >Rich
> >
> >
> > This excercise seems to have confounded numerous folks in numerous areas of
> > endeavour it seems...I've appended two possible solutions (headers from
> > code) that I came across while searching for an answer some time ago. The
> > first is a simple minimalist solution, the second is a much more
> > sophisticated solution (can handle an array of polygons for the p_in_poly
> > test)...but will need more work to customise. If anybody else would like
> > the code (which can be freely and publicly distributed) let me know and
> > I'll forward same.
> >
> > Regards, Roderick
> >
> >
> > /***************************************************************************
> > * *
> > * INPOLY.C *
> > * *
> > * Copyright (c) 1995-1996 Galacticomm, Inc. Freeware source code. *
> > * *
> > * Please feel free to use this source code for any purpose, commercial *
> > * or otherwise, as long as you don't restrict anyone else's use of *
> > * this source code. Please give credit where credit is due. *
> > * *
> > * Point-in-polygon algorithm, created especially for World-Wide Web *
> > * servers to process image maps with mouse-clickable regions. *
> > * *
> > * Home for this file: http://www.gcomm.com/develop/inpoly.c *
> > * *
> > * 6/19/95 - Bob Stein & Craig Yap *
> > * stein at gcomm.com *
> > * craig at cse.fau.edu *
> > * *
> > ***************************************************************************/
> >
> >
> > /*************************************************************
> >
> > Copyright (c) 1995 Raimund Seidel
> > All rights reserved.
> >
> > This program is distributed WITHOUT ANY WARRANTY;
> > without even the implied warranty of MERCHANTABILITY or
> > FITNESS FOR A PARTICULAR PURPOSE.
> >
> > **************************************************************
> >
> >
> > A RANDOMIZED PLANAR POINT LOCATION STRUCTURE
> >
> > by R. Seidel
> >
> > last edited: 90 Feb 10
> >
> >
> > This file contains several routines for dealing with a general version
> > of the so-called planar point location problem, which can be described
> > as follows: one is to preprocess a set of non-vertical straight line
> > segments into a data structure so that for any given query point p one
> > can determine quickly which segment is the first one directly below p.
> > It is assumed that no two segments have interior points in common.
> >
> > The method employed is a randomized one that I have so far not gotten
> > around to write down formally in a paper. It has the property that
> > a search requires fewer than 4*ln(n) comparisons in expectation. It has
> > O(nlogn) expected preprocessing time and needs O(n) expected space.
> > All expectations are over "coin flips" in the algorithm and not over
> > assumed input distributions.
> >
> >
> >
> > The Test Program allows for two usages: either the input is a
> > set of segments as described above and for query points the next
> > segment below are returned, or the input is the sequence of corners
> > counter clockwise around a simple polygon and for query points it
> > is determined whether they lie inside this polygon or not.
> >
> > Just compile this file and run it. It should be fairly self-explanatory.
> >
> >
> > Some warnings: There is only minimal checking whether the input
> > is correct (whether there are improper intersections).
> > Although the program should not crash, the answers will not
> > be meaningful.
> > There is also no overflow checking. Currently everything
> > is done in terms of integer coordinates. Keeping their
> > magnitudes smaller than 2^15 will definitely avoid overflow.
> > Using a coordinate larger than `infinity' can cause a crash.
> >
> > Remarks:
> > The coordinate type can be changed from integer to something
> > else quite easily by changing the first 5 definitions. A change
> > to floating point will of course open the usual Pandora's box
> > of precision problems. However, they are refined to the two
> > macros point_above_segment and point_below_segment.
> >
> > These two macros along with segment_above_segment are also
> > the only things that would need to be adjusted if one wanted to
> > use this algorithm for segments that are not straight, but
> > still x-monotone.
> >
> >
> > For any remarks, complaints, etc. send email to
> >
> > seidel at lyra.berkeley.edu
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > _____________________________________________________________________
> >
> > Roderick Brown Tele: (Int+ 61 3) 9344-9868
> > School of Earth Sciences Dept.: (Int+ 61 3) 9344-7675
> > The University of Melbourne Facsimile: (Int+ 61 3) 9344-7761
> > Parkville, 3052 Home Telephone: (Int+ 61 3) 9397-8848
> > Australia Email: r.brown at earthsci.unimelb.edu.au
> >
> > ______________________________________________________________________
> >
> >
> >
> >
--
+=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+
| Eric B. Mitchell mailto:emitchell at altaira.com |
| tel: (301) 809 - 3534 Altair Aerospace Corporation |
| tel: (800) 7 - ALTAIR 4201 Northview Dr. Suite 410 |
| fax: (301) 805 - 8122 Bowie, MD 20716 |
+=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=+
,___
/"\ / o=\ /"""---===/
/ \_/ \__/ ---===/
| //\ || /""TT""/ //\ || ||""\
| // \ || || // \ || ||__/
| //--==\ |L--/ || //--==\ || || "=,
\ ---===/
\____---===/
More information about the grass-user
mailing list