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?

Answer 1

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!

Answer 2

i have found a way to find what i want. here it is: (code is C++/Ogre)

    // top or bottom vector of rectangle
Ogre::Vector3 right = Ogre::Vector3(vertices[3] - vertices[2]); 
right.normalise();
    // vector opposite of the top vector
Ogre::Vector3 left = Ogre::Vector3(vertices[0] - vertices[1]); 
left.normalise();


    // you may store above values if rectangle doesnt move much. this would reduce amount of operations


    // vector from top vertex to position we are checking
Ogre::Vector3 p2ToPos = Ogre::Vector3(pos - vertices[2]);
p2ToPos.normalise();

    // vector from bot vertex to position we are checking
Ogre::Vector3 p1ToPos = Ogre::Vector3(pos - vertices[1]);
p1ToPos.normalise();

    // angle between our vectors
Ogre::Real dot1 = p2ToPos.dotProduct(right);
Ogre::Real dot2 = p1ToPos.dotProduct(left);

    // is both dot products (which gives cos) are positive point is between our rectangle
if(dot1 > 0 && dot2 > 0)
    return true;

this calculates what we want with only 2 normalise functions and 2 dot products.