Successive Inner or Outer Approximation of Simple Polygons with Hierarchies of Implicit Functions

Question

The problem I want to solve, is to quickly decide, whether a point $p=(x^*,y^*)$ is inside or outside of a polygon $P := (p_1, p_2,..., p_n=p_1), p_i := (x_i,y_i)$, with $n$ potentially very large.

Edit:
In view of Joseph's answer, I see the need to give some additional information about what the actual situation is.

• The polygons I encounter, have an approximately fractal boundary and an otherwise fairly well behaved shape, i.e. the difference between the area of the largest enclosed and the smallest enclosing convex polygon is 'small'. This well behavedness of shape is the reason for looking at implicit functions e.g. largest enclosed and smallest enclosing ellipse.
• The number of point in polygon queries is extremely high, so that any kind of preprocessing pays off for a sufficiently large number of queries
• the probability of a point to be in polygon $P$ is not known, but suggestions for inclusion tests, that are optimal on average, may assume a known probability.

(end of edit)

My idea was to try to find the series-expansion of a bivariate function $f(x,y)$ with the following properties:

• $f(x,y) := \sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_{ij}x^iy^j$
• $\sum_{i=0}^{n}\sum_{j=0}^{n}a_{ij}x^iy^j=0$ resembles a jordan curve, that does not intersect the polygon $P$
• if the jordan curve encloses the polygon, then the enclosed area should be minimal and maximal if the jordan curve is inside the polygon.
• the jordan curves related to different partial sums should be nested

Questions:

• are there better functions than the one's resembling the Schwarz-Christoffel mapping http://en.wikipedia.org/wiki/Schwarz%E2%80%93Christoffel_mapping of a circle to the polygon $P$?
• are there practical methods of determining such functions?

Note: I formulated the series expansion as a Taylor series but other expansions would also be appreciated.

Computational Geometry solutions that aim at minimizing the average time that is needed for a point-in-polygon query in the above setting are also welcome.

Answer 1

This problem is called the point-in-polygon problem in the graphics and computational geometry literature, and searching that phrase will bring you to much discussion and working code. It is rather firmly established that the best method is the ray-shooting algorithm, described, e.g., in Wikipedia here.
      
Straightforward implementation runs in $O(n)$ time, and you can find this all over the web, including my own implementation here. If you are going to repeatedly query, sophisticated data structures will allow $O(\log n)$ per query.

Answer 2

From a computational geometry point of view, this article http://compgeom.com/~piyush/papers/occluder.pdf that I just found, comes closest to what I need.