CODEWITHSUNDEEP
c++algorithmgeometrycomputational-geometry
CMPXCHG8B
CMPXCHG8B

Reputation: 497

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.

Upvotes: 3

Views: 2215

Answers (4)

dfrib
dfrib

Reputation: 73206

The point in polygon is very well known problem in the context of finding if a 2D point lies within any type of polygon (2D space). See e.g.

The problem of point in polyhedra (3D) is---for the case of any kind of polyhedra---quite a bit tricker. In your case, however, you are strictly considering convex polyhedra, as all platonic solids are a of the latter type.

In this case, I could point you to two methods for solving this problem.

1 : (General method for any convex polytope) You can consider your problem as finding if a point is within the convex hull of a set of known points, where, in your case, your points are the vertices of your platonic solid, and they exactly describe the convex hull of themselves (no "interior" vertices, due to convexity). General solutions to how to implement this problem has been discussed e.g. here:

2 : As mentioned above, the 2D point in polygon is well-studied, and you can even find C++ code for it in the SO link I provided above. Since you are considering convex polyhedra in 3D, we know that the intersection of a 2D plane cutting through such a polyhedra will describe a convex polygon. So, for each point you want to investigate, you create plane which contains the point, and which intersect the polyhedra (your platonic solid): the remaining problem is then solving the "2D point within a polygon problem", on this plane.

Upvotes: 1

6502
6502

Reputation: 114579

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).

Upvotes: 5

Minor Threat
Minor Threat

Reputation: 2095

If you're looking for an optimized algorithm you may try to check if the point lies outside of the bounding sphere of your solid and check against surfaces only when it doesn't.

Upvotes: 3

gen-y-s
gen-y-s

Reputation: 881

draw a line from the point to somewhere outside the shape, and count how many of its surfaces it passes thru. If the number is odd, the point is inside, otherwise it's outside.

QED

Upvotes: 0

Related Questions