MATLAB: Determine if a point is inside a cube

cube

Hi! There are given 8 vertices of a cube and a random point. How can I define that the point lies inside the cube? I wanted to create 2 vectors from the random point. These vectors should be parallel to X and Y axis (Z is not needed here). Then, if vectors intersect with cube sides 4 times, then the point lies inside a cube. But this seems to be too complex approach for this problem. Does someone know a simpler way? A code snipped would be very helpful. Thanks.

Best Answer

The way I'd do it is to call convhulln(). Basically it gives you the vertices of your set of 3D vertices that are on the convex hull. The convex hull is what you'd get if you basically wrapped a balloon around your points.

So all you have to do is to pass in your cube coordinates concatenated with your "test" point and see if it returns the cube coordinates. If it doesn't then the point is outside. If it does, then the cube is the convex hull and that must mean your test point is inside the cube. It's one line of code to call convhulln() and another to do the check to see if what it returns matches your cube coordinates. You should be able to do it. If you can't then it's your turn to supply us with code that generates cube coordinates and test points (one inside and one outside) so that we can do those two lines for you.

Related Solutions

MATLAB: How to determine whether point lies within pyramid volume

Because the pyramid is regular, the algorithm is easy:

 E0 = [ 0,  0, 1];
 E1 = [ 1,  1, 0];
 E2 = [-1,  1, 0];
 E3 = [-1, -1, 0];
 E4 = [ 1, -1, 0];
 
 % Define the parameters of the pyramid:
 Pyramid.Z    = E0(3);
 Pyramid.Base = [min(E(:, 1)), max(E(:, 1)), min(E(:, 2)), max(E(:,2))]
 
 % Choose random points in the cuboid surrounding the pyramid:
 P = rand(10000, 3) .* [2, 2, 1] - [1, 1, 0];
 
 % Select points inside the pyramid:
 T = inPyramid(P, Pyramid);
 P = P(T, :);
 
 % Show the result:
 figure;
 plot3(P(:,1), P(:,2), P(:,3), '.')
 hold on
 plot3(E0(1), E0(2), E0(3), 'ro');
 plot3(E1(1), E1(2), E1(3), 'ro');
 plot3(E2(1), E2(2), E2(3), 'ro');
 plot3(E3(1), E3(2), E3(3), 'ro');
 plot3(E4(1), E4(2), E4(3), 'ro');
 xlabel('x')
 ylabel('y')
 zlabel('z')

For a point with at Z==0, you have to check, if it is inside the square. This square is shrinking linearily with the height until Z==1.

 function T = inPyramid(P, Pyramid)
 % P: 3D position as [N x 3] matrix
 % Pyramid: Struct, .Z: Height of pyramid
 %          .Base: minimum and maximum of X and Y positions at the
 %          base as [1 x 4] vector
 S = Pyramid.Base .* (Pyramid.Z - P(:, 3)) / Pyramid.Z;
 T = (P(:, 3) >= 0 & P(:, 3) <= Pyramid.Z) &     ... % Inside Z range
     (P(:, 1) >= S(:, 1) & P(:, 1) <= S(:, 2)) & ... % Inside X range
     (P(:, 2) >= S(:, 3) & P(:, 2) <= S(:, 4));      % Inside Y range
 end

This is elementary maths only.

A constructive approach instead of this rejection method:

https://www.mathworks.com/matlabcentral/answers/327990-generate-random-coordinates-inside-a-convex-polytope

MATLAB: Pretty simple question regarding convhulln. Now that I have K…

(Somebody should post a thing on the FEX explaining all the basics about convex hulls, tessellations, etc. One more thing to add to the round tuit list.)

Think in 2-d first. A convex hull of some data points is a simple polygon, composed of linear segments. Any vertex of the convex hull is also one of the data points. A convex hull does not introduce new points. So essentially a convex hull is just a set of references into the original set of points. Since these things are best done visually, lets generate an example.

>> xy = rand(8,2)
xy =
      0.80028      0.84913
      0.14189      0.93399
      0.42176      0.67874
      0.91574      0.75774
      0.79221      0.74313
      0.95949      0.39223
      0.65574      0.65548
     0.035712      0.17119
