c++algorithmgeometrycomputational-geometry

Check if a 3D point lies inside a 3D platonic solid?


Are there any known methods for quickly and efficiently determining if a 3D point lies within a platonic volume of a known size?

This seems easy enough to do with a cube (hexahedron) or a circle (ellipsoid). I can't seem to figure it out for a tetrahedron, octahedron, dodecahedron, or an icosahedron. I'm guessing it might be possible to break the shapes down into several sub-solids and then check each one, but I'd like to avoid any kind of iterative solver if possible.


Solution

  • A simple way is to represent the solid as the intersection of semispaces.

    A plane in 3d has implicit equation:

    ax + by + cz + d = 0
    

    where (a, b, c) is the plane normal and d is the value of -(a*x + b*y + c*z) for any point of the plane (the computed value will not depend on which point you choose).

    For points in space on one side of the plane the result of a*x+ b*y + c*z + d will be negative, on the other side the result will be positive instead.

    A platonic solid (any convex solid) can be represented as the points of space that are on the non-positive side of all faces, i.e.

    a[i]*x + b[i]*y + c[i]*z + d[i] <= 0
    

    thus a reasonably fast test could be:

    struct Plane {
        double a, b, c, d;
    };
    
    struct Point {
        double x, y, z;
    };
    
    int side(const Point pt, const Plane& pl) {
        double v = pt.x*pl.a + pt.y*pl.b + pt.z*pl.c + pl.d;
        if (v < -EPS) return -1;
        if (v > EPS) return 1;
        return 0;
    }
    
    struct ConvexSolid {
        std::vector<Plane> planes;
    
        bool contains(const Point& pt) const {
            return std::all_of(planes.begin(), planes.end(),
                               [&](const Plane& pl){
                                   return side(pt, pl) <= 0;
                               });
        }
    };
    

    In addition if you know that most of your points will be inside the solid adding a quick-accept test may be a good idea. Consider the center and the distance from the faces... if your point is inside the sphere centered in the center and with that radius then for sure is inside the solid too.

    Therefore, if you expect many of the points to be inside that sphere, checking for it first can be a good investment as it only takes to check

     r2 = (x-xc)*(x-xc) + (y-yc)*(y-yc) + (z-zc)*(z-zc)
    

    that should be slightly more than the cost of checking a single plane.

    Note however that if most points are NOT inside that sphere then doing this check will be indeed a pessimization.

    Another speedup would be to consider also the bounding sphere with the same center... in this case you only can use the same r2 computation to do a "band" checking and you will need to run the full check only if r2 > r2min (i.e. if the point is not inside the inner sphere) and if r2 < r2max (i.e. if the point is not outside the outer sphere).