//A newer, more generalized vector collison test! This time, we are testing 1. if an n-dimensional point is within a polygon with n+1 vertices AND if a vector intersects with an n-1 dimensional plane defined by n points!


class point2{

	public float x, y;

	point2(float givenX, float givenY){

		x = givenX;
		y = givenY;

	}

	public String toString(){ return "X: " + x + "; Y: " + y + ";"; }


	//returns z component of 3d cross product of 2d vectors with the assumption that z of each of them is 0.
	public static float crossProductZ(point2 vector1, point2 vector2){

		return((vector1.y * vector2.x) - (vector1.x * vector2.y));

	}

}

class point3{

	public float x, y, z;

	point3(float givenX, float givenY, float givenZ){

		x = givenX;
		y = givenY;
		z = givenZ;

	}

	public String toString(){ return "X: " + x + "; Y: " + y + "; Z: " + z + ";"; }

	//returns w component of 4d cross product of 3d vectors with the assumption that w of each of them is 0.
	public static float crossProductW(point3 vector1, point3 vector2, point3 vector3){

		return(	(vector1.x * vector2.y * vector3.z) -
			(vector1.x * vector2.z * vector3.y) -
			(vector1.y * vector2.x * vector3.z) +
			(vector1.y * vector2.z * vector3.x) +
			(vector1.z * vector2.x * vector3.y) -
			(vector1.z * vector2.y * vector3.x)	);

	}

}

class triangle{

	public point2 p1, p2, p3;

	triangle(point2 given1, point2 given2, point2 given3){

		p1 = given1;
		p2 = given2;
		p3 = given3;

	}

	public static boolean isInside(point2 p, triangle t){

		point2 temp1, temp2, tempp;

		//step 1: translate triangle such that p1 is origin

		temp1 = new point2(t.p2.x - t.p1.x, t.p2.y - t.p1.y);
		temp2 = new point2(t.p3.x - t.p1.x, t.p3.y - t.p1.y);
		tempp = new point2(p.x - t.p1.x, p.y - t.p1.y);

		//step 2: check if angle of vector tempp is between vectors temp1 and temp2

		//we can do this by checking if the signs of the cross products between temp1 & tempp have the same sign as between temp1 & temp2, and again for temp2 & tempp and temp2 & temp1!
		if(
			(point2.crossProductZ(temp1, tempp) * point2.crossProductZ(temp1, temp2) <= 0) ||
			(point2.crossProductZ(temp2, tempp) * point2.crossProductZ(temp2, temp1) <= 0)){

			return false;

		}

		//finally, we do it again using another point as the origin.

		temp1 = new point2(t.p1.x - t.p2.x, t.p1.y - t.p2.y);
		temp2 = new point2(t.p3.x - t.p2.x, t.p3.y - t.p2.y);
		tempp = new point2(p.x - t.p2.x, p.y - t.p2.y);

		if(
			(point2.crossProductZ(temp1, tempp) * point2.crossProductZ(temp1, temp2) <= 0) ||
			(point2.crossProductZ(temp2, tempp) * point2.crossProductZ(temp2, temp1) <= 0)){

			return false;

		}

		return true;

	}

}

class tetrahedron{

	public point3 p1, p2, p3, p4;

	tetrahedron(point3 given1, point3 given2, point3 given3, point3 given4){

		p1 = given1;
		p2 = given2;
		p3 = given3;
		p4 = given4;

	}

	public static boolean isInside(point3 p, tetrahedron t){

		point3 temp1, temp2, temp3, tempp;

		//Step 1: translate
		temp1 = new point3(t.p1.x - t.p4.x, t.p1.y - t.p4.y, t.p1.z - t.p4.z);
		temp2 = new point3(t.p2.x - t.p4.x, t.p2.y - t.p4.y, t.p2.z - t.p4.z);
		temp3 = new point3(t.p3.x - t.p4.x, t.p3.y - t.p4.y, t.p3.z - t.p4.z);
		tempp = new point3(p.x - t.p4.x, p.y - t.p4.y, p.z - t.p4.z);

		//Step 2: check if between vectors
		if(
			(point3.crossProductW(temp1, temp2, tempp) * point3.crossProductW(temp1, temp2, temp3) <= 0 )||
			(point3.crossProductW(temp2, temp3, tempp) * point3.crossProductW(temp2, temp3, temp1) <= 0 )||
			(point3.crossProductW(temp3, temp1, tempp) * point3.crossProductW(temp3, temp1, temp2) <= 0 )){

			return false;

		}

		//Step 3, 4, 5, & 6: Do it again twice

		temp1 = new point3(t.p1.x - t.p2.x, t.p1.y - t.p2.y, t.p1.z - t.p2.z);
		temp2 = new point3(t.p3.x - t.p2.x, t.p3.y - t.p2.y, t.p3.z - t.p2.z);
		temp3 = new point3(t.p4.x - t.p2.x, t.p4.y - t.p2.y, t.p4.z - t.p2.z);
		tempp = new point3(p.x - t.p2.x, p.y - t.p2.y, p.z - t.p2.z);

		if(
			(point3.crossProductW(temp1, temp2, tempp) * point3.crossProductW(temp1, temp2, temp3) <= 0 )||
			(point3.crossProductW(temp2, temp3, tempp) * point3.crossProductW(temp2, temp3, temp1) <= 0 )||
			(point3.crossProductW(temp3, temp1, tempp) * point3.crossProductW(temp3, temp1, temp2) <= 0 )){

			return false;

		}

		return true;

	}

}

