グリッド点を保存する幾何学的変換とその応用に関する研究

資料種別: 文書・図像類

著者: 浅野, 哲夫ほか

出版者: -

出版年: 1995-03-26

資料形態: デジタル

ページ数・大きさ等: -

NDC: -

すべて見る

資料に関する注記

一般注記：: 金沢大学 / 大阪電気通信大学コンピュータの画面に代表されるようなグリッド平面上では、直線はグリッド点の系列として、塗りつぶし図形はグリッド点の集合として表現される。直線や2次曲線をいかにグリッド点の系列として表現するかについては多くの研究がなされているが、問題の計算複雑度に関する理論的な解析はあま...

書店で探す

全国の図書館の所蔵

国立国会図書館以外の全国の図書館の所蔵状況を表示します。

連携機関・データベースの一覧

所蔵のある図書館から取寄せることが可能かなど、資料の利用方法は、ご自身が利用されるお近くの図書館へご相談ください

その他

金沢大学学術情報リポジトリKURA
デジタル
連携先のサイトで、学術機関リポジトリデータベース（IRDB）（機関リポジトリ）が連携している機関・データベースの所蔵状況を確認できます。
金沢大学学術情報リポジトリKURAのサイトでこの本を確認

書店で探す

書誌情報

この資料の詳細や典拠（同じ主題の資料を指すキーワード、著者名）等を確認できます。

デジタル

資料種別: 文書・図像類
タイトル: グリッド点を保存する幾何学的変換とその応用に関する研究
著者・編者: 浅野, 哲夫
Asano, Tetsuo
著者標目: 浅野, 哲夫
Asano, Tetsuo
出版年月日等: 1995-03-26
出版年（W3CDTF）: 1995-03-26
並列タイトル等: A study on geometric transformation preserving grid points and its applications
タイトル（掲載誌）: 平成5(1993)年度科学研究費補助金一般研究(C) 研究成果報告書概要 = 1993 Fiscal Year Final Research Report Summary
巻号年月日等（掲載誌）: 1992 – 1993
掲載巻: 1992 – 1993
掲載ページ: 2p.-
本文の言語コード: jpn
件名標目: 計算幾何学
アルゴリズム
計算複雑度
コンピュータ・グラフィックス
整数計画法
Computational Geometry
Algorithm
Computational Complexity
Computer Graphics
Integer Programming
対象利用者: 一般
一般注記: 金沢大学 / 大阪電気通信大学
コンピュータの画面に代表されるようなグリッド平面上では、直線はグリッド点の系列として、塗りつぶし図形はグリッド点の集合として表現される。直線や2次曲線をいかにグリッド点の系列として表現するかについては多くの研究がなされているが、問題の計算複雑度に関する理論的な解析はあまりなされていないのが現状である。本研究の目的は、グリッド平面上に任意の閉図形が与えられたとき、その内部に含まれるグリッド点を効率よく列挙するアルゴリズムを開発することであった。最初に、グリッド点を保存する幾何学的変換に基づいて効率のよいアルゴリズムを考案し、計算機実験を行なってその有効性を確認した。基本的なアイディアは、グリッド点をグリッド点に写す変換を用いて素朴な方法で効率よくグリッド点を列挙できる部分(密な部分)とグリッド点が疎な部分に分割するという操作を後者の部分が十分小さくなるまで繰り返すというものである。この繰り返し回数は与えられた図形のディメンジョンの対数をとったものになるから、効率のよい実行が可能になる訳である。また、この変換法をうまく用いて2変数の整数計画問題に対する効率のよいアルゴリズムも与えた。これについても計算機実験を行なった。計算機実験に用いたプログラムのリストの一部(主要部分のみ)は報告書に含めておいた。さらに他方面への応用例として、画像のディジタル・ハーフトーニングの問題さらにはディジタル画像から直線や円のような基本図形の成分を検出する問題についても考察し、効率のよいアルゴリズムを得ることに成功した。これらの問題に対して従来から様々な方法が提案されているが、問題の計算複雑度が厳密に解析されたことがなかった。その意味で本研究は重要な一石を投じたものと思われる。
In this research we have developed efficient algorithms for reporting all the grid points within a given convex polygon in optimal time and also applied the algorithm for two-dimensional integer programming. We have also implemented those algorithms using C language and evaluated their practical efficiencies.The results were quite satisfactory. We further extended the similar idea to some other problems : digital halftoning of pictures of multiple brightness levels and that of detecting all possible digital components of a specified curve in a digital picture.
研究課題/領域番号:04650331, 研究期間(年度):1992 - 1993
出典：「グリッド点を保存する幾何学的変換とその応用に関する研究」研究成果報告書　課題番号04650331（KAKEN：科学研究費助成事業データベース（国立情報学研究所））（https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-04650331/046503311993kenkyu_seika_hokoku_gaiyo/）を加工して作成
DOI: 10.24517/00061985
一次資料へのリンクURL: https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55710&item_no=1&attribute_id=26&file_no=1
https://kanazawa-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=55710&item_no=1&attribute_id=26&file_no=1
オンライン閲覧公開範囲: 限定公開
著作権情報: CC BY-NC-ND
関連情報: https://kaken.nii.ac.jp/search/?qm=90113133
https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-04650331/
https://kaken.nii.ac.jp/ja/report/KAKENHI-PROJECT-04650331/046503311993kenkyu_seika_hokoku_gaiyo/
連携機関・データベース: 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
提供元機関・データベース: 金沢大学 : 金沢大学学術情報リポジトリKURA