Question

How to determine whether a point lies inside a 2D triangle in C++

Answer 1

#include <iostream>

/*
    Determine whether a point lies inside a triangle using barycentric coordinates.

    Correct, robust approach:
    -------------------------
    For triangle ABC and point P:

        v0 = C - A
        v1 = B - A
        v2 = P - A

    We compute:

        dot00 = v0 · v0
        dot01 = v0 · v1
        dot02 = v0 · v2
        dot11 = v1 · v1
        dot12 = v1 · v2

        denom = dot00 * dot11 - dot01 * dot01

        v = (dot11 * dot02 - dot01 * dot12) / denom
        w = (dot00 * dot12 - dot01 * dot02) / denom
        u = 1 - v - w

    The point P is inside or on the boundary of triangle ABC iff:
        u >= 0, v >= 0, w >= 0

    This avoids the sign issues we had before and is a standard,
    numerically stable barycentric formulation.
*/

struct Point {
    double x, y;

    // Subtraction of two vectors
    Point operator-(const Point& other) const {
        return {x - other.x, y - other.y};
    }
};

// Dot product
double dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

// Check if point P is inside triangle ABC using barycentric coordinates
bool pointInTriangle(const Point& A, const Point& B, const Point& C, const Point& P) {
    Point v0 = C - A;
    Point v1 = B - A;
    Point v2 = P - A;

    double dot00 = dot(v0, v0);
    double dot01 = dot(v0, v1);
    double dot02 = dot(v0, v2);
    double dot11 = dot(v1, v1);
    double dot12 = dot(v1, v2);

    double denom = dot00 * dot11 - dot01 * dot01;

    // Degenerate triangle (area ~ 0)
    if (denom == 0.0) {
        return false;
    }

    double invDenom = 1.0 / denom;

    double v = (dot11 * dot02 - dot01 * dot12) * invDenom;
    double w = (dot00 * dot12 - dot01 * dot02) * invDenom;
    double u = 1.0 - v - w;

    // Inside (or on edge) if all barycentric coordinates are >= 0
    return (u >= 0.0 && v >= 0.0 && w >= 0.0);
}

int main() {
    // Triangle ABC
    Point A{0.0, 0.0};
    Point B{5.0, 0.0};
    Point C{2.5, 5.0};

    // Point P (as in your note)
    Point P{2.5, 2.0};

    bool inside = pointInTriangle(A, B, C, P);

    std::cout << "Point (" << P.x << ", " << P.y << ") is "
              << (inside ? "inside" : "outside")
              << " the triangle.\n";
}



/*
run:

Point (2.5, 2) is inside the triangle.

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>

/*
    Simple 2D point structure
*/
struct fPoint {
    float x, y;
};

/*
    edgeOrientation(p1, p2, p3)
    ---------------------------
    Computes the 2D cross product of vectors:
        (p1 - p3) × (p2 - p3)

    The sign of this value tells us whether p1 lies to the left or right
    of the directed edge p3 → p2.

    This is the core of the "same-side" triangle test.
*/
float edgeOrientation(fPoint p1, fPoint p2, fPoint p3) {
    return (p1.x - p3.x) * (p2.y - p3.y)
         - (p2.x - p3.x) * (p1.y - p3.y);
}

/*
    PointInTriangle(pt, v1, v2, v3)
    --------------------------------
    Uses the same-side method:

    A point is inside the triangle if it lies on the same side of all
    three edges. If the signs of the three cross products are all
    non-negative or all non-positive, the point is inside or on the edge.

    If the signs mix (some positive, some negative), the point is outside.
*/
bool PointInTriangle(fPoint pt, fPoint v1, fPoint v2, fPoint v3) {
    float d1 = edgeOrientation(pt, v1, v2);
    float d2 = edgeOrientation(pt, v2, v3);
    float d3 = edgeOrientation(pt, v3, v1);

    bool has_negative = (d1 < 0) || (d2 < 0) || (d3 < 0);
    bool has_positive = (d1 > 0) || (d2 > 0) || (d3 > 0);

    // Inside if NOT both negative and positive signs
    return !(has_negative && has_positive);
}

int main() {
    // Triangle vertices
    fPoint A{0.0f, 0.0f};
    fPoint B{5.0f, 0.0f};
    fPoint C{2.5f, 5.0f};

    // Test point
    fPoint P{2.5f, 2.0f};

    bool inside = PointInTriangle(P, A, B, C);

    std::cout << "Point (" << P.x << ", " << P.y << ") is "
              << (inside ? "inside" : "outside")
              << " the triangle.\n";
}


/*
run:

Point (2.5, 2) is inside the triangle.

*/

 

70+ SQL courses for beginners and professionals