How to find all points in a given 3D shape

Question

Consider a 3D space, we only study integer points . And then we are given 3 basis vectors (non-orthogonal, of cause) by which we can obtain a 3D crooked cubic (how to call that in English?). The question is: how to find out all the points inside this crooked cubic? I want to find a way to scan all points near the target space. But I don't know how.

Recently I have some idea to approach to the solution. The solution point must satisfy a equation that where ) for i=1,2,3 (x_i can=0 is my other consideration, that's fine). So the problem is concluded to find the solution of where A and b are all integer matrix and the first row of is , the second row ...

Then I have no ideal what to do next. A super naive solution is to choose a very large space B, and check each point b in B to see if there is a x to satisfy Ax=b.

Is there a better way?

Answer 1

A basis like {a1,a2,a3} do not define a parallepiped, but the full 3D space. It's just a different "coordinates-system" from typical orthogonal system.

Any point P(px,py,pz) can be expressed as a combination of base-vectors:

P= u1·a1 + u2·a2 + u3·a3

This vector equation is expressed in matrix form [P]=[A]·[u] by expanding each vector to its x,y,z components. [u] is a column matrix.

To find the [ui] vector for point Pi you must invert (i.e. get [A^-1]) the matrix [A], and then [ui]=[A^-1]·[Pi]

The thing is that we can consider a point to be "inside" the axis if all of u1,u2,u3 are >= 0

So, to check your collection of points (coords given in cartesian system) you calculate the [ui] componentes for each point Pi and check if some component is < 0.

Note:
If all ux,uy,uz belong to [0,1] range it means that P is inside a parallepiped (6 faces, edges parallel to axis) whose vertices are defined by start (0,0,0) and end (aix,aiy,aiz) points.
Don't confuse with "normalized length" (Length=1): If all a1,a2,a3 vector have length=1 then you have a "unitary basis"