Considering a convex polygon lying on a plane in 3D space, how can I know if a point on that plane lies inside or outside that polygon?

Question

I have a plane in space and a polygon in it. I know the position of each vertices making the polygon. I also know the position of the point on the plane. How can I know whether the point is inside or outside the polygon?

Answer 1

Here's a quick, although not efficient, solution:

1. Find the median of the polygon points; call it $P$.

2. For each of the polygon points $Q_i$, define $r_i = Q_i - P.$ Compute $$ n = r_1 \times r_2\\ u = r_1\\ w = n \times v $$

3. Express the $r_i$ in terms of $u$ and $w$; fior the unknown point $Q$, express it that way too: $$ x_i = r_i \cdot u \\ y_i = r_i \cdot v \\ x = (Q-P) \cdot u \\ y = (Q - P) \cdot v $$

Now you have the simpler problem of determining whether the point $(x, y)$ lies withing the polygon formed by the points $(x_i, y_i)$ in the plane. A nice solution is to compute the winding number, but simpler, in general, is to look at a ray from $(x, y)$ in a random direction $h$, it should intersect the polygon in 0, 1, or 2 points. (If it intersects in more, or one of the intersections is a vertex, pick a new random $h$. With probability one, it'll be a good one). The point Q is inside iff the ray intersects the polygon in a single non-vertex point. (Here "inside" means "inside or on the boundary", and I'm assuming a closed ray, i.e., one that includes the starting point).

Answer 2

Assuming you have Cartesian coordinates $(x,y,z)$ for each point, to reduce this to a two-dimensional problem, you can simply choose a coordinate axis that is not parallel to the plane in which the polygon lies, and remove that coordinate from all points. For example, if the plane is not parallel to the $z$ axis, consider just the coordinates $(x,y)$ at each point.

The result will be an orthogonal projection of your point and your polygon. The original point is inside the original polygon if and only if the projected point is inside the projected polygon.

Answer 3

The following solution is elegant and efficient, and relatively simple to implement. First the idea, then the algorithm.

Consider a point $x$ and an $n$-sided convex polygon $P$ with ordered boundary vertices $(p_1, p_2, ... p_n)$, all lying in a plane in 3D space. We want to know whether $x$ lies inside $P$, outside of it, or on its boundary.

Notice that triangles can be constructed using $x$ and any pair of adjacent $p_i$ and $p_{i+1}$. If $x$ lies inside the polygon, then the normals of all triangles $(x,p_i,p_{i+1})$ point in the same direction.

Now the algorithm. First, calculate the cross-product $N = (p_1 - x) \times (p_2 - x)$; we will consider $N$ to be the normal direction of $P$, and compare all other normals against it.

Next, we compute all remaining $(p_i - x) \times (p_{i+1} - x)$. Each of these cross-products either points in the same direction as $N$, or in the direction of $-N$. To find out in which way they point, we take the dot product of $(p_i - x) \times (p_{i+1} - x)$ with $N$. If every dot product $\left((p_i - x) \times (p_{i+1} - x)\right)\cdot N$ is positive, then $x$ lies inside $P$; if at least one dot product is negative, then $x$ lies outside of $P$; if a dot product is zero for some $p_i, p_{i+1}$, then $x$ lies on the boundary of the polygon; in particular, it lies on the edge connecting $p_i$ to $p_{i+1}$.