Check if a point is inside a plane segment

Question

i would like to know if a point in a plane segment, and its coordinate in [0,1][0,1] relative to segment. e.g 0,0 left bottom corner, 1,1 right top corner, 0.5,0.5 center

these are the thing i already know:

-point is in on the same plane as plane segment. -coordinates of 4 points of the plane segment. but they are not clock-wise order or any order i would know. -plane's normal and its distance to origin. such as; ax + by + cz +d . x,y,z,d are known.

here is a sketch i did: A,B,C points are on same plane as plane segment. P1, P2, P3, P4 coordinates is known, but is not ordered in any meaningful way.

thank you.

edit:

one idea i have is

sort points
create vector between each points
create vectors from 2 points
dot product them
if degree is between 0 and 90, it's inside

would this work? i need good real-time performance, isn't dot product is slow on CPU? how would i find relative coordinate of point?

Loránd Biró Loránd Biró · Accepted Answer · 2012-03-09T18:11:29

In my opinion the best way to check this is transforming the whole plane and the points to the origin of coordinate system: Translate every point so the left bottom point will be in the center of coordinate system, and rotate everything so the normal vector will be pointing parallel with one of the axes. This means a matrix multiplication for every point, but after this you can easily check which points are in the rectangle. This is an XNA C# implementation, but the logic is the same everywhere: (I tried to use your sketch for inputs)

// Inputs - Right handed coordinate system
Vector3 p1 = new Vector3(-1.0f, 1.0f, 1.0f);  // left top
Vector3 p2 = new Vector3(1.0f, -1.0f, 0.0f);  // right bottom
Vector3 p3 = new Vector3(1.0f, 1.0f, 1.0f);   // right top, redundant if this is a rectangle
Vector3 p4 = new Vector3(-1.0f, -1.0f, 0.0f); // left bottom

Vector3 a = new Vector3(-0.5f, 0.0f, 0.5f);

// Calculating transformation matrix
Vector3 right = Vector3.Normalize(p2 - p4);
Vector3 forward = Vector3.Normalize(p1 - p4);
Vector3 up = Vector3.Cross(right, forward);

Matrix transform = new Matrix();
transform.M11 = right.X;
transform.M12 = right.Y;
transform.M13 = right.Z;
transform.M14 = 0.0f;
transform.M21 = forward.X;
transform.M22 = forward.Y;
transform.M23 = forward.Z;
transform.M24 = 0.0f;
transform.M31 = up.X;
transform.M32 = up.Y;
transform.M33 = up.Z;
transform.M34 = 0.0f;
transform.M41 = p4.X;
transform.M42 = p4.Y;
transform.M43 = p4.Z;
transform.M44 = 1.0f;

transform = Matrix.Invert(transform);

// Transforming
Vector3 tp1 = Vector3.Transform(p1, transform);
Vector3 tp2 = Vector3.Transform(p2, transform);
Vector3 tp3 = Vector3.Transform(p3, transform);
Vector3 tp4 = Vector3.Transform(p4, transform);
Vector3 ta = Vector3.Transform(a, transform);

ta.X /= tp2.X; // divide with rectangle width
ta.Y /= tp1.Y; // divide with rectangle height

// Now everything is on the XY plane
// P1: {X:0    Y:2.236068 Z:0}
// P2: {X:2    Y:0        Z:0}
// P3: {X:2    Y:2.236068 Z:0}
// P4: {X:0    Y:0        Z:0}
// A:  {X:0.25 Y:0.5      Z:0}

This works on any four points.

It's not the fastest solution, but I'm sure it's the cleanest and simplest if you know matrix transformations. If you find any faster and yet simple solution I'm interested too, but probably there will be no performance issues. On my Intel 2.4ghz processor this computation happens more than 1 million times under 1 second without any problem. Hope this helps, good luck!

Check if a point is inside a plane segment

2 Answers