臺灣博碩士論文加值系統

本論文主要是以O(N)的最短路徑演算法為核心，進而推演出在3D空間上的最短路徑演算法，並利用此3D最短路徑演算法，使得二維網格平面多組搜尋演算法推展至3D空間模型，且利用3D最短路徑演算法推導出3D空間模型上動態即時追截(dynamic chasing)系統。而後，藉由3D空間中轉換二次曲面(quadric surfaces)的觀念，將3D空間上的單組、多組最短路徑以及動態欄截演算法應用至二次曲面上。其時間與空間複雜度仍維持在O(N)，此處N為3D空間中所有可通行之自由空間的方塊數。並可實際應用在海上船舶的搜尋與追截、汽車導航系統、航行器的空中搜尋與追截、地理資訊方面應用及巡弋飛彈攔截系統等。而本論文所執行範例是在Microsoft Windows 2000、CPU(中央處理器) Intel P3 700、記憶體256MB環境下執行。

Recently, Jan, Hsu and Wu proposed planar and spatial shortest path searching algorithms with O(N) of time and memory space complexities based on the nuclear fission chain reactions scheme, where N is the number of non-obstacle cells. Meanwhile, it is also extended to dynamic chasing algorithm in planar space. Using space-marking method with extra data structure, we applied these algorithms to 3-dimentioanl space and quadric surfaces without changing the time and space complexities in this thesis. These new algorithms have been coded in C++ language on personal computer with an Intel Pentium III 700 processor running MS Windows 98/2000, and some illustrations are presented as well.

圖目錄 Ⅴ
表目錄 Ⅶ
第一章 緒論 1
1.1 研究動機與目的 1
1.2 論文編排方式 2
第二章 文獻探討 4
2.1 3D網格資料結構 4
2.2 3D網格圖最短路徑演算法 12
2.3 3D網格圖最短路徑演算法應用實例 14
第三章 3D網格圖之多組最短路徑與動態即時追截 17
3.1 3D多組最短路徑 17
3.2 3D空間之航行器領域 18
3.3 3D多組最短路徑及避碰演算法 20
3.4 3D多組最短路徑及避碰演算法時間複雜度分析 20
3.5 3D多組最短路徑及避碰演算法應用實例 21
3.6 3D動態即時追截系統 25
3.7 3D動態即時追截演算法 25
3.8 3D動態即時追截演算法時間複雜度分析 28
3.9 3D動態即時追截演算法應用實例 28
第四章 二次曲面之單組、多組最短路徑與動態即時追截 34
4.1 3D網格圖之二次曲面 34
4.2 二次曲面之單組最短路徑 36
4.3 二次曲面之單組最短路徑演算法 36
4.4 二次曲面之單組最短路徑演算法時間複雜度分析 37
4.5 二次曲面之單組最短路徑演算法應用實例 38
4.6 二次曲面之多組最短路徑 40
4.7 二次曲面之多組最短路徑演算法 40
4.8 二次曲面之多組最短路徑演算法時間複雜度分析 41
4.9 二次曲面之多組最短路徑演算法應用實例 41
4.10 二次曲面之動態即時追截 44
4.11 二次曲面之動態即時追截演算法 44
4.12 二次曲面之動態即時追截演算法時間複雜度分析 45
4.13二次曲面之動態即時追截演算法應用實例 45
第五章 結論與未來發展 49
參考文獻 51

