「筆順最適化 (地図描画の)」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【ひつじゅんさいてきか (optimal drawing (of map))】 地図(例えば道路地図)は多数の線分からなる図形と見なせるが, 一筆書きできれば...') |
|||
| 1行目: | 1行目: | ||
| − | 【ひつじゅんさいてきか (optimal drawing (of map))】 | + | '''【ひつじゅんさいてきか (optimal drawing (of map))】''' |
地図(例えば道路地図)は多数の線分からなる図形と見なせるが, 一筆書きできればプロッター等で無駄なく描ける. 一筆書きできないとき, ペンを上げて次に描くべき点まで移動して再びペンをおろして描くことになる. このペンを上げて空送りする操作は無駄な部分で, 高速に図を描く際は, できるだけ小さくしたい. これが筆順最適化問題であるが, この問題は, 平面最小重み完全マッチングになり, バケット法を基づいて高速に解かれている. | 地図(例えば道路地図)は多数の線分からなる図形と見なせるが, 一筆書きできればプロッター等で無駄なく描ける. 一筆書きできないとき, ペンを上げて次に描くべき点まで移動して再びペンをおろして描くことになる. このペンを上げて空送りする操作は無駄な部分で, 高速に図を描く際は, できるだけ小さくしたい. これが筆順最適化問題であるが, この問題は, 平面最小重み完全マッチングになり, バケット法を基づいて高速に解かれている. | ||
2007年7月13日 (金) 11:36時点における版
【ひつじゅんさいてきか (optimal drawing (of map))】
地図(例えば道路地図)は多数の線分からなる図形と見なせるが, 一筆書きできればプロッター等で無駄なく描ける. 一筆書きできないとき, ペンを上げて次に描くべき点まで移動して再びペンをおろして描くことになる. このペンを上げて空送りする操作は無駄な部分で, 高速に図を描く際は, できるだけ小さくしたい. これが筆順最適化問題であるが, この問題は, 平面最小重み完全マッチングになり, バケット法を基づいて高速に解かれている.