- PR -

Shapeオブジェクトの重なり判定

1
投稿者投稿内容
カーニー
ぬし
会議室デビュー日: 2003/09/04
投稿数: 358
お住まい・勤務地: 東京
投稿日時: 2004-02-25 16:19
Java2Dで複数のノードと、それらを接続するリンクを表現するグラフィックを描画しようと考えています。
イメージとしては以下のような感じです。

コード:
ノードA ┬ ノードB
        │
        ├ ノードC ┐
        │         │
        │ ノードD ┴ ノードE ─ ノードF
        │
        └ ノードG


さて、各ノードは何らかのShapeオブジェクトで表現するとして、Graphics2Dオブジェクト上にリンクでつなぎながらノードを1つずつ配置していく際に、ノード同士が重ならないようにする必要があります。

今のところ「Shapeオブジェクトを置いて、重なったらずらす」というアルゴリズムを考えているのですが、Shapeオブジェクト同士の「重なり判定」を便利に行う方法はないかと思案しています。

新たなShapeを配置するたびにintersectメソッドで既存の全てのShapeに対してチェックするくらいしか思い浮かばないのですが、どなたかよい方法をご存じないでしょうか?

事前に重ならないように座標を計算しておくのも一案ですが、とりあえずは以上の前提で何かアドバイスをいただければと思います。
どうぞよろしくお願いいたします。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-02-25 17:47
unibon です。こんにちわ。

引用:

カーニーさんの書き込み (2004-02-25 16:19) より:
今のところ「Shapeオブジェクトを置いて、重なったらずらす」というアルゴリズムを考えているのですが、Shapeオブジェクト同士の「重なり判定」を便利に行う方法はないかと思案しています。

「重なり判定」ができても、そのつぎに「ずらす」アルゴリズムも必要になるかもしれませんが、以下は「重なり判定」についてのみ書きます。

引用:

カーニーさんの書き込み (2004-02-25 16:19) より:
新たなShapeを配置するたびにintersectメソッドで既存の全てのShapeに対してチェックするくらいしか思い浮かばないのですが、どなたかよい方法をご存じないでしょうか?

ここでの Shape とは、java.awt.Shape インターフェースのことでしょうか。それとも概念的なものを指されているだけなのでしょうか。というのも java.awt.Shape インターフェースにある intersects メソッドは引数が Rectangle2D クラスなので、せいぜい Shape と Rectangle2D との重なり判定には使えますが、Shape 同士の重なり判定の用途には使えないからです。
ただ、ノードは普通は簡単な幾何学的な形状(円、楕円や多角形程度)なので、自前で重なり判定をおこなうことはそれほどは難しくないとは思います。しかし、重なっているか否かの2値が分かったとしても、上述のようにどこにずらせば良いのかは分からないので、ノードを描くという目的のためには、重なり判定だけでは不十分かもしれません。
びしばし
大ベテラン
会議室デビュー日: 2002/03/13
投稿数: 181
投稿日時: 2004-02-25 17:49
ゲームに使われる手法に、画面と同じサイズの「その座標にShapeが表示されている/いない」を管理するビットマップを用意して、
新規Shapeは「すべての座標にまだなにも表示されていない」ところに配置する、という手法(名称は失念)があります。いかがでしょうか。

この方法の利点は既存Shapeの数がいくら増えても判定の計算量が一定なところです。
欠点はビットマップを用意するメモリ領域とビットマップの更新処理などが必要なことです。
カーニー
ぬし
会議室デビュー日: 2003/09/04
投稿数: 358
お住まい・勤務地: 東京
投稿日時: 2004-02-25 18:08
unibonさん、こんにちは。カーニーです。
お返事どうもありがとうございます。

引用:

unibonさんの書き込み (2004-02-25 17:47) より:
ここでの Shape とは、java.awt.Shape インターフェースのことでしょうか。それとも概念的なものを指されているだけなのでしょうか。というのも java.awt.Shape インターフェースにある intersects メソッドは引数が Rectangle2D クラスなので、せいぜい Shape と Rectangle2D との重なり判定には使えますが、Shape 同士の重なり判定の用途には使えないからです。

はい、java.awt.Shapeを実装するクラス(java.awt.Rectangleとか)のことです。
Shape#getBounds2D()でRectangle2Dを取得して、intersectsメソッドに渡してやろうかと思っています。・・・でイケますよね? まだコードは全然書いてないのですが。

