線分や円弧をクリックして選択するプログラム
- CAD等の図面上の線分や円弧をクリックして選択するプログラムを作成する際の最適なデータ構造と探索アルゴリズムについて知りたいです。
- 現在の叩き台ではバウンディングボックスの情報を用意し、線形探索でクリック許容範囲内の線を見つけていますが、大規模な図面では時間がかかるため改善したいです。
- 学生の頃に学んだ2分探索法などは使えそうですが、2次元以上の高次元のデータ構造や探索アルゴリズムについての知識が足りません。どのような手法が適しているでしょうか？
- ベストアンサー
線分や円弧をクリックして選択するプログラム
CAD等で描かれた2次元の図面上の任意の線(線分や円弧)をクリックして選択するプログラムを作っています。 いまは叩き台として、各線のバウンディングボックス(線分や円弧を囲む最小の長方形)の情報(対角線の両端座標) が入った配列(実際はC++のSTL vectorです)を用意して、クリックした座標の一番近くに在る、若しくは内包する バウンディングボックスを線形探索して、見つかったバウンディングボックスに所属する線がクリック許容範囲内 であるかを分析しています。 しかし、この方法では線の数が少ないうちは良いのですが、大規模な図面になると時間が掛かってしまい 使い物になりません。 このような場合、どういったデータ構造でどのようなアルゴリズムで探索するのが良いのでしょうか? なにか定石的なものがあるのでしょうか? 恥ずかしながら、探索アルゴリズムというと学生の時に2分探索法等を習った程度で、2次元以上の高次元のもの 扱うアルゴリズムはピンときませんでした。
- その他（プログラミング・開発）
- 回答数3
- ありがとう数4
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
> やはりボロノイ図を応用するのが定石なのでしょうか？ いえ，点の場合はボロノイ図ですが，大きさのある図形は 多次元木を使う方がいいと思います．(ちょっと自信不足) 確か1993年頃だったと思いますが，PC-9801 ＋ MS-DOS 上で， ２次元木を使って多数の点や線分を高速検索するプログラムを ２～３種類書いたことがあります．ちょっとうろ覚えですが， ・数千個のランダムな点を画面に表示しておき，マウスをドラッグして 矩形領域を指定し，その中に含まれるすべての点の色を変える． ・数百本のランダムな線分を画面に表示しておき，現在のマウス位置Ｐに 最も近い線分を検索する．そしてＰを中心とし，その線分に接する円を 表示する． 今から見ればずいぶん非力な PC ですが，マウスをかなり速く動かしても 十分追随していたと思います．
その他の回答 (2)
- noocyte
- ベストアンサー率58% (171/291)
多次元木を使うことになると思います． 「計算幾何学」,「多次元木」などで検索してみるといいでしょう． 計算幾何学 (Wikipedia) http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%B9%BE%E4%BD%95%E5%AD%A6 ┌とりあえず「多次元木」で検索して見つけたページ ↓ここに書いてある多次元木の名前でさらに検索するといいと思います． 多次元木 (multidimensional tree) なぜ必要か？ http://alpha.c.oka-pu.ac.jp/~yokota/de/tajigen.htm ↓これは図形ではなく点の高速検索 緯度経度から地名を検索する方法。（リバースジオコーディング・リバースジオコーダ） http://okwave.jp/qa2711706.html
お礼
ありがとうございます。 やはりボロノイ図を応用するのが定石なのでしょうか？ 一応、手元にR.セジウィック著の「アルゴリズムC 第2巻」という本があるので、そちらと教えていただいたリンク先を参考に挑戦してみます。 リバースジオコーディング、リバースジオコーダという用語は初めて聞きました。これらについても調べてみます。
的外れな回答だったら申し訳ありません。 バウンディングボックスを複数内包するバウンディングボックスを作ってみてはいかがでしょうか？
お礼
ありがとうございます。 なるほど。闇雲に探索するよりは良さそうですね。 もう少し質問を締め切らずに待ってみます。
関連するQ&A
- 線をオブジェクトとして選択するアルゴリズムについて。
線とか、丸とかを描くグラフィック関係のソフトを作りたいのですが、 wordの図形描画の機能みたいに、ある線分をクリックすることでその線分がアクティブになって、移動をしたり、長さを変えるといったようなことをプログラムで作ろうとしたら、どのようなアルゴリズムを組んだらよいのでしょうか？ ちなみに、言語はVC++とVBを使うことができます。 簡単な考え方でもよいですし、どちらかの言語のプログラムを書いていただいても結構なので、どなたかお答えよろしくお願いします。
- 締切済み
- その他（プログラミング・開発）
- C言語での開発環境での線の扱い方
C言語での開発環境での線の扱い方 TSP問題を考えています。 １：2次元配列で座標(今回は5点程度)を用意。 (例)sorce[4][4]={{0,1},{3,8},{2,4},{2,7},{8,2}} ２：任意の点をスタート位置に設定。 ３：座標同士の距離を計測(ユークリッド距離)。 ４：(２)のうち最短距離を選ぶ。 ここまでできています。 これからアルゴリズムとしては、 ５：任意のスタート位置から最短距離にある座標を線で繋ぐ。 ６：繋いだ先の座標から最短距離にある座標を線で繋ぐ(これを繰り返す。)。 ７：もし線の交差があれば、交差している座標間で線を入れ替える。 この処理を行いたいのですが、まず線を引くような、処理をどうやったらC言語で行えるのか(実際に線を引いて出力するわけではありません。)がわかりません。 ですので、5番の方法だけでも結構ですので、教えてください。よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 2次元座標上の対称性を排除した点の組合せ
2次元座標上の対称性を排除した点の組合せ 質問です． グリッドの引かれた2次元座標上において，格子上の任意のn点の座標の組合せを求め，プログラムに入力することを検討しています． 現在は全組合せをプログラムに入力しているのですが，空間上に， ・x軸，y軸に関する線対称性 ・原点に関する点対称性 があるので，計算量削減のために，2次元座標上において，これらの対称性を排除した任意のn点の組合せを求めるアルゴリズムを作成したいのですが，何か定石のような考え方はないでしょうか． とりあえず，現在検討しているのが， 1. 2次元座標空間を軸上，第1～4象限と5つのエリアに分ける 2. 軸上にn点を取る場合，軸上に(n-1)点をとり，第1象限から1点をとる場合...と，思いつく全てのパターンについて組合せを考える といったものなのですが，もっとスマートな方法があるはずでは，と思い，質問させて頂きました． 以上，宜しくお願い致します．
- 締切済み
- 数学・算数
- 隣接行列プログラム
隣接行列を使ったグラフ探索のプログラムを作りたいのですが。。 手も足もでません。どなたか助けていただけないでしょうか？？ まずstate.txt 1 2 3 0 といったフォーマットに従った状態空間が記述された テキストファイルを読み込んで、隣接行列を動的に作成し、 さらにその状態空間をfwrite()を用いてバイナリ形式のファイルにする。 実行時のコマンドラインは次の書式に従う。 > ./MakeGraph テキストファイル(読み込み元） 状態空間(書き込み元） 状態数 [Enter] もうひとつは、上で作成した状態空間ファイル（バイナリ形式）をmalloc(),fread()を用いて メモリ上に復元し、経路探索を行う。 ただし、オプション指定で縦型探索と横型探索を切り替えられるようにすること。 実行時のコマンドラインは次の書式に従う。 > ./Search [-bd] 状態空間ファイル 状態数 開始状態 終了状態 [Enter] ちなみに、 使用例 > ./MakeGraph state.txt state.bin 4 [Enter] > ./Search -d state.bin 4 1 0 [Enter] > ./Search -b state.bin 4 3 3 [Enter] > ./Search -bd state.bin 4 2 0 [Enter] 結果例 1-0 : d : 0 <- 3 <- 1 3-3 : b : 3 <- 1 <- 0 <- 3 2-0 : b : Not Found... 2-0 : d : Not Found... これらを作るうえでのヒントのようなものもあるのですが、さっぱりで。。 状態空間をファイルから取り込むため、隣接行列で表現した状態空間のサイズは可変、 （たとえば、状態数５ならば、２５個）である。したがって、メモリは動的に確保する必要がある。 また探索時に容易に扱えるようにするため、隣接行列は２次元配列であることが望ましい。 しかし、２次元の動的確保は難易度が高いので、１次元配列の動的確保を応用することで考える。 １次元配列を状態数２個確保し、２点の座標を指定することで、要求する要素へ アクセスできるマクロCoordinates(x, y, size)を用意する。 このマクロを利用すれば、１次元配列で確保したデータを２次元として扱うことができる。 ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ MakeGraph.cとSearch.cは次にあります。 ここにはのせきれなかったので。。 お手数おかけします。 http://mugen.cc.osaka-kyoiku.ac.jp/pg/ あとstate.txt のフォーマットは次のようになっています。 これはデータ構造などででてくる有向グラフを隣接行列で示した場合、 スタート地点の状態０から状態１に（０→１） 状態１から状態２と、ゴールの状態３に（１→２、１→３） ゴールの状態３からスタート地点の状態０に（３→０） となっていた場合に、状態０～３までのリンク先をあらわしたものです。 単に、机上において、隣接行列で表現すると ０ １ ２ ３ ０ ０ １ ０ ０ １ ０ ０ １ １ ２ ０ ０ ０ ０ ３ １ ０ ０ ０ となります。（線がはいっていないのでややこしいかもしれませんが。。） これと同じ意味で、 1 （状態０のリンク先で、１の直後に￥ｎ） 2 3 （状態１のリンク先で、２と３の間に空白、さらに３の後ろに￥ｎ） （状態２のリンク先はなにもないので、まっしろ） 0 （状態３のリンク先） となっています。こういう説明で伝わっているかわかりませんが、 よろしくおねがいします！！
- 締切済み
- C・C++・C#
- ３次元的に曲がった線の一部のをまっすぐにしたとき…
３次元的に曲がった線の一部のをまっすぐにしたときの座標は？ 連続する空間上の線分をのばしたときの座標の求め方 図のように空間上に線分がつながっています。一か所Rがついた箇所があります。 P1,P2固定でそのRのついた曲がりをまっすぐに伸ばした場合のP4',P5'の座標の 求め方を教えてください。 焦ってます。早く回答をいただけると助かります。 よろしくお願いします<(_"_)> 説明図が不鮮明なので上記URLに画像を掲載します。 http://photos.yahoo.co.jp/ph/hirokotobuki2001/vwp?.dir=/ca4a&.src=ph&.dnm=57e8.jpg&.view=t&.done=http%3a//photos.yahoo.co.jp/ph/hirokotobuki2001/lst%3f%26.dir=/ca4a%26.src=ph%26.view=t
- 締切済み
- 機械設計
- イラストレータで、数本の線で囲まれた内側を図形として扱う方法
よろしくお願いします。 例として漢字の「井」の様に、縦２本、横２本の線で囲まれた形。 この内側の多角形(井の場合は四角形)を円や四角等と同じような図として認識し、塗りを指定するとクリックひとつで着色ができるような方法はないでしょうか？ 試しに次のことをやってみましたが良い結果ではありません。 (1)アンカーポイントの追加ツールで各交点をクリックし、アンカーとし、その後出っ張った各線の端部のアンカーをアンカーポイント削除ツールで削除し、残ったものが多角形になる。→線全体が消えてしまう。 (2)別のレイヤーでその形をトレースする。 →実際には曲線の入った複雑な形に使いたいので、直線で囲まれたシンプルな形なら良いですが、この場合トレース方式は求めていません。 (参考)最終的には、８コースある陸上トラックの様な図を描く途中段階で、円弧と直線を連結させた後、他のコースに交差してしまっている各円弧をコースの中だけそれぞれ削除するために使いたいです。 そして、コースごとに違う色で塗りたい計画です。
- ベストアンサー
- その他(ソフトウェア)
- ＤＸＦの変換精度
私はプラ型屋をやっている者ですが、最近では100%近く客先からＤＸＦデータを もらえるようになり、年々厳しくなっていく短納期化に伴い、少々精度が悪くても それを使って型設計やＮＣテープ作りをやってまいりました。しかしこのたび ３次元ＣＡＤを導入しましてＤＸＦを使ってモデリングしてみたところ、ほんの少し(加工上は全く関係の無い0.001mm以下の数字)でも線と円弧がずれていたり、たとえば誰が見ても90°で描いたであろうと思われる線が調べてみると89.9999785° だったりすると、うまくモデリング出来ず２次元の時と違い全く妥協を許しません。本当は図面を見ながら自分で２次元形状を描いてそれを押し出していけばいいのでしょうが．．．．そこで無理な注文かもしれませんが、例えば精度の悪いデータを変換時に少数点以下5桁目を四捨五入して6桁目以降は切り捨ててくれるとかが出来るソフト、もしくわそのようなサービスがあるサイトを知っている方いませんか。ちなみに使用ＣＡＤはAutoCAD2000iです。
- 締切済み
- 中間ファイル
- 複数の点の、相似・近似の確認
こんにちは、 現在、自作のプログラムを作成中の者です。 作成しているプログラムのアルゴリズムで、どうしても答えが出せない部分がありますので、お知恵を貸してください。 プログラム概略 ・画面にマウスで線を描く ・その線をデータベースに名前と共に保存 ・呼び出し画面で図形を書いた際に、登録してある図形から該当するものの名前を呼び出す。 といった処理を行おうと考えています。 現在完成している処理としては。 ・マウスをクリックして画面上でドラッグする間、一定の間隔でマウスの座標を所得し線を描く。 ・クリックを離した時点で、一連のマウスの座標を、配列変数に格納する。 ・複数のマウスクリック（複数の線）用に変数をもたせ管理する。 ・最後に、その形にあった状態でデータベースに保存する。 というところまで完成しているのですが。 保存されている情報と、呼び出しの際に描いた情報を結びつけるためのアルゴリズムが思いつきません。（一番要のところかもしれませんが・・・） データベースへの保存も、どういった情報を保存すればいいのか定まっていないので、改良中ではあります。 ただ、全く同じ図形（大きさも含めて）を描くことは現実的な操作ではないと思いますので。 どのような条件でデータベースとの照合を行えばいいのかを考えています。 漠然とした情報かとは思いますが、数学的な理論などでも勉強しますので、 このような感じの求め方 等のヒントを頂ければと思います。 長文、失礼いたしました。よろしくお願い致します。
- ベストアンサー
- その他（プログラミング・開発）
- 四次元とはどんな形ですか？
0次元が点とか1次元が線とかいうような切り口の解説は飽きるほど見てきましたが、四次元がどんな形なのはいまだに納得するイメージが得られていません。 線も面も立体も、その図形自体がその図形を含む空間に対して、それぞれ曲線、曲面、球体等という形で「曲がる」という性質を持ち得えますよね。そこからの類推で、記述に四次元を要する図形も、その図形の外側に対して曲がった部分を持っているのだろうなということは分かります。 また同様に、線も面は言うまでもなく、立体もメッシュ球といった例があるように、1次元から3次元までの図形のどれもが、線によってその全体像を表現できるということからの類推として、四次元もメッシュのような形で線分を使って表現可能なものであるのだろうと思います。 分からないのは、四次元の図形というものは空間に対してどのような占め方をするものなのだろうということです。 面は線を無限に集めたものだとたとえられることがありますが、やはり認識的には線と面、長さと面積というものは質的に異なるものに感じられます。面と立体もやはり、厚みを持たないものと厚みもといふくらみを持つものとして根本的な差異を感じます。 そうして立体に対して四次元の図形とは何かということになるわけですが、線と面は異なる、面と立体は異なる、という類推からいくと、立体と四次元の図形も根本的に異なるものなのだと思います。また体積と超体積も質的に別物なのでしょう。しかしどうにも私自身がいまだに超体積に対して体積の単純な延長上の概念としか認識できていないように感じます。 多胞体という言葉がありますけど、この言葉を使っている専門家はともかくとして、少なくとも私にとって胞がたくさんあるような図形というのはぶどうのようなものとしかイメージできず、三次元的な認識に囚われてしまっている感が否めません。線を無限にたくさん集めたものに対する面はちゃんと質的に異なるものとしてイメージされるのに、立体(胞)をいくら集めても所詮ぶどうのような、三次元に収まるものとしか考えられないわけです。 今まで書いたことをまとめれば、四次元の図形というのは、他の図形同様曲がるという性質を持つことができて、メッシュで全体像を描くこともできるようなもので、でもそれより下のどの次元の図形とも質的に異なっている図形である、ということで四次元に対して理解しているということです。 球を無限に薄く切っていった円を、再度円を順序よく貼り合わせれば球になることは当然のことです。三次元については各z座標に対応するいくつかの断面を見ただけでも、大ざっぱにこれは「球の断面図だな」と全体像を把握できてしまうでしょう。 しかし四次元も変数を一つ固定して得られる各立体を断面図とみなすものですが、どんなに細かくいろんな断面図を見ても、そもそもある断面図とそれにごく近い断面図がそれぞれどのように「くっついているのか」がわかりません。三次元の球から得られる断面図という場合であれば、ある断面図とそのごく近くの断面図のくっつき方は、上下の断面の端がなす輪郭が円周のごく一部になっているようなくっつき方(重なり方)なわけでしょう。それが全ての断面同士の関係においてそうであるということで、その完成形の球ともイメージの整合性がとれているわけです。 他方たとえば三次元球面は、二つの二次元球面の面同士をその内部が重ならないようにくっつけた形だといます。。二つの二次元球面が代表的かつそれで全体を構成するのに必要十分な、そういう四次元の図形の断面図とみなせるものなのでしょうが、この二つの断面図のくっつき具合が皆目見当がつきません。せいぜい団子のようなイメージしかできず、これは多胞体といわれてぶどうしか想像できないように、三次元からの質的な転換がまだできていないということなのだと思います。 結局四次元とはどんな形なのでしょうか?換言すれば、四次元の断面図のくっつき具合はどのようになっているのでしょうか？
- 締切済み
- 数学・算数
お礼
気が付くのが遅れてすみません。 2次元木を実装する方向で進めてみます。 ありがとうございました。