---
# System prepended metadata

title: BSP for point-in-triangle test

---

# 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
    ```c++
    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
    }    
    ```