引用:

ただ、ノードは普通は簡単な幾何学的な形状(円、楕円や多角形程度)なので、自前で重なり判定をおこなうことはそれほどは難しくないとは思います。しかし、重なっているか否かの2値が分かったとしても、上述のようにどこにずらせば良いのかは分からないので、ノードを描くという目的のためには、重なり判定だけでは不十分かもしれません。

ずらすほうもちと難しそうですが、ある程度のアイディアはありまして。
説明しようとすると、データ構造やら制約条件など込み入った話になってしまうので割愛させていただきますが。
まあ、ない頭振り絞ってがんばります。
カーニー
ぬし
会議室デビュー日: 2003/09/04
投稿数: 358
お住まい・勤務地: 東京
投稿日時: 2004-02-25 18:27
びしばしさん、お返事どうもありがとうございます。

引用:

びしばしさんの書き込み (2004-02-25 17:49) より:
ゲームに使われる手法に、画面と同じサイズの「その座標にShapeが表示されている/いない」を管理するビットマップを用意して、
新規Shapeは「すべての座標にまだなにも表示されていない」ところに配置する、という手法(名称は失念)があります。いかがでしょうか。

この方法の利点は既存Shapeの数がいくら増えても判定の計算量が一定なところです。
欠点はビットマップを用意するメモリ領域とビットマップの更新処理などが必要なことです。

最初は、何とかクラスの何とかメソッドをコールすると、重なってるShapeがIteratorで返される、みたいのを期待していましたが、そのアプローチはよさげですね。

よいヒントをいただきました。どうもありがとうございます。

名称を思い出したら、ぜひ教えて下さい!
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-02-25 18:46
unibon です。こんにちわ。

引用:

カーニーさんの書き込み (2004-02-25 18:08) より:
はい、java.awt.Shapeを実装するクラス(java.awt.Rectangleとか)のことです。
Shape#getBounds2D()でRectangle2Dを取得して、intersectsメソッドに渡してやろうかと思っています。・・・でイケますよね? まだコードは全然書いてないのですが。

ノードが Rectangle2D なのですね。てっきりいびつな形状なのかと勝手に思い込んでいました。だとしたら intersects メソッドが使えると思います。万が一 intersects が使えなくても2つの長方形の重なり判定は容易でしょう。

引用:

カーニーさんの書き込み (2004-02-25 16:19) より:
新たなShapeを配置するたびにintersectメソッドで既存の全てのShapeに対してチェックするくらいしか思い浮かばないのですが、どなたかよい方法をご存じないでしょうか?

これしかなく、逆に言えば、これがもっとも良いと思います。たしかに N 個あれば (N * (N - 1) / 2) 回の判定が必要になり、すなわち N の2乗のオーダーの計算が必要になりますが、でも原理的にそれしかないはずです。N が小さければ大丈夫です。
もっとも N が大きくなれば、びしばしさんのビットマップのような手法が必要になってきますが。
ちなみに、ノードの配置が2次元ではなく擬似2次元(1.5次元)のようなものならば、ある種の最適化もできると思います。縦はそれほど長くなくてきわめて横長の画面など、たとえば年表みたいなものとか。しかし、これは限られた用途の場合なので、これがあてはまらないことのほうが多いでしょう。
カーニー
ぬし
会議室デビュー日: 2003/09/04
投稿数: 358
お住まい・勤務地: 東京
投稿日時: 2004-02-26 11:10
こんにちは、カーニーです。

引用:

unibonさんの書き込み (2004-02-25 18:46) より:
ノードが Rectangle2D なのですね。てっきりいびつな形状なのかと勝手に思い込んでいました。


あぁ、ごめんなさい。
とにかく最終的に重なりがない状態になればいいので、それほど厳密に「重なっている」ことを判定できなくてもいいのです。

なのでShapeがいびつだとしても、Rectangle2D取ったレベルでの判定で十分間に合う、というのがこちらの事情であります。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-02-26 14:26
unibon です。こんにちわ。

特に回答ではないのですが、備忘録的に書かせていただきますと、要は2次元だとソートできないので効率の良い重なり判定ができないです。1次元ならばあらかじめ座標でソートしておけば、あるノードの周辺のノードだけを調べることができるのですが、2次元以上ではソートができないので八方ふさがりなのです。
1

スキルアップ／キャリアアップ（JOB@IT）