# Binary Space Partitioning (BSP) for Point-in-triangle test
## What's BSP
- Binary Space Partitioning (BSP) is a **space subdivision technique** used in computer graphics, collision detection, and geometric computations. It recursively divides a space into two parts (hence "binary") using hyperplanes (like lines in 2D or planes in 3D).
## How BSP works for point-in-triangle test
- Given a triangle with vertices A, B, C and a point P, we can use BSP-like logic to determine if P is inside the triangle
- **Method: Cross product**
- Compute vectors from each edge to the point:
- AB -> AP
- BC -> BP
- CA -> CP
- Calculate cross product
- If all cross product have the same sign, the point is inside
- If any cross product is zero, the point is on the edge
- If signs differ, the point is outside
- **Math formulation**
- For edge AB and point P, the cross product is
$$(Bx - Ax)(Py - Ay) - (By - Ay)(Px - Ax)$$
- Positive: P is on one side
- Negative: P is on the other side
- Zero: P is on the line
- Pseudo implementation

    bool bsp(Point A, Point B, Point C, Point P) {
        float d1 = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);
        float d2 = (C.x - B.x) * (P.y - B.y) - (C.y - B.y) * (P.x - B.x);
        float d3 = (A.x - C.x) * (P.y - C.y) - (A.y - C.y) * (P.x - C.x);

        bool has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
        bool has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
        bool has_zero = (d1 == 0) || (d2 == 0) || (d3 == 0);

        if (has_zero)
            return (false);
        return !(has_neg && has_pos); // Inside if all same sign
    }