Java——判断点是否在四面体内/立方体内

1、假设有一个四面体，四个顶点定义：

V1 = (x1, y1, z1)
V2 = (x2, y2, z2)
V3 = (x3, y3, z3)
V4 = (x4, y4, z4)

要检测的点定义为：P = (x, y, z)

可以根据这些点组成的4个行列式来进行判断：

D0

|x1 y1 z1 1|
|x2 y2 z2 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

D1

|x y z 1|
|x2 y2 z2 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

D2

|x1 y1 z1 1|
|x y z 1|
|x3 y3 z3 1|
|x4 y4 z4 1|

D3

|x1 y1 z1 1|
|x2 y2 z2 1|
|x y z 1|
|x4 y4 z4 1|

D4

|x1 y1 z1 1|
|x2 y2 z2 1|
|x3 y3 z3 1|
|x y z 1|

判据：

如果Di (i=1,2,3,4)与D0的符号都相同，即同为正，或同为负，那么P点就在四面体内部；

否则P点在四面体外部。


2、算法的Java实现：

/**
	 * 判断点是否在四面体内
	 * 
	 * @param point
	 *            含有三个元素的数组，表示点的坐标
	 * @param box
	 *            4X3的二维数组，四面体四个顶点的坐标
	 * @return
	 */
	static boolean pointInTetrahedron(double[] point, double[][] box) {
		// 标志点是否在四面体内
		boolean flag = true;
		// 扩展四面体矩阵，最后增加一列，数值全为1
		double[][] ts = new double[4][4];
		for (int j = 0; j < ts.length; j++) {
			for (int j2 = 0; j2 < ts.length - 1; j2++) {
				ts[j][j2] = box[j][j2];
			}
			ts[j][3] = 1;
		}
		// 查看扩展后的矩阵
		System.out.println("扩展的四面体为：");
		for (int i = 0; i < ts.length; i++) {
			for (int j = 0; j < ts.length; j++) {
				System.out.print(ts[i][j] + " ");
			}
			System.out.println();
		}
		// 用点的坐标分别替换四面体的点坐标，得到新的矩阵
		for (int i = 0; i < ts.length; i++) {
			// 数组的深度拷贝
			// 注意：对于一维数组可以直接使用clone()进行复制，
                        //但是对于二维数组必须对每一行进行深度复制才行
			double[][] ti = new double[ts.length][ts[0].length];
			for (int j = 0; j < ts.length; j++) {
				ti[j] = ts[j].clone();
			}
			// 点坐标替换四面体的点坐标
			ti[i][0] = point[0];
			ti[i][1] = point[1];
			ti[i][2] = point[2];
			// 输出新的矩阵
			System.out.println("替换的四面体为：");
			for (int im = 0; im < ts.length; im++) {
				for (int j = 0; j < ts.length; j++) {
					System.out.print(ti[im][j] + " ");
				}
				System.out.println();
			}
			// 如果点坐标替换之后的矩阵与原四面体矩阵两者符号不同，P点不在四面体内
			if (determinant(ts) * determinant(ti) < 0) {
				flag = false;
				break;
			}
		}
		return flag;
	}

3、上面判断了点是否在多面体内，以来上面的程序，就可以进行点与长方体关系的判断。

算法原理：

(1)首先将长方体划分为四面体（每个长方体划分为5个四面体）
(2)分别判断点与以上四面体的关系，只有点不在任意一个四面体时，表示点不在长方体内。

程序实现如下：

/**
      * 判断点是否在长方体内
      * 首先将长方体划为5个四面体，分别判断点是否在这几个四面体内
      * 如果这个点在任何一个四面体内部，那么这个点就在这个多面体内部；
      * 如果这个点不在任何一个四面体内部，那么这个点就不在这个多面体内部。
      * @param point  点的坐标
      * @param box  长方体的三个基矢
      * @return
      */
     public static boolean pointInBox(double[] point,double[][] box){
    	    //标志点是否在长方体内，true表示点在长方体内，false不在
	     	boolean flag=true;
	     	//将长方体划分为五个四面体
	     	double[][] t0={{box[0][0],box[0][1],box[0][2]},
	  			       {box[2][0],box[2][1],box[2][2]},
	  			       {box[2][0]+box[0][0],box[2][1]+box[0][1],box[2][2]+box[0][2]},
	  			       {box[0][0]+box[1][0]+box[2][0],box[0][1]+box[1][1]+box[2][1],box[0][2]+box[1][2]+box[2][2]}};
	  	
	    	double[][] t1={{box[0][0],box[0][1],box[0][2]},
	     			   {box[1][0],box[1][1],box[1][2]},
	     			   {box[2][0],box[2][1],box[2][2]},
	     			   {box[0][0]+box[1][0]+box[2][0],box[0][1]+box[1][1]+box[2][1],box[0][2]+box[1][2]+box[2][2]}};
	    	
	    	double[][] t2={{box[0][0],box[0][1],box[0][2]},
	     			   {box[1][0],box[1][1],box[1][2]},
	     			   {box[0][0]+box[1][0],box[0][1]+box[1][1],box[0][2]+box[1][2]},
	     			   {box[0][0]+box[1][0]+box[2][0],box[0][1]+box[1][1]+box[2][1],box[0][2]+box[1][2]+box[2][2]}};
	     	
	    	double[][] t3={{box[2][0],box[2][1],box[2][2]},
	  			       {box[1][0],box[1][1],box[1][2]},
	  			       {box[2][0]+box[1][0],box[2][1]+box[1][1],box[2][2]+box[1][2]},
	  			       {box[0][0]+box[1][0]+box[2][0],box[0][1]+box[1][1]+box[2][1],box[0][2]+box[1][2]+box[2][2]}};
	     	
	     	double[][] t4={{0,0,0},
	     			   {box[0][0],box[0][1],box[0][2]},
	     			   {box[1][0],box[1][1],box[1][2]},
	     			   {box[2][0],box[2][1],box[2][2]}};
	     
	       //点不在任意一个四面体内，说明点不在该长方体内	
	       boolean f1=pointInTetrahedron(point, t0);
	       boolean f2=pointInTetrahedron(point, t1);
	       boolean f3=pointInTetrahedron(point, t2);
	       boolean f4=pointInTetrahedron(point, t3);
	       boolean f5=pointInTetrahedron(point, t4);
	       System.out.println(f1+"  "+f2+"  "+f3+"  "+f4+"  "+f5);
	       if(!pointInTetrahedron(point, t0)&&!pointInTetrahedron(point, t1)&&
	    		   !pointInTetrahedron(point, t2)&&!pointInTetrahedron(point, t3)&&
	    		   !pointInTetrahedron(point, t4)){
	    	   flag=false;
	       }
	     	return flag;
	     }