Lesson 47 — Hình học tính toán
Ba module tương tác: Cross product / Orientation (click 3 điểm xem rẽ trái/phải), Convex hull (animate Andrew monotone chain), Point in polygon (ray casting đếm giao). Tất cả quy về một phép toán: tích có hướng (cross product).
1. Cross product & Orientation
Click 3 điểm trên lưới: A (đỏ), B (xanh dương), C (tím). Hệ tính
cross(A,B,C) = (B−A)×(C−A) rồi cho biết C nằm bên trái (CCW) / phải (CW) / thẳng hàng.
Thử: kéo 3 điểm — cross > 0 rẽ trái, < 0 rẽ phải, = 0 thẳng hàng: một phép nhân thay mọi phép đo góc.
2. Convex Hull — Andrew's Monotone Chain
Click thêm điểm bất kỳ. Bấm Dựng hull để animate từng bước build lower + upper hull bằng cross product (loại điểm tạo khúc cua sai chiều).
3. Point in Polygon — Ray Casting
Đa giác cố định. Click bất kỳ đâu để đặt điểm truy vấn — hệ bắn tia ngang sang phải, đếm số cạnh cắt: lẻ = trong, chẵn = ngoài.