权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

精度保証機能を有する幾何アルゴリズムの開発

具有精度保证功能的几何算法的开发

基本信息

批准号：
14780246
负责人：
永井孝幸
金额：
$ 1.22万
依托单位：
Tottori University of Environmental Studies
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2003
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780246/
关键词：
計算幾何精度保証入力誤差反射計算反復計算

项目摘要

計算結果の精度保証を有効に行うには,誤差の過大評価を避けることがポイントとなる.従来,頂点・線分など個々の図形要素に対して精度属性を持たせる手法が知られている.しかし,この方法を多角形の集合演算に用いた場合は誤差の過大評価が発生しやすい.さらには精度属性を持った図形要素同士は相対的な位置関係が明確に定まらないため,図形の位置関係が明確に定まるものとして設計された幾何アルゴリズムを適用するのは困難である.安定して動作する幾何アルゴリズムを設計するには図形要素間の位置関係が明確に定まることが不可欠であるという観点から,多角形の各図形要素に精度属性を持たせて間接的に精度保証を行うのではなく,精度保証された多角形が表す境界を明示的に求めるという手法について基礎検討を行った.この手法では,図形要素の位置が明確に定まることから安定した幾何アルゴリズムを設計することが可能となり,また誤差の過大評価を避けられることも分かった.本年度は昨年度に行った検討に基づき,多角形の集合演算で精度保証を行うために必要となるデータ構造・基本演算について基礎的な実装を行った.精度保証計算の基本手続きとなる「多角形頂点の丸め演算」を幾何アルゴリズムライブラリCGAL・LEDAを用いて実装し、考案法が動作することを確認した.また実装した結果から、計算精度を高くした場合の実行速度の低下が著しいことが分かり,実装レベルでの更なる工夫が必要であることも判明した.研究結果については順次とりまとめ次第発表する予定である.

The accuracy of the calculation results is guaranteed. For example, vertexes, lines, and shape features, precision attributes are maintained, and methods are known. This method is used in polygonal set calculus, and the error is too large to be evaluated. The precision attribute is maintained in the shape of the element and the position relationship of the element is defined. The position relationship of the shape is defined. The design geometry is difficult to apply. The positional relationship between the polygon elements is clearly defined in the design of stable geometry, and the accuracy attribute of each polygon element is indirectly guaranteed. The method is to determine the position of the shape element, to determine the stability of the geometry, to design the shape element, to avoid the error of the shape element. This year's annual review is based on the analysis of the accuracy of the polygonal set calculation. The necessary structure and basic calculation are based on the implementation of the algorithm. Accuracy assurance calculation of the basic manual "Polygon vertex calculation" geometry is not used in the design, test method is used in the operation of the confirmation. When the calculation accuracy is high, the speed of operation is low, and the time required to complete the calculation is necessary. The results of the study are as follows: