Return to 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 Robert'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.

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.

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.

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.

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 Robert'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.

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.

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-i}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.

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.

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.