- make suggestions
- ask questions
- present your own code
Documentation and code are here:
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
Various writers have strong opinions about additions, such as that points on the boundary should be handled. I disagree, for reasons listed in the page linked above. However, feel free to argue your case here.
2 comments:
A couple of comments, and a couple of questions:
* I admire the simplicity of your code which has stood the test of time; and has been incorporated in packages such as numpy
* I am not concerned as to whether a point lies exactly on the boundary or not
The particular application I have in mind is to have my software developers (using OSGB x,y co-ordinates) whether a point is within Scotland or not. The results of this are:
* The co-ordinates will therefore all be positive;
* The point (0,0) will definitley lie outside the area of interest;
* The boundary shape will have multiple polygons
* All the points will be stored in a database, and pulled from the database to cary out
* A good description of the boundary may therefore have 100,000 points or more in it.
While the algorithm is clearly O(n), was wondering as to the merits (to be tested) of only pulling boundary segments of interest from a database query first....
Storing boundary data as:
segment Pi Pj
1 x0,y0, x1,y1
2 x1,y1, x2,y2
3 x2,y2, x3,y3
..
n x(n-1),y(n-1), x0,y0
and only pulling segments for the test where
ytest >= min(yi,yj) AND ytest <= max(yi,yj)
as databases are quite efficient at that sort or thing.
Ditto, with that sort of 'duplicated' layout - you wouldn't need to draw a line to (0,0) at the beginning an end of each polygon - as only the relevant Pi,Pj pairs would get fed directly to the test.
The link to the code and commentary (http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html) is broken.
Post a Comment