開啟主選單

求真百科

計算幾何是一門興起於二十世紀七十年代末的計算機科學的一個分支,主要研究解決幾何問題的算法。計算機的出現使得一些問題大幅簡化,然而一些人類直觀自從1946年世界上第一台電子計算機問世以來,計算機應用的一個重要里程碑是1962年美國麻省理工學院發明了世界上第一台圖形顯示器。自此之後,計算機可以通過圖形顯示器直接輸入、輸出圖形,並且可以在顯示屏上通過光標的移動而直接修改圖形。而在這之前,工程師是通過一厚疊紙上密密麻麻的數字來間接表達工程圖形的。

1962年被認為是美國和歐洲CAD開始發展的一年。首先的應用領域是汽車、飛機和造船工業。這3個行業,由於其產品的外形曲面特別複雜,要求特別苛刻,而成為CAD首先應用的領域。

與此同時,也就發展出了一門新興學科——計算幾何,它在美國常常被稱為CAGD(Computer Aided Geometric Design,計算機輔助幾何設計),專門研究「幾何圖形信息(曲面和三維實體)的計算機表示、分析、修改和綜合」。1972年在美國舉行CAGD第一次國際會議,標誌計算幾何學科的形成[1]

目錄

概念

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

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

工作原理

幾何化

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

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

代數化

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

圖形化

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

視頻

計算幾何 相關視頻

《計算幾何 》
0311高三立體幾何之體積計算

參考文獻