help wanted -- is the point in the polygon or isn't it?

[Joe Garvey]

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 at mips.com
990 Almanor Ave                  HP Desk: garvey (cmic at mips.com) /hp1900/ux
Sunnyvale, Ca, 94086             800-831-3104 (outside CA)
408-720-6439 (let it ring)       800-824-7814 (inside CA)