12.18.2008

空間三點,是順時針排列還是逆時針排列

Robert 說,他有平面上的三點,依序列出,他要知道這樣列出是順時針還是逆時針..
他有記得小時候學過什麼右手法則,cross 之類的,拇指會是方向。
要 Google 什麼呢?

  • google 多邊 法向 -- 不是 (其實空間法向就對了)。
  • google 多邊 內積 -- 不是,這是求面積的。

內積?那外積是什麼呢?
  • google 外積 !!!
就是這個了,外積是求空間中兩向量的法線向量...


但是三點怎麼變成兩個向量呢?
三點 A, B, C 可以變成 (B-A), (C-B) 兩個向量。

所以答案就是:算 (B-A), (C-B) 這兩個向量的外積,如果是正,代表 A, B, C三點是逆時針。

這是國中數學吧....其實最後也不確定這是不是對的 :P


PART-II

Robert 又說...不行呀,不只3點,是很多點呀,要怎麼辦?
google 什麼呢?
  • Google polygon clockwise
一次就找到答案:
http://debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm

? 就是依順序每三點計算是順時針還是逆時針,多的就贏 ?

續:

似乎是不行,Robert 遇到一個 算錯的 case :

{ 262952,2774455 }, // 0
{ 262955,2774449 }, // 1
{ 262957,2774437 }, // 2
{ 262964,2774419 }, // 3
{ 262970,2774410 }, // 4
{ 262977,2774403 }, // 5
{ 262986,2774399 }, // 6
{ 263006,2774395 }, // 7
{ 263019,2774393 }, // 8
{ 263046,2774385 }, // 9
{ 263065,2774382 }, // 10
{ 263078,2774382 }, // 11
{ 263109,2774387 }, // 12
{ 263126,2774385 }, // 13
{ 263132,2774385 }, // 14
{ 263140,2774382 }, // 15
{ 263148,2774379 }, // 16
{ 263168,2774369 }, // 17
{ 263177,2774367 }, // 18
{ 263185,2774369 }, // 19
{ 263189,2774372 }, // 20
{ 263193,2774378 }, // 21
{ 263198,2774377 }, // 22
{ 263201,2774376 }, // 23
{ 263205,2774369 }, // 24
{ 263209,2774366 }, // 25
{ 263215,2774364 }, // 26
{ 263223,2774363 }, // 27
{ 263234,2774358 }, // 28
{ 263248,2774352 }, // 29
{ 263259,2774342 }, // 30
{ 263273,2774326 }, // 31
{ 263286,2774307 }, // 32
{ 263296,2774285 }, // 33
{ 263302,2774270 }, // 34
{ 263306,2774255 }, // 35
{ 263311,2774242 }, // 36
{ 263319,2774229 }, // 37
{ 263326,2774221 }, // 38
{ 263337,2774211 }, // 39
{ 263344,2774206 }, // 40
{ 263348,2774199 }, // 41
{ 263351,2774190 }, // 42
{ 263351,2774179 }, // 43
{ 263350,2774170 }, // 44
{ 263357,2774124 }, // 45
{ 263357,2774099 }, // 46
{ 263357,2774084 }, // 47
{ 263359,2774077 }, // 48
{ 263353,2774079 }, // 49
{ 263352,2774086 }, // 50
{ 263352,2774099 }, // 51
{ 263352,2774124 }, // 52
{ 263345,2774170 }, // 53
{ 263346,2774179 }, // 54
{ 263346,2774189 }, // 55
{ 263344,2774197 }, // 56
{ 263341,2774204 }, // 57
{ 263335,2774210 }, // 58
{ 263321,2774220 }, // 59
{ 263314,2774228 }, // 60
{ 263307,2774238 }, // 61
{ 263304,2774247 }, // 62
{ 263299,2774266 }, // 63
{ 263296,2774278 }, // 64
{ 263291,2774290 }, // 65
{ 263284,2774303 }, // 66
{ 263278,2774312 }, // 67
{ 263271,2774321 }, // 68
{ 263256,2774337 }, // 69
{ 263241,2774349 }, // 70
{ 263227,2774357 }, // 71
{ 263217,2774362 }, // 72
{ 263208,2774362 }, // 73
{ 263199,2774362 }, // 74
{ 263195,2774359 }, // 75
{ 263181,2774343 }, // 76
{ 263169,2774329 }, // 77
{ 263158,2774316 }, // 78
{ 263151,2774306 }, // 79
{ 263143,2774290 }, // 80
{ 263132,2774267 }, // 81
{ 263125,2774258 }, // 82
{ 263121,2774255 }, // 83
{ 263114,2774252 }, // 84
{ 263104,2774250 }, // 85
{ 263092,2774249 }, // 86
{ 263075,2774252 }, // 87
{ 263069,2774251 }, // 88
{ 263059,2774247 }, // 89
{ 263025,2774233 }, // 90
{ 263022,2774230 }, // 91
{ 263022,2774225 }, // 92
{ 263023,2774219 }, // 93
{ 263031,2774202 }, // 94
{ 263048,2774179 }, // 95
{ 263068,2774151 }, // 96
{ 263071,2774146 }, // 97
{ 263078,2774128 }, // 98
{ 263084,2774107 }, // 99
{ 263085,2774099 }, // 100
{ 263090,2774080 }, // 101
{ 263085,2774079 }, // 102
{ 263084,2774086 }, // 103
{ 263081,2774099 }, // 104
{ 263079,2774106 }, // 105
{ 263075,2774122 }, // 106
{ 263067,2774142 }, // 107
{ 263057,2774160 }, // 108
{ 263040,2774181 }, // 109
{ 263029,2774197 }, // 110
{ 263020,2774213 }, // 111
{ 263016,2774225 }, // 112
{ 263015,2774231 }, // 113
{ 263017,2774235 }, // 114
{ 263020,2774238 }, // 115
{ 263033,2774241 }, // 116
{ 263044,2774246 }, // 117
{ 263055,2774251 }, // 118
{ 263066,2774257 }, // 119
{ 263084,2774254 }, // 120
{ 263098,2774253 }, // 121
{ 263107,2774254 }, // 122
{ 263119,2774260 }, // 123
{ 263127,2774268 }, // 124
{ 263132,2774280 }, // 125
{ 263139,2774300 }, // 126
{ 263144,2774309 }, // 127
{ 263163,2774329 }, // 128
{ 263168,2774337 }, // 129
{ 263168,2774345 }, // 130
{ 263168,2774352 }, // 131
{ 263164,2774359 }, // 132
{ 263157,2774365 }, // 133
{ 263143,2774374 }, // 134
{ 263134,2774379 }, // 135
{ 263122,2774382 }, // 136
{ 263115,2774382 }, // 137
{ 263108,2774381 }, // 138
{ 263090,2774376 }, // 139
{ 263079,2774375 }, // 140
{ 263063,2774377 }, // 141
{ 263047,2774381 }, // 142
{ 263022,2774381 }, // 143
{ 263004,2774386 }, // 144
{ 262985,2774391 }, // 145
{ 262976,2774396 }, // 146
{ 262967,2774403 }, // 147
{ 262960,2774412 }, // 148
{ 262955,2774423 }, // 149
{ 262951,2774429 }, // 150
{ 262940,2774441 }, // 151
{ 262938,2774447 }, // 152
{ 262936,2774452 }, // 153
{ 262935,2774455 }, // 154

沒有留言: