計算幾何

隨着科學技術的飛速發展及計算機在國民經濟各個領域中的普遍運用，計算機輔助設計，即CAD越來越為人們所重視。當前的CAD工作中，計算機遠遠不只是一種高效的計算工具，它已成為人們進行創造性設計活動的得力助手甚至參謀。計算幾何作為CAD的基礎理論之一，主要研究內容是幾何形體的數學描述和計算機表述；它同計算機輔助幾何設計，即CAGD有着十分密切的關係。而CAGD是由微分幾何、代數幾何、數值計算、逼近論、拓撲學以及數控技術等形成的一門新興邊緣學科，其主要研究對象和內容是對自由形曲線、曲面的數學描述、設計、分析及圖形的顯示、處理等。

在第二次世界大戰期間，人們已首次用計算幾何的方法解決實際問題。當時尤其是航空工業的發展激勵了新的設計方法的形成和發展。計算幾何這一術語，最初是由明斯基和帕伯特於1969年作為模式識別的代用詞而提出的，到1972年，福雷斯特給其下了正式定義：“對幾何外形信息的計算機表示、分析和綜合”。這裏的幾何外形信息是指那些用來確定某些幾何外形的離散數據點或特徵多邊形。按照給定的信息，建立一定的數學模型，再通過計算機進行計算，求得其他所需的信息，這就是計算機表示。之後還需對所建立的數學模型特性及誤差等進行分析、綜合，以便逼真地反映出幾何形體。 ^[1] 

計算幾何研究的對象是幾個圖形。早期人們對於圖像的研究一般都是先建立座標系，把圖形轉換成函數，然後用插值和逼近的數學方法，特別是用樣條函數作為工具來分析圖形，取得了可喜的成功。然而，這些方法過多地依賴於座標系的選取，缺乏幾何不變性，特別是用來解決某些大撓度曲線及曲線的奇異點等問題時，有一定的侷限性。

幾何圖形是實際物體的抽象描述，幾何化是指被研究對象本身的性質所決定的一種必然趨勢。

在國外，計算幾何的代數化有一股很強的勢頭。為了在計算機和圖形顯示終端表示和處理各種複雜的曲面和幾何形體，需進行大量的計算，往往需要將問題代數化、線性化、離散化，特別對於最新式的全色連續色調的圖像，必須對顯示屏上的光柵網格點逐點進行計算掃描。

隨着交互式圖形顯示系統在CAGD中的廣泛應用，計算機圖形學作為新興學科得到迅速發展。其主要研究對象是圖形的生成、變換、顯示、剪取、隱藏線和隱藏面的消除、陰影色調及相應的光順處理等。其中剪取問題是計算機圖形學的一個基本問題，剪取的關鍵是速度，尤其是在交互式動態顯示和最新式的光掃描中。 ^[2]