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?
>
>RichThis 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@gcomm.com *
* craig@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@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@earthsci.unimelb.edu.au______________________________________________________________________