1  #include "Point.hpp"
 2  
 3  // Static helper function for cross product
 4  static Fixed crossProduct(Fixed qx, Fixed qy, Fixed rx, Fixed ry, Fixed sx,
 5                            Fixed sy) {
 6    // (r - q) x (s - q) = (rx - qx)*(sy - qy) - (ry - qy)*(sx - qx)
 7    return (rx - qx) * (sy - qy) - (ry - qy) * (sx - qx);
 8  }
 9  
10  bool bsp(Point const a, Point const b, Point const c, Point const point) {
11    // Use Fixed arithmetic and cross products to determine if the point is
12    // strictly inside the triangle (not on edges). For points A,B,C and P,
13    // compute signed areas via cross products:
14    // sign1 = (P - A) x (B - A)
15    // sign2 = (P - B) x (C - B)
16    // sign3 = (P - C) x (A - C)
17    // If all signs are > 0 or all < 0 then P is strictly inside. If any
18    // sign == 0 the point is on an edge -> return false (strict inside only).
19  
20    Fixed ax = a.getX();
21    Fixed ay = a.getY();
22    Fixed bx = b.getX();
23    Fixed by = b.getY();
24    Fixed cx = c.getX();
25    Fixed cy = c.getY();
26    Fixed px = point.getX();
27    Fixed py = point.getY();
28  
29    // Check triangle degeneracy: area = (B-A) x (C-A)
30    Fixed area = crossProduct(ax, ay, bx, by, cx, cy);
31    if (area == Fixed(0))
32      return false; // Degenerate triangle
33  
34    Fixed s1 = crossProduct(ax, ay, bx, by, px, py); // (B-A) x (P-A)
35    Fixed s2 = crossProduct(bx, by, cx, cy, px, py); // (C-B) x (P-B)
36    Fixed s3 = crossProduct(cx, cy, ax, ay, px, py); // (A-C) x (P-C)
37  
38    // If any are zero -> on edge -> not strictly inside
39    if (s1 == Fixed(0) || s2 == Fixed(0) || s3 == Fixed(0))
40      return false;
41  
42    bool has_neg = (s1 < Fixed(0)) || (s2 < Fixed(0)) || (s3 < Fixed(0));
43    bool has_pos = (s1 > Fixed(0)) || (s2 > Fixed(0)) || (s3 > Fixed(0));
44  
45    return !(has_neg && has_pos);
46  }