class plane2{

	point2 p1, p2;

	plane2(point2 given1, point2 given2){

		p1 = given1;
		p2 = given2;

	}

	public static boolean doesIntersect(point2 vector, plane2 plane){

		//Step 1: check if vector is between the vertices of the plane! (If the vector goes towards the plane)
		if(
			(point2.crossProductZ(plane.p1, vector) * point2.crossProductZ(plane.p1, plane.p2) <= 0) ||
			(point2.crossProductZ(plane.p2, vector) * point2.crossProductZ(plane.p2, plane.p1) <= 0)){
			return false;

		}

		//Step 2: check if the point is outside of the triangle formed by the plane and the origin
		point2 temp1, temp2, tempp;

		temp1 = new point2(0 - plane.p1.x, 0 - plane.p1.y);
		temp2 = new point2(plane.p2.x - plane.p1.x, plane.p2.y - plane.p1.y);
		tempp = new point2(vector.x - plane.p1.x, vector.y - plane.p1.y);

		if(
			(point2.crossProductZ(temp1, tempp) * point2.crossProductZ(temp1, temp2) > 0) &&
			(point2.crossProductZ(temp2, tempp) * point2.crossProductZ(temp2, temp1) > 0)){

			return false;

		}

		return true;

	}

}
class plane3{

	point3 p1, p2, p3;

	plane3(point3 given1, point3 given2, point3 given3){

		p1 = given1;
		p2 = given2;
		p3 = given3;

	}

	public static boolean doesIntersect(point3 vector, plane3 plane){

		//Step 1: check if vector is between the vertices of the plane! (If the vector goes towards the plane)
		if(
			(point3.crossProductW(plane.p1, plane.p2, vector) * point3.crossProductW(plane.p1, plane.p2, plane.p3) <= 0 )||
			(point3.crossProductW(plane.p2, plane.p3, vector) * point3.crossProductW(plane.p2, plane.p3, plane.p1) <= 0 )||
			(point3.crossProductW(plane.p3, plane.p1, vector) * point3.crossProductW(plane.p3, plane.p1, plane.p2) <= 0 )){

			return false;

		}

		//Step 2: check if the point is outside of the triangle formed by the plane and the origin
		point3 temp1, temp2, temp3, tempp;

		temp1 = new point3(0 - plane.p1.x, 0 - plane.p1.y, 0 - plane.p1.z);
		temp2 = new point3(plane.p2.x - plane.p1.x, plane.p2.y - plane.p1.y, plane.p2.z - plane.p1.z);
		temp3 = new point3(plane.p3.x - plane.p1.x, plane.p3.y - plane.p1.y, plane.p3.z - plane.p1.z);
		tempp = new point3(vector.x - plane.p1.x, vector.y - plane.p1.y,vector.z - plane.p1.z);

		if(
			(point3.crossProductW(temp1, temp2, tempp) * point3.crossProductW(temp1, temp2, temp3) > 0 )&&
			(point3.crossProductW(temp2, temp3, tempp) * point3.crossProductW(temp2, temp3, temp1) > 0 )&&
			(point3.crossProductW(temp3, temp1, tempp) * point3.crossProductW(temp3, temp1, temp2) > 0 )){

			return false;

		}

		return true;

	}


}

public class vectorCollisionTest2{

	public static void main(String[] args){

		/*
		point3 p = new point3(7, 7, 7);
		tetrahedron t = new tetrahedron(new point3(0, 0, 0), new point3(0, 2, 2), new point3(4, 5, 6), new point3(5, 8, 13));

		System.out.println(
			"Is P(" + p + "\n" +
			"within T[\n\t(" + t.p1 + ")\n\t("  + t.p2 + ")\n\t("  + t.p3 + ")\n\t("  + t.p4 + ")\n]?\n" +
			tetrahedron.isInside(p, t)
		);*/

		/*
		point2 v = new point2(1, 4);
		plane2 p = new plane2(new point2(1, 3), new point2(3, 1));

		System.out.println(
			"Does V(" + v + "\n" +
			"cross over P[\n\t(" + p.p1 + ")\n\t(" + p.p2 +")\n]?\n" +
			plane2.doesIntersect(v, p)
		);
		*/

		point3 v = new point3( 0, 6, 7);
		plane3 p = new plane3(new point3(0, 1, 3), new point3(4, 6, 2), new point3(8, 0, 0));

		System.out.println(
			"Does V(" + v + "\n" +
			"cross over P[\n\t(" + p.p1 + ")\n\t(" + p.p2 + ")\n\t(" + p.p3 + ")\n]?\n" +
			plane3.doesIntersect(v, p)
		);


	}

}