Point in Polygon 3d (same plane) algorithm

Question

I have a point and a polygon in the same plane in 3d space and now I want to check whether or not the point is in the polygon or not. Is there an easy way to change the algorithm from this thread Point in Polygon Algorithm to work for 3d space? Or are there other algorithms that can solve this problem easily?

If there are not, would the following idea work: Check if the plane is the XZ-plane or the YZ-plane, if yes, ignore the other axis (i.e. for the XZ-plane ignore the y values) and use the pip algorithm from the before mentioned thread. And if no, just ignore the z values of the point and the polygon and use the pip algorithm.

Yes, projection onto appropriate coordinate plane (ignoring one coordinate) is the simplest way. — MBo, Jun 19 '20 at 18:11

Spektre · Answer 1 · 2020-06-23T07:29:30.580

there are 2 "basic" ways of testing planar concave polygon:

convert to set of convex ones and test direction of cross product between point and all faces

the conversion to convex polygon is not as easy but its doable either by triangulation or clipping ear or what ever method... After that just check the cross products... so if your convex polygon has vertexes p0,p1,p2,...,p(n-1) and testing point p then
```
d0 = cross( p-p0 , p0-p(n-1) );
for (i=1;i<n;i++)
    {
    di = cross( p-p(i), p(i)-p(i-1) );
    if ( dot ( d0 , di ) <=0.0 ) return false;
    }
return true;
```
so just check all the polygons and return OR of the subresults
use hit test

You cast ray from your point in any direction parallel to your plane and count the number of hits you ray has done with the edges of polygon. If its even point is outside if its odd point is inside. The link in your question uses this algo. However in 3D you need to change the direction so it still is inside plane... for example by using single edge of polygon dir=p1-p0 as your direction. You also have to code some rules for cases when your ray hits Vertex directly so its counted just once instead of multiple times. Also the hit must be computed in 3D so you need axis/line intersection. It can be found here:
- Cone to box collision
just look for line closest(axis a0,line l1) function. It returns line that is the closest connection between line and axis. Then just simply check if the two points are the same or not (length of the line is zero).

Now to simplify this you might port your 3D data into 2D

That can get rid of some accuracy problems related to rounding to the plane...

You are doing this by just ignoring one coordinate. That is simple but it might bring some rounding problems also the result has different shape (scaled differently in each axis) so the metrics is not the same anymore which might bring other problems latter if this is used for other purposes or any kind of thresholding is used.

There is a better method. We need any 2 basis vectors u,v that are perpendicular to each and are inside your plane and one point o inside the plane. That is easy just:

o = p0;    // any point from the polygon
u = p1-p0; // any edge of polygon
u /= |u|;  // normalize
v = p2-p1; // any other edge of polygon
v /= |v|;  // normalize
for (;fabs(dot(u,v)>0.75;) // if too parallel
    {
    v=(p(1+rand(n-1))-p0); // chose random "edge"
    v /= |v|;  // normalize
    }
v=cross(u,v); // make u,v perpendicular
v=cross(v,u); // and inside the plane
v /= |v|;     // normalize just in case because of rounding the size might not be unit anymore

Now to convert point p(x,y,z) from 3D to 2D (x,y) just do:

x = dot(p-o,u);
y = dot(p-o,v);

to convert back to 3D:

p = o + x*u + y*v;

With this way of conversion the metrics is the same so the length of polygon edges and size of polygon will not change ...

Point in Polygon 3d (same plane) algorithm

1 Answers1