人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

一次元領域の重なり検出のアルゴリズムについての質問です。

たとえば
領域A(1以上?7以下;以下同様),
領域B(2?5),
領域C(3?9)
から
重なり領域イ(2?3)AとB
重なり領域ロ(3?5)AとBとC
重なり領域ハ(5?7)AとC
というような解をもとめるアルゴリズムで知られたものがあるでしょうか?
Webページないし,書籍での資料を教えていただければ幸いです。
CやRubyなどでのサンプルがあるとなおありがたいです。

●質問者: snpia
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:Ruby Web アルゴリズム 一次元 書籍
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● haruo-31
●35ポイント

行列演算アルゴリズムと呼ばれる分野ですよね。

とりあえず詳しくないながらURLを張っておきます。

http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/geo.html

1次元であってもY軸を0にしたりして、無理やり2次元にして計算してしまえば良いと思いますよ。

◎質問者からの返答

ご回答ありがとうございます。

「面と面の重なり検出」「面と点の重なり検出」というのは一つの分野のようですね

他に自分で

http://mgccl.com/2007/07/04/1d-segment-intersection-detection-pa...

http://en.wikipedia.org/wiki/Segment_tree

http://en.wikipedia.org/wiki/Interval_tree

なども見つけてみました。

ただ,私の今回の目的には,ちょっとやりすぎのようでしたので,結局,次の回答者様の

アルゴリズムを採用しました。ともあれ,とてもいい勉強になりました。


2 ● ita
●70ポイント ベストアンサー

アルゴリズムとしては特別なものはいらないと思います。

全ての領域の両端の値と、それが左か右かの情報と組にします

struct Bndry

{

double pos; //位置

char LR; //右か左か

int idx; //何番目の領域か

}

これを全部用意してからposの値でソートします。

並び替えた小さい方から順に見て行って、初期値0の変数を、LRを見て

左端なら+1、右端なら-1していきます。

これが2以上となる部分が重なってる部分です。

元のデータ

pos,LR,idx

1,L,0

7,R,0

2,L,1

5,R,1

3,L,2

9,R,2

ソート

ーーーー

カウンタ

0

1L 1

2L 2

二重

3L 3

三重

5R 2

二重

7R 1

9R 0

◎質問者からの返答

ご回答ありがとうございました。この方法で実装することが出来ました。

実際には構造体に「領域(区間)名」を入れることで,どの区間が,重なっているかも

出力することにしました。

とてもエレガントな解だと思います。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