>> plot(xy(:,1),xy(:,2),'o')

See that there appear to be 5 of those points that lie on the boundary of the convex hull in this case, and 3 points lie clearly in the interior.

We can find the hull using either convhull, or convhulln.

>> convhull(xy(:,1),xy(:,2))
ans =
     1
     2
     8
     6
     4
     1
>> convhulln(xy)
ans =
     8     6
     6     4
     4     1
     1     2
     2     8

What do these numbers mean? Each index returned corresponds to ONE vertex of the hull polygon, but also to one of our original data points. Thus, the convex hull goes between the points [1 2 8 6 4 1] in the set IN THAT ORDER. The points that are inside the hull are of course then numbered [3 5 7].

See that each row of the array returned by convhulln is the same information, just in a slightly different form. It tells us that one edge of the hull is the edge [8 6], connecting point 8 and point 6. Then we connect points 6 and 4, with another edge, etc. These edges in the array returned from convhulln are given in no specific order, but they will be the same information overall as that returned by convhull.

The difference is that convhulln will work in any number of dimensions. (Ok, it can get pretty nasty to visualize in high dimensions. But 3 or 4 or 5 dimensions is entirely adequate. And we can't even draw pictures past 3-d anyway.)

So think about the 2-d case. The convex hull in 2-d is composed of "facets" composed of edges, line segments. In 3-d, the convex hull will always be composed of triangles. A 3-d convex hull will have planar facets. They will always break down into triangular facets though. Yes, one could imagine the set of points that comprise the unit 3-cube. (A cube in R^3.) Clearly its convex hull is a set of squares.

So here are the 8 vertices of the unit 3-cube.

V =
     0     0     0
     1     0     0
     0     1     0
     1     1     0
     0     0     1
     1     0     1
     0     1     1
     1     1     1

ndgrid could essentially help you to generate that list of points if you wanted.

Let us generate the convex hull using matlab. It is a set of triangles.

>> convhulln(V)
ans =
     4     3     1
     2     4     1
     6     2     1
     5     6     1
     6     4     2
     4     6     8
     3     7     1
     7     5     1
     4     7     3
     7     4     8
     7     6     5
     6     7     8

Each square has been split, into a pair of triangles. Since there are 6 square faces of a cube, there will be 12 triangles.

>> size(ans)
ans =
    12     3

If you prefer to visualize them this way, we can sort the triangles in increasing order of the vertices, and then use sortrows. This does not change the information in any serious way.

>> sortrows(sort(convhulln(V),2))
ans =
     1     2     4
     1     2     6
     1     3     4
     1     3     7
     1     5     6
     1     5     7
     2     4     6
     3     4     7
     4     6     8
     4     7     8
     5     6     7
     6     7     8

Still the same information. Each row is ONE triangle. A set of references into the original set of data points. In the case of the unit 3-cube of course, EVERY point lies one the surface, in at least a few of the triangles of that hull. In fact, depending on how those surface squares are split into triangles each point may lie in from 3 to 6 different triangles.

What you need to see is that a convex hull in 3-d is composed of triangles. If we go to higher dimensions, a convex hull in n-dimensions will be composed of (n-1)-simplexes. (A k-simplex is composed of k+1 points. So an (n-1)-simplex is defined by n vertices.) For example...

>> size(convhulln(rand(100,4)))
ans =
   290     4
>> size(convhulln(rand(100,5)))
ans =
        1068           5
>> size(convhulln(rand(100,6)))
ans =
        4047           6
>> size(convhulln(rand(100,7)))
ans =
       16094           7

See that each row of the result is a set of indexes into the original array of points, and that in n-dimensions, each row will be a facet, an (n-1) simplex. We can't plot these things on a 2-d monitor or piece of paper, but who cares?

Best Answer

Related Solutions

MATLAB: How to determine whether point lies within pyramid volume

MATLAB: Pretty simple question regarding convhulln. Now that I have K…

Related Question