(3.236.214.19) 您好!臺灣時間:2021/05/10 06:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳仲平
研究生(外文):Chung-Ping Chen
論文名稱:平面上點位置的偵測
論文名稱(外文):Planar Point Location
指導教授:劉虎城
指導教授(外文):Hoo-Chen Liu
學位類別:碩士
校院名稱:淡江大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1994
畢業學年度:82
語文別:中文
論文頁數:58
中文關鍵詞:平面點位置的偵測平面上任兩條直線不交錯的圖形
外文關鍵詞:PlanarPoint LocationPlanar Straight Line Graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:192
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
平面上,任意n個點所構成的多邊形,將一個平面分割成若干個區域,今
天,任意給一測試點p,我們如何來判斷,這個點p是落在平面的哪一個
區域,這就是本論文所要探討的主題:平面上點位置的偵測。在本論文中
,我們利用一種塗色的技巧,發展出一執行時間複雜度為 O(logn) 的搜
尋演算法,且其先前處理所需的資料結構,也簡化不少。這個快速且準確
的演算法,經實驗證明,的確比傳統的演算法,增加不少的執行效率。傳
統上,我們在探討幾何圖學的演算法時,必須衡量以下三件事,第一:資
料結構的複雜度;第二:所佔記憶體空間大小;第三:演算法的執行效率
;而本論文:平面上點位置的偵測,將隨著測試點的不同,所座落的區域
也有所不同。在考量每測試一個點,就必須執行其搜尋演算法,因此,加
強演算法的執行效率,更是當務之急。論文中所提的快速搜尋演算法,即
針對此而來。相信,在需要即時系統的軍事偵測上,更能增加其實質效益


The point-location problem is statedas follows: Given a
subdivision of the plane by a straight line planar graph with n
vertices and an arbitrary query point Q, determine which region
of the subdivision contains Q. In this paper, we present an
algorithm whose search time is O(logn) for identifying which
region of subdivision contains a given test point. Using the
technology of filling color, our search algorithm is
practically the most efficient among the tested algorithm.
Analyzing geometric algorithm, we must trade-off among search
time, preprocessing time, and storage. However, the point
location problem, search time is more important than the
others, because it is belongs to the type of repetitive-mode
queries, that is whenever given a test point Q, we must run the
search algorithm to find which region of the subdivision
contains Q. So, how to speed th efficience of the search
algorithm is the most important part in point-location problem.
In this paper the search algorithm can just yield the efficient
solution in above geometric problems, especially in real time
system, such as the detection of militrary affairs.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