Search code examples
3dpointplane

Check if a point is inside a plane segment

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: plane 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?

Solution

  • 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!