直線をマウスでクリックしたときの判定方法

[戻る]
ひで 2004/10/12(火) 18:30:01
環境は Visual studio .Net 2003, Win2000 SP4, MFC SDI です。

クライアント領域に直線を引いたとします。

そして、この直線をマウスでクリックしたとき、
直線がクリックされたことを判定したいのですが、良い方法が思いつきません。

思いつくのは、普通に直線上の座標とクリックされた座標を比較し、
判定する方法です。しかし、これは良い方法とは思えません。

良い方法をお持ちの方、ご教授していただけるとありがたいです。

2004/10/12(火) 21:34:14
>思いつくのは、普通に直線上の座標とクリックされた座標を比較し、
>判定する方法です。しかし、これは良い方法とは思えません。

良くないと判断したのは何故でしょうか?
どの程度直線に近ければ直線を指していると判断したいのでしょうか?

ひで 2004/10/12(火) 22:47:20
ご返信ありがとうございます。

> 良くないと判断したのは何故でしょうか?

良くないと判断したのは、直線の数が多くなった場合、
判定(if 文)に時間がかかってしまうからです。
そのため、直線を MFC CWnd のようなクラスから派生させてクラス化し、
マウスからのメッセージを受け取ることができればうまくいくかと
考えているのですが、具体的な方法が思いつきません。

> どの程度直線に近ければ直線を指していると判断したいのでしょうか?

ほぼ、直線上です。
例えば、MS Power Point などで直線を引き、それを選択するような感じです。

2004/10/13(水) 02:30:40
>良くないと判断したのは、直線の数が多くなった場合、
>判定(if 文)に時間がかかってしまうからです。

どのくらい多くなったら判定にどのくらい時間が掛かるのでしょうか?
少なくとも、直線が一本の場合に実験なさった上でなければ何も判断できないように思います
まさかとは思いますが、一つの判定に要する時間の本数倍の時間が掛かるとは考えていない
でしょうね

>例えば、MS Power Point などで直線を引き、それを選択するような感じです。
私は Power Point など使ったことありませんので、例にされても判りませんが

>直線を MFC CWnd のようなクラスから派生させてクラス化し、
>マウスからのメッセージを受け取ることができればうまくいくかと
>考えているのですが、具体的な方法が思いつきません。
直線はウィンドーとしては相応(ふさわ)しくないので、 CWnd から派生させるのはどうなん
でしょうね(直線同士が重なった場合、どの直線にマウスメッセージが届くのでしょうか?)

Takahashi 2004/10/13(水) 09:29:25
島さんの仰るとおり、CWndはまずいんではないかなと・・・
直線自体をクラス化した方がいいように思います。
例えば

class line
{
public:
    int x1;    // 直線の始点(x1, y1)
    int y1;
    int x2;    // 直線の終点(x2, y2)
    int y2;

    int z;    // 直線が重なった場合の Z オーダー

    // マウス座標 (x, y) が 直線上に位置するかを調べる
    bool hit(int x, int y);

    // 描画
    bool draw(HWND wnd);
};

かなり適当ですが、こんな感じでどうでしょうか?
線を引いたら、list なり vector なりに push していけば、
オブジェクトを管理できます。
直線上にあるかは、保存してあるオブジェクト
についてそれぞれ hit を呼び出して判定すればよいのではないでしょうか?

また、line のメンバ hit, draw をもつ基底クラスから派生する形を取れば
円とかいろいろかけると思います。

たいちう 2004/10/13(水) 10:15:12
> 良くないと判断したのは、直線の数が多くなった場合、
> 判定(if 文)に時間がかかってしまうからです。

実際に試したわけではないんですよね?

私の感覚ではプログラムがOSとやり取りする時間に比べると、
プログラム内部の処理の時間はよっぽど短いものです。
直線の数やアルゴリズム、マシンスペックにもよりますが、
(恐らく)数千本程度なら遅いと感じないのではないでしょうか。

Takahashiさんの例がシンプルなので、その方法で実装してみて、
実際に時間がかかりすぎるようなら再度質問されてはいかがでしょうか。

επιστημη [E-Mail] [HomePage] 2004/10/13(水) 10:16:39
> また、line のメンバ hit, draw をもつ基底クラスから派生する形を取れば
> 円とかいろいろかけると思います。

