garvey@cmic.UUCP (Joe Garvey) (06/08/90)
As part of a PROM function generator, I've got to determine if a point
is inside or outside an N-dimensional polygon (N-changes everytime the
program is invoked). The polygon in question is convex (any two points
inside the polygon can be connected by a line that doesn't go outside
the polygon).
In 2-D this is simple. Take a point at infinity (or definately outside
the polygon) connect the point in question to the point definately outside.
Then calculate the number of times that this line intercepts the line
segments in the polygon. If the number of intersections is even (0 is even)
then the point is outside the polygon. If the number of intersections is odd
then the point is inside the polygon. Actually for a convex 2-D polygon,
the only odd value you will get is 1. (BTW, this algorithm doesn't require
the polygon to be convex...)
How do I do this for the N-dimensional case? Anyone got a program, or a code
fragment? No it's not in my version of "Numerical Recipies". How about
a description of the calculations involved, or a reference to examine?
Of course you could save me a lot of effort if you had a program that
took a small sample of points and extrapolated/interpolated the rest for
the case:
F(x1, x2, ... xN) = (y1, y2, ... yM)
Where the x's are independent variables and the y's are dependent variables
and we've got a set of measurements of the function F.
--
Joe Garvey UUCP: {apple,backbone}!versatc!mips!cmic!garvey
California Microwave Internet: garvey%cmic@mips.com
990 Almanor Ave HP Desk: garvey (cmic@mips.com) /hp1900/ux
Sunnyvale, Ca, 94086 800-831-3104 (outside CA)
408-720-6439 (let it ring) 800-824-7814 (inside CA)