How to check if 4 points form a convex quadrilatera

Question

I'm quite new to coding in general. I have found some answers for this question but the answers seem advanced for me.

I'm trying to write my own Finite Element Project. For this I would like to write a method that checks if random 4 nodes given as input form a convex quadrilateral.

My method is supposed to look like this:

private bool IsConvex(Node[4] corners)
{
    bool isConvex;

    //CODE//

    return isConvex;
}

the Node class is defined by three public properties referring to their coordinates (.coordX, .coordY, .coordZ)

Answer 1

In order to know if a quadrilateral is convex or not, you can make a triangle of three points and see if the fourth point is located inside that triangle or not. If you manage finding one triangle, which contains the fourth point, then you don't have a convex quadrilateral.

Ok, and how can you know if a point is located inside a triangle?

Well, you start by determining at which side a point is located compared to a vector.
Come again?
Well, for each vector, you can find out if a point is located at the left side or at the right side: you just rotate the vector back to the Y-axis, you do the same with the point and if the X coordinate of the point is negative your point is located at the left side, otherwise it's at the right side, like in these three cases (left, left and right):

Once you have figured that out, you define a point being inside a triangle if, after having described the triangle as a triangle of vectors, your point is at the same side of all vectors, like in this example (be aware that your triangle consists of the vectors AB, BC and CA: the points must follow up each other):

Good luck

Answer 2

First a little helper class to handle things related to triangles made up of three nodes.

using System.Numerics;

public readonly struct Triangle
{
    public const float DistanceTolerance = 1e-6f;
    public Triangle(Vector3 a, Vector3 b, Vector3 c)
    {
        A = a;
        B = b;
        C = c;
    }

    public Vector3 A { get; }
    public Vector3 B { get; }
    public Vector3 C { get; }

    private Vector3 AreaVector { get => (Vector3.Cross(A, B) + Vector3.Cross(B, C) + Vector3.Cross(C, A)) / 2; }
    public float Area { get => AreaVector.Length(); }
    public Vector3 Normal { get => Vector3.Normalize(AreaVector); }

    public float DistanceTo(Vector3 point) => Vector3.Dot(Normal, point - A);

    public Vector3 Project(Vector3 point)
    {
        // A projected point lies on the plane defined by the three veertices A,B,C
        Vector3 n = Normal;
        float d = Vector3.Dot(n, point - A);
        return point - n * d;
    }

    public void Barycentric(Vector3 P, out (float w_A, float w_B, float w_C) coordinates)
    {
        Vector3 n = Vector3.Cross(A, B) + Vector3.Cross(B, C) + Vector3.Cross(C, A);
        float w_A = Vector3.Dot(n, Vector3.Cross(P, B) + Vector3.Cross(B, C) + Vector3.Cross(C, P));
        float w_B = Vector3.Dot(n, Vector3.Cross(A, P) + Vector3.Cross(P, C) + Vector3.Cross(C, A));
        float w_C = Vector3.Dot(n, Vector3.Cross(A, B) + Vector3.Cross(B, P) + Vector3.Cross(P, A));
        float sum = w_A + w_B + w_C;
        coordinates = (w_A / sum, w_B / sum, w_C / sum);
    }

    public bool Contains(Vector3 P)
    {
        if (Math.Abs(DistanceTo(P)) <= DistanceTolerance)
        {
            Barycentric(P, out var coordinates);
            return coordinates.w_A >= 0 && coordinates.w_A <= 1
                && coordinates.w_B >= 0 && coordinates.w_B <= 1
                && coordinates.w_C >= 0 && coordinates.w_C <= 1;
        }
        return false;
    }
}

If you are not familiar with barycentric coordinates, they are the linear combinations of the vertices that make up an interior (or exterior) point.

For example if a point is defined as P = 0.3*A + 0.5*B + 0.2*C then the barycentric coordinates of P are (0.3,0.5,0.2). The only restriction here is that the sum of the barycentric coordinates must equal to 1.

A point P is interior to the triangle ABC if all the barycentric coordinates of P are between 0 and 1.

This is the rule that I am using to write the Triangle.Contains(point) function. I also check to see if the point is on the same plane as the triangle.

Now to get to the algorithm to check if an n-gon is convex, all I have to do is take 3 vertices at a time, and check that all remaining other vertices are exterior to those three.

    public static bool IsConvex(Vector3[] nodes)
    {            
        for (int i = 0; i < nodes.Length; i++)
        {
            // pick three nodes at a time i,j,k
            var j = (i + 1) % nodes.Length;
            var k = (i + 2) % nodes.Length;
            var A = nodes[i];
            var B = nodes[j];
            var C = nodes[k];

            // deefine triangle ABC from three nodes
            var trig = new Triangle(A, B, C);

            // check nodes after the three and wrap around to grab first nodes also
            for (int r = 3; r < nodes.Length; r++)
            {
                var P = nodes[(r + i) % nodes.Length];

                // if _any_ node is interior to ABC then non-convex
                if (trig.Contains(P))
                {
                    return false;
                }
            }               
        }
        return true;
    }

and some test code to make sure it all works as intended.

    static readonly Random rng = new Random();
    static void Main(string[] args)
    {
        // Generate a random 3D triangle
        var trig = new Triangle(
            new Vector3(10 * (float)rng.NextDouble(), 0, 0),
            new Vector3(0, 10 * (float)rng.NextDouble(), 0),
            new Vector3(0, 0, 10 * (float)rng.NextDouble()));

        // Generate an interior point (in the plane)
        var point1 = 0.3f * trig.A + 0.5f * trig.B + 0.2f * trig.C;
        // Check that it is contained inside the triangle
        Debug.Assert(trig.Contains(point1));

        // Generate an exterior point (on the plane)
        var point2 = -0.3f * trig.A + 0.5f * trig.B + 0.8f * trig.C;
        // Check that it is not contained inside the triangle
        Debug.Assert(!trig.Contains(point2));

        // Generate a point out of plane
        var point3 = point1 + 2.5f * trig.Normal;
        // Check that it is not contained inside the triangle
        Debug.Assert(!trig.Contains(point3));

        // Generate a convex quadrilateral
        var poly1 = new Vector3[] {
            new Vector3(0f,0f,0f),
            new Vector3(5f,0f,0f),
            new Vector3(5f,3f,0f),
            new Vector3(1f,7f,0f),
        };

        // Generate a non-convex quadrilateral
        var poly2 = new Vector3[] {
            new Vector3(0f,0f,0f),
            new Vector3(5f,0f,0f),
            new Vector3(2f,2f,0f),
            new Vector3(1f,7f,0f),
        };

        // Check that it is convex
        Debug.Assert(IsConvex(poly1));
        // Check that it is not convex
        Debug.Assert(!IsConvex(poly2));
    }