class shape {
public:
  virtual ~shape() {}
  virtual bool hit(int x, int y) const =0;
  virtual void draw(HWND wnd) const =0;
};

class line : public shape { ... };
class circle : public shape { ... };

…とかなんとか。

SunPac 2004/10/13(水) 15:13:09
LineDDA()やPtInRegion()APIなんかhit(int x, int y)に使えそうですね。
LineDDA()は遅いけど、確実でしょう。
PtInRegion()は直線が太さを持ったり、あるいは複雑な図形にも応用できるでしょう。
ただの直線なら普通に計算してもいいと思うけど。

ちなみにdraw(HWND)はdraw(HDC)の方がよさげ。裏画面に描画するかもしれないから。

2004/10/14(木) 10:48:42
おそらく、異なる二点ABが作る線分上にある点Cが存在するかという問題に読み替えること
が出来ると思いますが、点A,B,Cの座標が整数の場合、線分の生成方式に合わせた
判定が必要ですから(DDA,Bresenham 等で微妙に異なるから)、マウスの座標の点の色が
判定したい線分の色になっているかどうかが最後の決め手になるでしょう(交叉していたり、
連結したりしている場合は交点や、頂点の色がどちらの線分の色なのか判っている必要がある
でしょう)。こういう面倒な判定がお嫌なら、判定したい線分だけビットマプ上に描画して
おいてマウスの座標に対応する点の色が線分の色かどうかで判定できると思います
(以上はほぼ直線上というお返事から判断した上でのものなので、一ドット程度が許容範囲と
いうことでしたら、計算で線分にのっているかどうかの判断が出来ると思います)

Takahashi 2004/10/14(木) 12:44:36
結構 hit の実装方法がありますね。(参考になります)
ちなみに、私だったらこうするかな・・・

直線 (x1, y1) - (x2, y2) から一次方程式 f(x) = ax + b
の a, b を計算します。
a, b は hit で何回も使用するものですから、直線の描画と同時に計算します。

マウスの座標 (mx, my) の mx を f(mx) と代入
マウスY座標 my と直線のY座標のズレ dy は
dy = |f(mx) - my| で求められますので、
「dy < 許容する範囲 だったら hit」で判定します。

# 多分、島さんと同じ考えだとは思うのですが、
# なんか考え方間違っていたりして・・・算数苦手なので・・・

重なっていた場合については、list 等のコンテナに記憶した場合に
push_back ならば後方のものほど新しい、つまり上層にあるということですから、
後端から探索を開始して、hit したものを選択したと見なします。
さらに探索すれば、裏側にあるものに対しても選択ができるでしょう。

また、SunPac さんの提示してくれた関数は結構おもしろいと思います。
複雑な形状を扱う場合に PtInRegion() は重宝しそうです。
# こんな関数があったなんて知らなかった・・・あと、HDC のほうがいいですね。
# というか、MFC のようなので CDC* かな。

・・・私の方法だと計算が多くてかえって速度が遅くなるかもです。
ひでさんは、何かと速度を気にしておられるようなので、皆さんが示してくれた
いろいろな方法を実際にテストしてみて、計算にかかった時間を測定するのが
問題解決のための一番の近道なのではないでしょうか。

#よく考えると Z オーダーを入れると結構めんどくさいですね。
#list の順番で管理した方がよさげです。

dairygoods 2004/10/14(木) 13:10:49
画面と同じサイズの二次元配列 hit[width][height] を用意しておいて、
hit[x][y] = そこにあるshape;
となるようにあらかじめ計算しておく方法もあります。

ビットマップを用意して、
shape番号を色として許容する太さの線を描いておくようにすれば、
自分でhit[x][y]の値を計算して埋めるより、更に楽になります。

ひで 2004/10/15(金) 03:43:29
皆様、ご意見ありがとうございます。
返事が遅くなってしまい、申し訳ありませんでした。

皆さまからのご意見を参考に、実際にプログラムを組み、無事成功いたしました。

作成したのは、次のような仕様です。

・直線をクラス化

・判定には、直線の式 y = a*x + b により直線上の点を求め、クリックされた座標と比較

