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)

分類:[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 編集(投稿者)

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

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

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

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

ん？階段のように、曲がりながら直線状に並んだら、どう判定する？

引用返信 編集キー/

■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)

2007/08/02(Thu) 15:12:24 編集(投稿者)
2007/08/02(Thu) 15:12:20 編集(投稿者)

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

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

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

どんな方法なんですか！ぜひ教えてください。

引用返信 編集キー/

■6211 / inTopicNo.5)

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

▲▼■

□投稿者/ セイン (15回)-(2007/08/06(Mon) 09:35:25)

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

引き続き、時計回り、反時計回りの判定方法を募集しています。

引用返信 編集キー/

■6214 / inTopicNo.6)

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

▲▼■

□投稿者/ Zee (9回)-(2007/08/06(Mon) 11:44:23)

■No6211 (セインさん) に返信
測量屋の出番でしょうか？

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

座標系自体は２種類あるので
・数学系（Ｘが横軸）　例えば：画面内の座標
・測量系（Ｘが縦軸）　　　　：測量＾＾；
どちらを使うかによります。

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

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

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

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

Ｃで書けない私ですので、ヒントになればと＾＾；

引用返信 編集キー/

■6215 / inTopicNo.7)

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

▲▼■

□投稿者/ y4yama (7回)-(2007/08/06(Mon) 12:06:03)

前提条件をもっとはっきり知りたいものです・・・
８の字のようになることは？
２重にぐるぐる回って（ある交差をするが）しまうことは？
ほぼ直線上（続いた3点が１８０度または、折り返して０度に並ぶ）ことは？
時計方向とは、わかるんだけど、座標系は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)

■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点に限る！ですね

別のアプローチですが、折れの向きを累計していけば、なんとかなりそうです
多角形の内角の和は、公式があります（略）外角の和は３６０度です
例として正６角形では、内角は１２０度ですね。外角は６０度
どちらが内角か判らないから、進行方向の右／左の両側の折れの角度を累計（a1とa2）していきましょう
すると１周まわるときは、a1とa2の差はほぼ７２０度になります（外角の和の2倍）。小さいほう側が内角の方です
a1とa2の差が０に近いときは、８の字になってます。

これで、なんとかなりませんか

引用返信 編集キー/

■6231 / inTopicNo.11)

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

▲▼■

□投稿者/ セイン (16回)-(2007/08/06(Mon) 15:27:34)

みなさんありがとうございます。

前提条件なのですが、

１必ず時計回り、反時計回りに座標が並んでいます。
２お互いが重なることはありません。（８の字はありません）
３三日月状やアルファベットのHなどの凹み座標列は存在します。
４座標系はX右、Y上です。

引用返信 編集キー/

■6233 / inTopicNo.12)

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

▲▼■

□投稿者/ Zee (11回)-(2007/08/06(Mon) 15:47:52)

■No6226 (Zee さん) に返信
使用している式自体、
三角形面積を利用したもんですからね。

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

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

近傍に細かく動いた時の座標は飛ばすような仕組みにしたらどうでしょうか？
お使いのデータの規則性がわからないですね＾＾；

引用返信 編集キー/

■6234 / inTopicNo.13)

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

▲▼■

□投稿者/ セイン (17回)-(2007/08/06(Mon) 15:48:02)

■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)

■No6231 (セインさん) に返信
> ２お互いが重なることはありません。（８の字はありません）
ただ、同一の座標はありますね。
これを排除すると面積で計算できると思いますが？

引用返信 編集キー/

■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）していきましょう
＞すると１周まわるときは、a1とa2の差はほぼ７２０度になります
は、満足されますよ。
デモ、2007-01-13 計算幾何　では、拒否されてましたが・・・
（折り返しの０度は無視すればいいんだけどネ）

引用返信 編集キー/

■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)

■No6239 (y4yama さん) に返信
> ■No6236 (Zee さん) に返信
> この計算は、閉じた図形の外に原点がある場合にも
> 一般化されたものなのでしょうか？
> 閉じた図形の中に原点があるのなら、直感的によ～く理解できるんですが・・・

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

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

原点と第１点と第２点でできる三角形は
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)

とりあえず、ぐぐる

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

３つ目あたりのサイトで数学的な解説がされています。

引用返信 編集キー/

■6246 / inTopicNo.19)

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

▲▼■

□投稿者/ セイン (18回)-(2007/08/06(Mon) 20:56:59)