1

I'm working on a project in C# where I have three vectors in R3, and I need to find out if a third vector is contained within the region formed by those vectors. The three basis vectors have a maximum angle of 90 degrees between any two of them, and they are all normalized on the unit sphere. They can be negative.

So far, I've tried matrix-vector multiplication to find the transformed coordinates of the vector. From there, I check whether all three components are positive.

This method works in most cases, but it has some issues working with specific sets of vectors. The issue seems to come from the order of the basis vectors. The basis vectors are processed in no specific order. I need a way to sort these three basis vectors in (x, y, z) order to ensure that the transformation correctly maps my target vector into the positive region of space when it is "inside" these vectors, and into a negative region of space when it is "outside".

All help is greatly appreciated.

Related discussion in 2D: How to determine if a vector is between two other vectors?

Edit: These are the solutions I ended up using. The first is very close to Edward's solution, and the second is slightly changed for consistency in my project.

public bool Vec3Between(Vector3 s, Vector3 p, Vector3 q, Vector3 r)
{
    Vector3 cross = Vector3.Cross(q, r);
    float ds = cross.x * s.x + cross.y * s.y + cross.z * s.z;
    float dp = cross.x * p.x + cross.y * p.y + cross.z * p.z;
    bool same_qr = (ds * dp >= 0);

    cross = Vector3.Cross(r, p);
    ds = cross.x * s.x + cross.y * s.y + cross.z * s.z;
    float dq = cross.x * q.x + cross.y * q.y + cross.z * q.z;
    bool same_rp = (ds * dq >= 0);

    cross = Vector3.Cross(p, q);
    ds = cross.x * s.x + cross.y * s.y + cross.z * s.z;
    float dr = cross.x * r.x + cross.y * r.y + cross.z * r.z;
    bool same_pq = (ds * dr >= 0);

    return same_qr && same_rp && same_pq;
}

public bool Vec3Between(Vector3 vTarget, Vector3[] vRef)
{
    bool same_side = true;
    for (int i = 0; i < 3; i++)
    {
        int i1 = (i < 2) ? (i + 1) : 0;
        int i2 = (i > 0) ? (i - 1) : 2;
        Vector3 cross = Vector3.Cross(vRef[i1], vRef[i2]);
        float plane_vTarget = cross.x * vTarget.x + cross.y * vTarget.y + cross.z * vTarget.z;
        float plane_vRef = cross.x * vRef[i].x + cross.y * vRef[i].y + cross.z * vRef[i].z;
        same_side = same_side && (plane_vTarget * plane_vRef >= 0);
    }
    return same_side;
}
willowed_jade
  • 13
  • 4

1 Answers1

2

It would be nice if you posted some examples, and maybe some code.

In the absence of that information, let me suggest another approach. Let the three vectors defining the region of space be p=(p1,p2,p3), q=(q1,q2,q3), r=(r1,r2,r3), and the fourth point s=(s1,s2,s3). We need to perform 3 tests:

1) Is s on the same side as p of the plane formed by q and r?

2) Is s on the same side as q of the plane formed by r and p?

3) Is s on the same side as r of the plane formed by p and q?

A yes to all three questions is equivalent to the geometric property you are looking for. I'll show you how to answer 1). Then 2) and 3) are analogous.

We find the plane through q, r and the origin by taking the cross product q x r = (q2*r3-q3*r2, q3*r1-q1*r3, q1*r2-q2*r1) = (a,b,c). Then the equation of the plane is a*x + b*y + c*z = 0.

We put the coordinates of s into the lhs of the above formula and get the expression a*s1 + b*s2 + c*s3, which has some value ds, say. We put the coordinates of p into the above lhs of the above formula and get the expression a*p1 + b*p2 + c*p3, which has some value dp, say.

If ds and dp have the same sign, then s and p are on the same side of the plane. If ds and dp have different signs, then s and p are on opposite sides of the plane.

Here's a boolean expression for the overall test:

( 
 ((q2*r3-q3*r2)*s1 + (q3*r1-q1*r3)*s2 + (q1*r2-q2*r1)*s3)
*((q2*r3-q3*r2)*p1 + (q3*r1-q1*r3)*p2 + (q1*r2-q2*r1)*p3)
> 0
)
&&
( 
 ((r2*p3-r3*p2)*s1 + (r3*r1-p1*r3)*s2 + (r1*p2-r2*p1)*s3)
*((r2*p3-r3*p2)*q1 + (r3*p1-r1*p3)*q2 + (r1*p2-r2*p1)*q3)
> 0
)
&&
( 
 ((p2*q3-p3*q2)*s1 + (p3*q1-p1*q3)*s2 + (p1*q2-p2*q1)*s3)
*((p2*q3-p3*q2)*r1 + (p3*q1-p1*q3)*r2 + (p1*q2-p2*q1)*r3)
> 0
)
Edward Doolittle
  • 4,002
  • 2
  • 14
  • 27