一見、簡単そうに思えますが、
実際に試してみるとなかなか思うように行きませんでした。
問題になったのは次の2点です。

・直線の式に関すること

・直線上の座標とクリックされたポイントの比較

まず、直線の式に関する問題を説明します。

例えば、直線の座標を 始点(x1, y1)、終点(x2, y2)とします。
すると、直線の式は次の様になります。

 y = (y2 - y1)/(x2 - x1)*(x - x1) + y1

このとき、分母 (x2 - x1) が 0 になるとき、計算不可となります。
また、横軸 x の範囲 rangex = x2 - x1 が小さな値になるとき、
この直線は rangex + 1 回の判定ポイントしか持ちません。
具体的に説明しますと、始点(0, 0)、終点 (2, 300) の直線があったとします。
ほぼ垂直な長い直線です。この直線の x の範囲は 0, 1, 2 しかありませんので、
長い直線にもかかわらず、判定ポイントを 3 つしか持たないため、
直線の始点、中点、終点のいずれかをクリックしないと判定できません。

この問題を解決するため、私は次のような方法を取りました。

”傾きの絶対値が 1 より小さい場合、y = a*x + b の式を用いる。
  傾きの絶対値が 1 より大きい場合、x = c*y + d の式を用いる。”

この方法により、この問題は解決されました。


つぎに、直線上の座標とクリックされたポイントの比較の問題について説明します。

私の場合、完全な直線上ではなくて、ほぼ直線上で判定されてほしかったため、
以上の判定方法ですと期待通りの動作にはなりませんでした。
クリックしたポイントの座標と、直線上の座標が完全に一致しないと、
クリックされたと判定されないため、非常にクリック判定を得るのが大変でした。
何度も非常に丁寧にクリックして、やっとクリック判定を得られるような感じでした。

この問題を解決するために、
直線状の点を中心に持つ CRect(縦、横の長さは数ピクセル)の中に、
クリックしたポイントが入っているかどうかで判定することにしました。
判定には CRect::PtInRect() を用いました。

この方法により、この問題は解決されました。


このクラスを用いて、クライアント領域に 1000 本のランダムな直線を引いて
クリックしてみました。
皆様の言われるとおり、気になっていた判定時間は全く問題ありませんでした(Pen4
2.2G)。


また、他にもいろいろ判定方法に関するアドバイスを頂きまして、
ありがとうございました。
今回は、直線の式を用いましたが、他の方法も非常に参考になりました。

ただ、一つ気になるのは、マウスからのメッセージを直接受け取ることはできないので
しょうか?
今回作成したクラスでも良いのですが、マウスクリックは 

void C****View::OnLButtonDown(UINT nFlags, CPoint point)

でクリックされたことを判断しています。そして、この関数内で、
描画された直線の hit() を順次呼び出しています。
そうではなくて、直線が直接メッセージを受け取ることができれば、
マウスクリックの判定も自動的に行ってくれるので楽になると思い、
CWnd から派生していれば、メッセージも受け取ることができるので、
良いかなと考えていました。
フレームや、メニューの無い細長いウィンドウでできないかなと・・・。
ただ、斜めの直線とかできるのかな?・・・
オブジェクトのサイズも大きそうだし・・・
など、いろいろ問題はありますが。

あと、作成した直線クラスのソースは載せたほうが良いでしょうか?
ヘッダ、.cpp あわせて約 140 行です。

REE 2004/10/15(金) 10:30:03
>直線状の点を中心に持つ CRect(縦、横の長さは数ピクセル)の中に、
>クリックしたポイントが入っているかどうかで判定することにしました。
>判定には CRect::PtInRect() を用いました。

これでもいいですが、この程度であれば、その中心とマウスカーソルの座標の差を取って
その絶対値で比較することも出来ます。

>そうではなくて、直線が直接メッセージを受け取ることができれば、
>マウスクリックの判定も自動的に行ってくれるので楽になると思い、
>CWnd から派生していれば、メッセージも受け取ることができるので、
>良いかなと考えていました。

可能ですが、今回の例では適切ではないと思います。

