← 回入口

計算幾何 (Computational Geometry)

幾何問題的高效演算法

概述

計算幾何研究幾何問題的高效演算法，廣泛應用於電腦圖形學、機器人學、地理資訊系統、電腦視覺和遊戲開發。基礎問題包括凸包、最近點對、線段相交、點定位。

基礎工具

class Point: def __init__(self, x, y): self.x = x self.y = y def cross(o, a, b): """向量 OA × 向量 OB 的叉積""" return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)

叉積可用於判斷三點的方向（順時針/逆時針）、線段相交檢測。

凸包 (Convex Hull)

凸包是包含所有點的最小凸多邊形。Andrew 演算法（單調鏈）時間 O(n log n)：先按 x 座標排序，分別求上下凸包。Graham Scan 也是 O(n log n) 的經典演算法。

最近點對

在平面點集中找出距離最近的點對。使用分治法可達到 O(n log n)：按 x 座標分割，遞迴求解左右兩側，再合併考慮分割線附近的點。

本課程範例

相關連結