移動視点からの多角形可視部分計算

• Item type: SIG Technical Reports(1)
• 公開日: 1995-03-17
• タイトル: 移動視点からの多角形可視部分計算
• タイトル / 言語: en
• タイトル: COMPUTING THE PORTION OF POLYGONS VISIBLE FROM A MOVING VIEWPOINT
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 龍谷大学理工学部数理情報学科
• 著者所属: 龍谷大学理工学部数理情報学科
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Informatics Ryukoku University
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Informatics Ryukoku University
• 著者名: 小澤, 孝夫; 内田, 直樹
• 著者名(英): Takao, Ozawa; Naoki, Uchida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本文では並列的に配置された凸多角形物体の列に沿って移動する視点を考える。まず、視点からの多角形可視部分を計算するための簡単化された基本的なモデルとそれに関する可視性問題を設定し、次いで、それらの問題を解くアルゴリズムと計算結果を示す。凸多角形は頂点と頂点をむすぶ辺から構成されるので、その可視部分を求めるのは、頂点の可視性を考え、辺の可視性は頂点の可視性に基づいて計算すればよい。従って、可視性計算のための基本的モデルとして、xy平面においてy軸に平行に配置された半直線物体の列およびそれらの半直線物体と交差しない線上を移動する視点から構成されるというモデルを考える。さらに、それらの半直線物体の可視性は、特定の半直線物体に対して視点からの視線を遮る半直線物体はどれかを求めるという問題に帰着できるので、この問題を解く線形時間アルゴリズムを示す。また、解を可視本と呼ばれるデータ構造に構成する。ランダムな半直線物体列に対して得られた計算結果は極めて特徴的なものである。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we consider a viewpoint moving along a row of polygonal objects. In order to compute the visible portion of such objects we introduce a simplified model and define visibility problems in terms of the model. We then gpresent solution algorithms for the problems and finally give some computational results. First, we note that a polygon consists of verticies and edges and that the visibility of the edges can be found from the visibility of the vertices. The abovementioned simplified model for finding the visibility of vertices is constituted by a row of half-lines in the xy-plane which are all in parallel to the y-axis, and the viewpoint which moves on the line not crossing any of the half-lines. The visibility of the half-lines can be obtained by finding, for each of the half-lines, the half-lines which lie in front of it and shut off the ray to the viewpoint. We present a linear-time algorithm for solving the problems of finding such half-lines. The solution is stored in a data structure called the visibility tree. We also present some computational results which are obtained for randomly generated half-line rows and which seem quite characteristic to our model.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 32(1994-AL-044), p. 37-44, 発行日 1995-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会