English  |  正體中文  |  简体中文  |  Items with full text/Total items : 28588/40619
Visitors : 4121703      Online Users : 70
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/49628

Title: Polygonal surfaces上最短路徑規劃
Shortest path-planning on polygonal surfaces
Authors: Po-Yang Wu
Contributors: NTOU:Department of Electrical Engineering
Keywords: 多面體表面;最短路徑;計算幾何學;Dijkstra演算法;稜點
Polygonal surface;near-shortest path;computational geometry;Dijkstra’s algorithm;ridge point
Date: 2015
Issue Date: 2018-08-22T07:09:22Z
Abstract: 本論文提出一個能有效率的在三角網格所構成的多面體表面(polygonal surfaces)上尋找最短路徑的演算法。在三維空間中尋找最短路徑是一個NP-hard問題。理論上,若將Kanai及Suzuki [11]演算法中的Steiner點數擴張至無限大,則計算所得的路徑將會是最佳解。實務上,本論文以KS演算法搭配29個Steiner point計算出非常接近最佳解的近似最短路徑值作為比較依據。雖然本論文的演算法比KS演算法得出的最短路徑長度稍長約2.75%,但是KS的計算時間是本論文的63倍以上,得證我們所提出的演算法是一個高效率且計算結果很接近最佳解的最短路徑演算法。在多面體表面上能有效率的找到最短距離對許多3D路徑規畫、GIS地形測量以及CNC車床加工等相關領域都會有很大的助益。
This thesis proposes an O(nlogn) algorithm capable of finding near- shortest path on polygonal surfaces. Shortest-path planning in 3-dimensional space is an NP-hard problem. Theoretically, if the number of Steiner points in Kanai and Suzuki’s algorithm [11] is allowed to approach infinity, the path obtained will be optimal. In practice, the results produced by the KS’s algorithm with 29 Steiner points are very near the optimal solutions. We thus compared the experimental results of our algorithm to the results of the KS’s algorithm using 29 Steiner points. Under such configuration, the average path length obtained by our method is slightly longer than the KS’s by 2.75%, but the computing time of ours is shorter by more than 63 times. The comparisons indicate that the proposed method is highly efficient for path-planning on polygonal surfaces. The method is potentially applicable to many important research fields and industrial applications such as 3D route planning, GIS, CNC tooling, etc.
URI: http://ethesys.lib.ntou.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=G0010153016.id
Appears in Collections:[電機工程學系] 博碩士論文

Files in This Item:

File Description SizeFormat

All items in NTOUR are protected by copyright, with all rights reserved.


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback