C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[15]: 時計回り、反時計回り判定


(過去ログ 18 を表示中)

[トピック内 44 記事 (1 - 20 表示)]  << 0 | 1 | 2 >>

■6130 / inTopicNo.1)  時計回り、反時計回り判定
  
□投稿者/ セイン (13回)-(2007/08/01(Wed) 18:29:26)
セイン さんの Web サイト

分類:[C/C++] 

以前はお世話になりました。
時計回り、反時計回りの判定方法として、下記サイトの一番上に書いてある行列の計算から求めてみましたが、
特定の条件時は、当てはまらないようです。
http://web2.incl.ne.jp/yaoki/arl.htm

私が書いたソース
vertexs は、3点座標が格納されたベクターの配列です。

/*------------------------------------------------------------------*/
/** 時計回りチェック
* @return
* CLOCK_WISE 0 //Clock-Wise :時計回り
* COUNTER_CLOCK_WISE 1 //Counter Clock-Wise : 反時計回り
*/
/*------------------------------------------------------------------*/
int CGLDraw::ClockWiseCheck
(
vertexs vertexsList ///< [i]座標列情報
)
{
/*
|vertex[0]x vertex[1]x| |vertex[1]x vertex[2]x| |vertex[n]x vertex[0]x|
| |+| |…| |=A
|vertex[0]y vertex[1]y| |vertex[1]y vertex[2]y| |vertex[n]y vertex[0]y|
Aの値<時計回り
Aの値<反時計回り
Aの値<同一直線
*/

double sum = 0; ///< 合計値 sum<0 時計回り sum>0 反時計回り
for(DWORD i=0; i<vertexsList.size(); ++i) {
if(i != vertexsList.size()-1) {
sum += ((vertexsList[i].x * vertexsList[i+1].y)-(vertexsList[i+1].x * vertexsList[i].y))/10000.0;
}
else {
sum += ((vertexsList[i].x * vertexsList[0].y)-(vertexsList[0].x * vertexsList[i].y))/10000.0;
}
}

if(sum>0) { return COUNTER_CLOCK_WISE;}
else if(sum<0) { return CLOCK_WISE;}
else { return NO_CLOCK_WISE;}
}



上記の式で判定すると、逆周りと判定されてしまう座標列。
[0] {x=169.90084838867187 y=206.44012451171875}
[1] {x=169.90084838867187 y=204.56155395507812}
[2] {x=261.70086669921875 y=204.56155395507812}
[3] {x=261.70086669921875 y=206.44012451171875}
[4] {x=261.75085449218750 y=206.40176391601562}
[5] {x=261.80084228515625 y=206.38104248046875}
[6] {x=261.80084228515625 y=110.74208068847656}
[7] {x=261.80084228515625 y=110.74208068847656}
[8] {x=261.75085449218750 y=110.72137451171875}
[9] {x=261.70086669921875 y=110.68299865722656}
[10] {x=261.70086669921875 y=112.56156921386719}
[11] {x=169.90084838867187 y=112.56156921386719}
[12] {x=169.90084838867187 y=110.68299865722656}
[13] {x=169.85086059570312 y=110.72137451171875}
[14] {x=169.80084228515625 y=110.74208068847656}
[15] {x=169.80084228515625 y=206.38104248046875}
[16] {x=169.85086059570312 y=206.40176391601562}
[17] {x=169.90084838867187 y=206.44012451171875}


どなたかヒントを教えてください。
引用返信 編集キー/
■6131 / inTopicNo.2)  Re[1]: 時計回り、反時計回り判定
□投稿者/ Jitta (385回)-(2007/08/01(Wed) 19:07:51)
2007/08/01(Wed) 19:27:23 編集(投稿者)
2007/08/01(Wed) 19:23:25 編集(投稿者)

携帯から、キチンと見ているわけではありません。

判定結果を足しているからじゃないですか?

じゃ、どうする?
小さい三角をつなぎ合わせてどうこう…と、どこぞで読んだかすかな記憶



あれ?正負の数を数えて、多い方?全部0なら直線。同じ数なら、最後の符号?かな?



ん?階段のように、曲がりながら直線状に並んだら、どう判定する?
引用返信 編集キー/
■6132 / inTopicNo.3)  Re[1]: 時計回り、反時計回り判定
□投稿者/ れい (26回)-(2007/08/01(Wed) 20:24:38)
No6130 (セイン さん) に返信
> 時計回り、反時計回りの判定方法として、下記サイトの一番上に書いてある行列の計算から求めてみましたが、
> 特定の条件時は、当てはまらないようです。

なぜ行列式の和で出るとおもったのでしょうか?
あれは3点でだけ成り立つ特殊な場合です。
複数点に拡張した場合は成り立ちません。

Clockwise/Unclockwiseの判定は
簡単でエレガントな方法があります。

引用返信 編集キー/
■6135 / inTopicNo.4)  Re[2]: 時計回り、反時計回り判定
□投稿者/ セイン (14回)-(2007/08/02(Thu) 09:16:47)
セイン さんの Web サイト
2007/08/02(Thu) 15:12:24 編集(投稿者)
2007/08/02(Thu) 15:12:20 編集(投稿者)

>あれ?正負の数を数えて、多い方?全部0なら直線。同じ数なら、最後の符号?かな?
三日月のときに成り立ちませんよねぇ。

>ん?階段のように、曲がりながら直線状に並んだら、どう判定する?
どうなんでしょう?

>なぜ行列式の和で出るとおもったのでしょうか?
>あれは3点でだけ成り立つ特殊な場合です。
>複数点に拡張した場合は成り立ちません。
>Clockwise/Unclockwiseの判定は
>簡単でエレガントな方法があります。

どんな方法なんですか!ぜひ教えてください。
引用返信 編集キー/
■6211 / inTopicNo.5)  Re[3]: 時計回り、反時計回り判定
□投稿者/ セイン (15回)-(2007/08/06(Mon) 09:35:25)
セイン さんの Web サイト
>Clockwise/Unclockwiseの判定は
>簡単でエレガントな方法があります。

引き続き、時計回り、反時計回りの判定方法を募集しています。
引用返信 編集キー/
■6214 / inTopicNo.6)  Re[4]: 時計回り、反時計回り判定
□投稿者/ Zee (9回)-(2007/08/06(Mon) 11:44:23)
Zee さんの Web サイト
No6211 (セイン さん) に返信
測量屋の出番でしょうか?

・時計回りと反時計回りを判断するには3点を使い、角度を算出したのちに、どちらが大きいのかを判断すれば足ります。

座標系自体は2種類あるので
・数学系(Xが横軸) 例えば:画面内の座標
・測量系(Xが縦軸)    :測量^^;
どちらを使うかによります。

時計は0又は12時が上になっているので、
測量系と考えて12時の方向を0度とするようにします。

・・・長くなりそうだ・・・
2点の座標を求めるときに、ピタゴラスの定義を使用しますが、
その2点の座標差をΔXとΔYとすると
それらを用いて、三角関数tan(タンジェント)の逆三角算数の「アークタンジェント」を使用します。
(計算のやり方は調べればわかるでしょう)

第2番目の基点となる地点から第1番目、第3番目の方向を計算し、
それから差引して+であれば、時計まわり、−であれば反時計回りとすれば良いんじゃないでしょうか。

但し、360度を超える時や
例外として1周以上する場合の分岐などに備えることが必要となります。

Cで書けない私ですので、ヒントになればと^^;
引用返信 編集キー/
■6215 / inTopicNo.7)  Re[5]: 時計回り、反時計回り判定
□投稿者/ y4yama (7回)-(2007/08/06(Mon) 12:06:03)
前提条件をもっとはっきり知りたいものです・・・
8の字のようになることは?
2重にぐるぐる回って(ある交差をするが)しまうことは?
ほぼ直線上(続いた3点が180度または、折り返して0度に並ぶ)ことは?
時計方向とは、わかるんだけど、座標系はX右、Y上とするの?(統一したら以下の話が楽になるため、あえて)
引用返信 編集キー/
■6224 / inTopicNo.8)  Re[6]: 時計回り、反時計回り判定
□投稿者/ 2リットル (1回)-(2007/08/06(Mon) 14:00:31)
Jittaさんの言われていることと同じになりますが、
多角形を3点ごとに分解してベクトル外積の総和をとり、
総和が正ならば時計周り、負ならば逆周り、0ならば同一直線状というアプローチはどうでしょうか。

件の例でいうと
vertex[0]を点A、vertex[1]を点B、、、vertex[16]を点Q, vertex[17]を点Rとしたときに
各3点の外積の総和は次の式になります。
sum = AB x BC + AC x CD + ,,, + AQ x RA
(ABは点Aから点Bへのベクトルです。)

セインさんのコードでひっかかったことは
外積の総和の絶対値が元の多角形の面積と異なってしまうことです。

素人考えなので間違ってたらごめんえ。
引用返信 編集キー/
■6226 / inTopicNo.9)  Re[7]: 時計回り、反時計回り判定
□投稿者/ Zee (10回)-(2007/08/06(Mon) 14:10:20)
Zee さんの Web サイト
No6224 (2リットル さん) に返信
> Jittaさんの言われていることと同じになりますが、
> 多角形を3点ごとに分解してベクトル外積の総和をとり、
> 総和が正ならば時計周り、負ならば逆周り、0ならば同一直線状というアプローチはどうでしょうか。
>
> 件の例でいうと
> vertex[0]を点A、vertex[1]を点B、、、vertex[16]を点Q, vertex[17]を点Rとしたときに
> 各3点の外積の総和は次の式になります。
> sum = AB x BC + AC x CD + ,,, + AQ x RA
> (ABは点Aから点Bへのベクトルです。)
>
> セインさんのコードでひっかかったことは
> 外積の総和の絶対値が元の多角形の面積と異なってしまうことです。

つうことでこんな多角形の面積計算公式があります。

A = 1/2 SUM(X2 - X1) (Y1 + Y2)

面積を出す公式ですが、
右周りで計算すると負の値に
左回りで計算すると正の値になります。
引用返信 編集キー/
■6230 / inTopicNo.10)  Re[8]: 時計回り、反時計回り判定
□投稿者/ y4yama (8回)-(2007/08/06(Mon) 15:14:52)
>時計回り、反時計回りの判定方法として、下記サイトの一番上に書いてある行列の計算から求めてみましたが、
これ、基本なんでしょうが面白いですね。ただし、3点に限る!ですね

別のアプローチですが、折れの向きを累計していけば、なんとかなりそうです
多角形の内角の和は、公式があります(略)外角の和は360度です
例として正6角形では、内角は120度ですね。外角は60度
どちらが内角か判らないから、進行方向の右/左の両側の折れの角度を累計(a1とa2)していきましょう
すると1周まわるときは、a1とa2の差はほぼ720度になります(外角の和の2倍)。小さいほう側が内角の方です
a1とa2の差が0に近いときは、8の字になってます。

これで、なんとかなりませんか
引用返信 編集キー/
■6231 / inTopicNo.11)  Re[9]: 時計回り、反時計回り判定
□投稿者/ セイン (16回)-(2007/08/06(Mon) 15:27:34)
セイン さんの Web サイト
みなさんありがとうございます。

前提条件なのですが、

1必ず時計回り、反時計回りに座標が並んでいます。
2お互いが重なることはありません。(8の字はありません)
3三日月状やアルファベットのHなどの凹み座標列は存在します。
4座標系はX右、Y上です。
引用返信 編集キー/
■6233 / inTopicNo.12)  Re[8]: 時計回り、反時計回り判定
□投稿者/ Zee (11回)-(2007/08/06(Mon) 15:47:52)
Zee さんの Web サイト
No6226 (Zee さん) に返信
使用している式自体、
三角形面積を利用したもんですからね。

お使いのデータは線になることが有ったり、
8の字になる部分があると面積では判断できませんよね。
(だからエラーが出るのだと思うのですが)

8の字になると面積の算出が逆になっていることが原因なんだと思います。

近傍に細かく動いた時の座標は飛ばすような仕組みにしたらどうでしょうか?
お使いのデータの規則性がわからないですね^^;
引用返信 編集キー/
■6234 / inTopicNo.13)  Re[10]: 時計回り、反時計回り判定
□投稿者/ セイン (17回)-(2007/08/06(Mon) 15:48:02)
セイン さんの Web サイト
■2リットル さんに返信
>sum = AB x BC + AC x CD + ,,, + AQ x RA
ごめんなさい>< … の途中の法則がわかりません(TT)

■Zee さんに返信
>A = 1/2 SUM(X2 - X1) (Y1 + Y2)

すごくシンプルでわかりやすそうな式ですね^^
肝心のこの計算式を展開したときの計算方法が・・・
SUM(X2 - X1) (Y1 + Y2)

ココの部分って、5点の場合だと
sum = ((x2 - x1) * (y1 + y2)) + ((x3 - x2) * (y2 + y3)) + ((x4 - x3) * (y3 + y4)) + ((x5 - x4) * (y4 + y5));

っていう計算ででるんでしたっけ?

■ y4yama さんに返信
前提条件をお伝えしてしてなく、ごめんなさい。
外角の和が常に360度っていうのは、凹み図では適応されないような気がします。
間違っていたらごめんなさい><





引用返信 編集キー/
■6236 / inTopicNo.14)  Re[10]: 時計回り、反時計回り判定
□投稿者/ Zee (12回)-(2007/08/06(Mon) 16:00:54)
Zee さんの Web サイト
No6231 (セイン さん) に返信
> 2お互いが重なることはありません。(8の字はありません)
ただ、同一の座標はありますね。
これを排除すると面積で計算できると思いますが?
引用返信 編集キー/
■6238 / inTopicNo.15)  Re[11]: 時計回り、反時計回り判定
□投稿者/ y4yama (9回)-(2007/08/06(Mon) 16:26:31)
ぐぐったら、
http://d.hatena.ne.jp/yaneurao/comment?date=20070113
2007-01-13 計算幾何 で、同じ話ですなぁ〜

>外角の和が常に360度っていうのは、凹み図では適応されないような気がします。
凹みでも、
>どちらが内角か判らないから、進行方向の右/左の両側の折れの角度を累計(a1とa2)していきましょう
>すると1周まわるときは、a1とa2の差はほぼ720度になります
は、満足されますよ。
デモ、2007-01-13 計算幾何 では、拒否されてましたが・・・
(折り返しの0度は無視すればいいんだけどネ)
引用返信 編集キー/
■6239 / inTopicNo.16)  Re[11]: 時計回り、反時計回り判定
□投稿者/ y4yama (10回)-(2007/08/06(Mon) 16:40:28)
No6236 (Zee さん) に返信
測量の常識!なんですね。外積=面積ですもんねぇ〜
この計算は、閉じた図形の外に原点がある場合にも
一般化されたものなのでしょうか?
閉じた図形の中に原点があるのなら、直感的によ〜く理解できるんですが・・・
引用返信 編集キー/
■6241 / inTopicNo.17)  Re[12]: 時計回り、反時計回り判定
□投稿者/ Zee (13回)-(2007/08/06(Mon) 18:30:10)
Zee さんの Web サイト
No6239 (y4yama さん) に返信
> ■No6236 (Zee さん) に返信
> この計算は、閉じた図形の外に原点がある場合にも
> 一般化されたものなのでしょうか?
> 閉じた図形の中に原点があるのなら、直感的によ〜く理解できるんですが・・・

この公式はですね
X軸から点までの角度と距離を行列式を使って計算する方法です。

多角形の面積をS
Siを線積
Liを原点からの距離
Aiを各点からのX軸からの角度(測量では方向角という)
とすると

原点と第1点と第2点でできる三角形は
S1 = 1/2 * L2{L1 * sin(A2 - A1)}
と言う風に
S2 = 1/2 * L3{L2 * sin(A3 - A2)}
...
Sn = 1/2 * Ln{Ln * sin(An - A(n-1))}
となり
S = S1 + S2 + ... + Sn
------------------------
  n
1/2 Σ | Xi Yi |
  i=1 | Xi+1 Yi+1 |
------------------------
となります(ただしN+1→1 とします)

だから右まわりが正、左回りが負で出てくるので、
足せば該当面積が残るってことです。
引用返信 編集キー/
■6242 / inTopicNo.18)  Re[13]: 時計回り、反時計回り判定
□投稿者/ Jitta (386回)-(2007/08/06(Mon) 18:47:09)
とりあえず、ぐぐる

キーワード
座標 判定 右回り


3つ目あたりのサイトで数学的な解説がされています。
引用返信 編集キー/
■6246 / inTopicNo.19)  Re[14]: 時計回り、反時計回り判定
□投稿者/ セイン (18回)-(2007/08/06(Mon) 20:56:59)
セイン さんの Web サイト
No6242 (Jitta さん) に返信
> とりあえず、ぐぐる
>
> キーワード
> 座標 判定 右回り
>
>
> 3つ目あたりのサイトで数学的な解説がされています。

明日中に研究して 解決済みマークつけられるようにがんばります^^
引用返信 編集キー/
■6254 / inTopicNo.20)  Re[13]: 時計回り、反時計回り判定
 
□投稿者/ Jitta (389回)-(2007/08/07(Tue) 07:54:12)
脱線:勉強会ネタ


No6241 (Zee さん) に返信

ドロー系のアプリでは、こういう計算って、必要なんですよ。
例えば、この計算式をコードに落とす、その考え方の過程ってことでも、十分コユイ…ある意味濃すぎる?…ネタになると思いますけど?!

続きは検討スレで
引用返信 編集キー/

次の20件>
トピック内ページ移動 / << 0 | 1 | 2 >>

管理者用

- Child Tree -