在哪裏學習計算幾何？

Question

我想解決在線編程競賽中的幾何問題。但是每當我讀到它們時，我都覺得太困難了。請提供一些我可以學習計算幾何的書籍和資源。

Answer 1

的經典之作：Computational Geometry in C。

還有：http://www.cs.uu.nl/geobook/。

Answer 2

這裏有兩個優異的書籍，我使用它們作爲教科書在大學：

1. Ĵd弗利，A麪包車大壩等人Introduction to Computer Graphics。 Addison-Wesley，1994，ISBN 0-201-60921-5。

2. D Hearn and M P Baker。 Computer Graphics with Open GL (3rd edition)。 Prentice-Hall，2004，ISBN 0-13-120238-3。

Introduction to Computer Graphics http://ecx.images-amazon.com/images/I/513QBRR0VAL._SL500_AA240_.jpg Computer Graphics with Open GL http://ecx.images-amazon.com/images/I/519TMP2ENVL._SL500_AA240_.jpg

Answer 3

爲了快速解決基本的幾何問題，使得它比賽的時間限制內運行，你需要確定你有寫作的算法強大的把握。

本頁面有一些關於如何改善的好建議。它被設置爲兩個學期的閱讀課程。

http://mrmbdctg.freehostia.com/contest_Tipsforbeginner.html

Answer 4

您可以嘗試TopCoder上的問題存檔。
但你應該先註冊。

在過濾器中進行選擇：
類別：幾何
司II級：Level One或Level Two。

幾乎所有的問題都有解決方案的描述。

它們相當簡單，你可以從比賽歸檔中選擇隨機幾何問題。

在page你還可以找到很多教程，包括幾何教程。

Answer 5

你必須知道凸包和點多邊形。通常在TopCoder上，人們會爲幾何應用程序創建一個可重用的庫，因爲多次使用相同的代碼。

檢查lbackstrom's tutorial開始。 Computional Geometry by de Berg, Cheong, van Kreveld, Overmars [編輯：Bart已經提到]可能比你需要的更多。

Answer 6

當然還有Computational Geometry - An Introduction，Preparata和Shamos。我擁有它，並推薦它來介紹這些原則。雖然不是真正的代碼字典。

Answer 7

我推薦兩本書（其中包括）：

• The Algorithm Design Manual By Steven S. Skiena - 從總體上討論的算法，但有一個關於計算幾何
• Computational Geometry: Algorithms and Applications

Answer 8

很多有用的信息，如果你想清除您的基礎知識，這是一個很好的起點 - https://www.hackerearth.com/notes/computational-geometry-i-1/。文章中也有一些實踐問題。

你也應該通過這篇文章閱讀 - http://www.toptal.com/python/computational-geometry-in-python-from-theory-to-implementation覆蓋一些先進的概念。