dairygoods 2004/10/15(金) 11:02:42
> そうではなくて、直線が直接メッセージを受け取ることができれば、
> マウスクリックの判定も自動的に行ってくれるので楽になると思い、
> CWnd から派生していれば、メッセージも受け取ることができるので、
> 良いかなと考えていました。

これは、ひでさんがやったことをOSにやってもらうだけで、
本質的な違いはありません。
(楽にはなるのかもしれませんが、ループが無くなるわけではありません。)

ウィンドウの場合は、あらゆる形のものを扱うための、
より複雑な当り判定計算が行われていますし、当り判定以外の様々な処理が伴います。
当り判定のためだけに流用するには、ウィンドウの仕組みは大袈裟過ぎると思います。

2004/10/15(金) 11:34:47
>クリックしたポイントの座標と、直線上の座標が完全に一致しないと、
>クリックされたと判定されないため、非常にクリック判定を得るのが大変でした。
>何度も非常に丁寧にクリックして、やっとクリック判定を得られるような感じでした。

だから最初にどの程度近ければ良しとするのか尋ねたのですがねえ
>>一ドット程度が許容範囲ということでしたら、計算で線分にのっているかどうかの判断が
>>出来ると思います
は参考にならなかったのでしょうか?

総当りで判定させているようですが、可能性のあるものだけ検査すればいいのです
確実に離れている線分は判定対象から外すことで判定対象が絞れます

>そうではなくて、直線が直接メッセージを受け取ることができれば、
>マウスクリックの判定も自動的に行ってくれるので楽になると思い、
>CWnd から派生していれば、メッセージも受け取ることができるので、
>良いかなと考えていました。

>>(直線同士が重なった場合、どの直線にマウスメッセージが届くのでしょうか?)
についてはどうお考えでしょうか?

ひで 2004/10/15(金) 23:15:36
ご返信ありがとうございます。

REE さん

> これでもいいですが、この程度であれば、
> その中心とマウスカーソルの座標の差を取ってその絶対値で比較することも出来ます。

そのほうが良いですね。その方法に変更します。

dairygoods さん

> ウィンドウの場合は、あらゆる形のものを扱うための、
> より複雑な当り判定計算が行われていますし、当り判定以外の様々な処理が伴います。
> 当り判定のためだけに流用するには、ウィンドウの仕組みは大袈裟過ぎると思います。

CWnd から派生させるのはベストではなさそうですね。

島 さん

>だから最初にどの程度近ければ良しとするのか尋ねたのですがねえ

>>一ドット程度が許容範囲ということでしたら、計算で線分にのっているかどうかの判断が
>>出来ると思います
>は参考にならなかったのでしょうか?

もちろん、参考になりました。
ただ、一ドットの許容範囲内で直線をクリックするのが、こんなに難しいとは思いません
でした。

> 総当りで判定させているようですが、可能性のあるものだけ検査すればいいのです
> 確実に離れている線分は判定対象から外すことで判定対象が絞れます

なるほど。私の思いつく判定対象の判別方法は、直線を囲む最小の四角形の中に、
クリックされたポイントが含まれているかどうかで判別できるように思います。
他にも判別方法があれば、ご教授願います。

>>(直線同士が重なった場合、どの直線にマウスメッセージが届くのでしょうか?)
> についてはどうお考えでしょうか?

私の作成しているアプリの場合、どちらの直線にマウスメッセージが
届いても問題ないので、このことに関しては問題にしていません。

ひで 2004/10/18(月) 23:56:57
[[解決]]
いくつかの報告をして、解決にしたいと思います。

PC のスペックは Pen4 2.2G です。

クライアント領域全体に 10000 本の直線をランダムに引き、
10000 本目の直線をクリックしたときにかかる判定時間は
約 0.016 [s] でした。1本目から順に hit をよんでいます。
もちろん、Release モードでコンパイルしています。

島さんの言われるように、判定対象を判別した場合、
今回の場合では若干の高速化が得られました。
直線の引かれ方によっては、より高速になると思います。

また、Takahashi さん、REE さんが言われるように、
差分の絶対値で判定を行った場合、PtInRect() に比べて、
非常に高速になりました。約 1/10 以下の時間になりました。

以上の例は、両者とも採用した場合です。

これで解決にしたいと思います。
ありがとうございました。

古いスレッドには追加発言できません。