Geek asks and answers

Find all points with integer coordinates inside the tetrahedron

I try to find all the points with integer coordinates that lie inside the tetrahedron (I want to somehow break through them). I know the coordinates of the four points (A, B, C, D) that define the tetrahedron.

What I'm doing now is to find the bounding box of the tetrahedron (the minimum and maximum coordinates x, y, z A, B, C, D), and then loop through all the points inside the bounding box. For each such point, I calculate the barycentric coordinates (using the equations from Wikipedia ) and check if the point is inside the tetrahedron (if any of the barycentric coordinates is negative or greater than 1, the point is not inside).

Is there a better way to do this? Currently, there is about a 1/6 probability that the point I'm testing (from the bounding box) really lies inside the tetrahedron, so I think I'm doing too many unnecessary calculations.

I am working with a list of tetrahedrons that I generated by triangulating a larger volume (I am expanding the volume and want to interpolate the missing values ​​using tetrahedral interpolation). I do not use external libraries.

+5
source share
2 answers

Another idea for improvement:

check if the "stick" passes in the direction of the z axis (i.e. x = 4, y = 6) through the tetrahedron. If not, then no values ​​with (x = 4, y = 5, z) can be inside.

, , (, , ).

, z = 1,3 z = 10,04. , (4,5, 2) - (4,5,10) .

x y.

, 1 .

+3

. , . :

, . , :

(, A, B, C). (C-A) x (B-A) ( ). (a, b, c), F(x,y,z) = ax+by+cz = 0. (x0, y0, z0) F (x0, y0, z0) , .

, , , "", 4 ( ), 3 2 .

+3

More articles:


All Articles