Determinant Predicates

When re-reading Real-Time Collision Detection by Christer Ericson i came across a section called Determinant Predicates in Chapter 3 A Math and Geometry Primer. I thought it was interesting that from just filling a matrix with data such a points in space and finding the determinate of that matrix you could do geometrical tests. Although the tests are not the most efficient ways for solving the problems outlined here i just wanted to make an implementation in C++ to test it myself.

The source is hosted on GitHub, you can find that here: Link

In the source i have provided 3 solution’s based on the matrices in the chapter.

1: orient2D which tests is a point (C) is on the left or right of a line defined by AB. The determinate

orient2D

Matrix3x3(float aX, float aY,
		float bX, float bY,
		float cX, float cY)
{
	data[0] = aX;	data[1] = aY;	data[2] = 1;
	data[3] = bX;	data[4] = bY;	data[5] = 1;
	data[6] = cX;	data[7] = cY;	data[8] = 1;
}

float Determinate()
{
	return data[0] * ((data[4] * data[8]) - (data[5] * data[7])) -
		data[3] * ((data[1] * data[8]) - (data[2] * data[7])) +
		data[6] * ((data[1] * data[5]) - (data[2] * data[4]));
}
//					 A        B       C
Matrix3x3 orient2D(10,10,	 5,5,	4,15);
float orient2D_Answer = orient2D.Determinate();

if(orient2D_Answer > 0)
	cout << "C lies to the left of the directed line AB" << endl;
else if(orient2D_Answer < 0)
	cout << "C lies to the right of the directed line AB" << endl;

 

2: orient3D which tests is a point (D) above or below the plane define by ABC

orient3D

Matrix4x4(float aX, float aY, float aZ,
	float bX, float bY, float bZ,
	float cX, float cY, float cZ,
	float dX, float dY, float dZ)
{
	data[0] = aX;	data[1] = aY;	data[2] = aZ;	data[3] = 1;
	data[4] = bX;	data[5] = bY;	data[6] = bZ;	data[7] = 1;
	data[8] = cX;	data[9] = cY;	data[10] = cZ;	data[11] = 1;
	data[12] = dX;	data[13] = dY;	data[14] = dZ;	data[15] = 1;
}

//					 A		  B		  C			D
Matrix4x4 orient3D(1,4,2,	0,1,4,	-1,0,1,	  2,0,4);
float orient3D_Answer = orient3D.Determinate();

if (orient3D_Answer > 0)
	cout << "D lies below the supporting plane of triangle ABC" << endl;
else if (orient3D_Answer < 0)
	cout << "D lies above the supporting plane of triangle ABC" << endl;

3: inCircle2D which tests if a point (D) is inside a circle whose points ABC lie on the circumference.

inCircle

float InCircle2D(float aX, float aY,
	float bX, float bY,
	float cX, float cY,
	float dX, float dY)
{
	float AxAy_Squared = (aX * aX) + (aY * aY);
	float BxBy_Squared = (bX * bX) + (bY * bY);
	float CxCy_Squared = (cX * cX) + (cY * cY);
	float DxDy_Squared = (dX * dX) + (dY * dY);

	Matrix4x4 matrix(aX, aY, AxAy_Squared,
		bX, bY, BxBy_Squared,
		cX, cY, CxCy_Squared,
		dX, dY, DxDy_Squared);

	float answer = matrix.Determinate();

	return answer;
}

//									 A		 B		 C		 D
float inCircle_Answer = InCircle2D(5,5,		4,5,	4,2,	4.5,3.5);

if (inCircle_Answer > 0)
	cout << "D lies inside the circle of the three points A, B, and C" << endl;
else if (inCircle_Answer < 0)
        cout << "D lies outside the circle of the there points A, B and C" << endl;

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s