[1] J. H. Beattie, “The Future of Electronic Chart in Merchant Ships,” The Journal of Navigation, Vol. 48, No. 3, 1995, pp. 335-348.
[2] T. M. Burgess and R. Webster, “Optimal Interpolation and Isarithmic Mapping of Soil Properties: I. The Semi-Variogram and Punctual Kriging,” Journal of Soil Science, Vol. 31, 1980, pp. 315-331.
[3] Charlie Calvert, “Charlie Calvert’s Borland C++ Builder 4 Unleashed,” SAMS, 1999.
[4] F. P. Coenen, G. P. Smeaton and A G Bole, “Knowledge-based Collision Avoidance,” The Journal of Navigation, Vol. 42, No. 1, 1989, pp. 107-116.
[5] T. G. Coldwell, “Marine Traffic Behaviour in Restricted Waters,” The Journal of Navigation, Vol. 36, No. 3, 1983, pp. 430-444.
[6] B. A. Colley, R. G. Curtis and C. T. Stockel, “A Marine Traffic Flow and Collision Avoidance Computer Simulation,” The Journal of Navigation, Vol. 37, No. 2, 1984, pp. 232-250.
[7] “Convention on the High Seas,” 1958, IMCO.
[8] Kayshav Dattatri, C++ Effective Object-Oriented Software Construction, Prenticr Hall PTR, 1997.
[9] P. V. Davis, M. J. Dove and C. T. Stockel, “A Computer Simulation of Multi-Ship Encounters,” The Journal of Navigation, Vol. 35, No. 2, 1982, pp. 347-352.
[10] Elisabeth M. Goodwin, “A Statistical Study of Ship Domains,” The Journal of Navigation, Vol. 28, No. 3, 1975, pp. 328-344.
[11] Grau, Juanita Kaye Shuker, “Development, Modification, and Comparison of Execution Times of Algorithms whitch Create or Modify Shortest Path Matrices for Road Network,” University of Missouri—Rolla Ph. D, 1979.
[12] Ivor Horton’s, Beginning Visual C++ 6, Wrox Press, 1998.
[13] Ellis Horowitz, Sartaj Sahni, Dinesh Mehta, Fundamentals of Data Structures In C++, W H FERRMAN, 1995.
[14] Gene Eu Jan, Ming-Bo Lin and Yung-Yuan Chen, “Computerized Shortest Path Searching for Vessels,” Journal of Marine Science and Technology, Vol. 5, No. 1, June 1997, pp. 95-99.
[15] Gene Eu Jan and Ki-Ying Chang, “An O(N) Shortest Path-Searching Algorithm on Raster,” Technical Report CS01001, Department of Computer Science, National Taiwan Ocean University, Taiwan, Jan. 2001.
[16] K Jiang, L. D. Seneviratne and S. W. E. Earles, “Finding the 3D Shortest Path with Visibility Graph and Minimum Potential Energy,” IEE/RSJ International Conference on Intelligent Robots and System Proceedings, Vol. 1, 1993, pp. 679-684.
[17] K Jiang, L. D. Seneviratne and S. W. E. Earles, “3D shortest path planning in the presence of polyhedral obstacles,” IEEE International Conference on System Man and Cybernetics, Vol. 5, 1993, pp. 206-211.
[18] S Kaveti, Eam Khwang Teoh, Han Wang, “On 3-D image segmentation based on planar and quadric approximations,” IEEE International Conference on Humans, Information and Technology, Vol. 1, 1994, pp. 349-353.
[19] Peter J. Kovach, Inside Direct 3D, Microsoft Press, 2000.
[20] C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Trans. on Electron. Computer, vol. EC-10, pp. 346- 365, Sept. 1961.
[21] Stanley B Lippman, Jose Lajoie, C++ Primer 3/e, Prentice Hall, 1998.
[22] R E Marston, M H Kuo, “Interpretation of 3-view engineering drawings as central quadric surface mechanical pts applications in region-based recognition,” Fourteenth International Conference on Pattern Recognition, Vol. 1, 1998, pp. 668-67arts,“ Third International Conference on Document Analysis and Recognition, Vol. 1, 1995, pp. 343-346.
[23] Myles Ross and Ron Dawson, “Drift Errors in Search and Rescue,” The Journal of Navigation Vol. 47, No. 3, 1994, pp. 369-382.
[24] G Y Wang, Z Houkes, P P L Regtient, M J Korsten, G R Ji, A statistical model to describe invariants extracted from a 3-D quadric surface patch and i2
[25] Fujii Yahei and Tanaka Kenichi, “Traffic Capacity,” The Journal of Navigation, Vol. 24, No. 3, 1971, pp. 543-552.
[26] 施保旭，“地理資訊系統”，儒林圖書有限公司，中華民國84年出版。
[27] “國際海事組織搜救手冊1993年合訂版”，交通部運輸研究所，中華民國八十四年七月，pp. 81-84，pp. 85-91。
[28] 許俊彥，“電子海圖上最短路徑搜尋及其應用”，國立台灣海洋大學電機工程學系碩士論文，民國88年六月。
[29] 紀嘉毅，“電腦輔助海上搜索與救助系統之實證研究”，國立台灣海洋大學航運技術研究所碩士論文，中華民國八十六年六月，pp. 75。
[30] 劉士元，“海上事故搜索救助系統雛形之研究”，國立台灣海洋大學航運技術研究所碩士論文，中華民國八十六年六月，pp. 58-63。
[31] 詹景裕、楊立豪、張啟隱，“電腦化搜救系統之最佳化”，中華民國第六屆運輸安全研討會。新竹交通大學，民國88年11月，pp. 397-pp. 406。
[32] 吳建興，“3D網格圖最短路徑規劃”，國立台灣海洋大學電機工程學系碩士論文，民國89年六月。
[33] “1972年國際海上避碰規則(1987年修正)”，中華民國船長公會譯印。
[34] 陳元平，“航海員避讓行為之研究”，國立台灣海洋大學航運技術研究所碩士論文，中華民國八十六年十二月，pp. 20-23，pp. 25。
[35] 楊立豪，“二維網格圖上動態的搜尋與攔截之最佳化”，國立台灣海洋大學光電科學研究所碩士論文，民國89年六月。