GPS＋はてなマップで陣取り

idea:5309 「GPS付携帯で送った画像の位置情報を連結して陣取り合戦」
原石アイディアはけーん。色々と仕様を考えるのが楽しいアイディアです。
昔あったゲーム QIX てのを思い出します。陣地から出て線で囲って新しい陣地を作るけど、南京玉すだれみたいなのが画面中を動いてて、描いてる途中の線に触れたらアウト。大きい陣地を取るにはリスクがありました。GPSでやる場合は途中で線を横切られたらやりなおし、って感じかな。これで出張で長ーーい陣地を作るのが難しくなる。
ちなみに地面でやるオリジナル版では、長い距離だと石を指で弾いて自陣にもどすのが難しくなるというリスクがある。
関係ないけど英語で形容詞 quixotic てのはよく使います。~~キホーティック~~クィクサーティクと読んで、ドン・キホーテのようなという意味です。
追記：QUIX でなくて QIXでした。ググるとgoogle:taito+QUIX] [google:taito+QIX 両方9000件くらい。q で始まる単語はほぼ例外なく次は u なので、無意識に間違えてるか、PACKMAN→PACMAN みたいに変えられたのかな。

GPS陣取り仕様書：

座標は最小分解能を1として整数で扱う
陣地は全て座標三つで表した三角形、およびそれらの和集合で表す
初期陣地は最小分解能程度の大きさの三角形。任意の空白領域に設定可能。(自宅付近を避けるなど個人情報保護の注意を喚起)
第一歩P1は自分の陣地内部になければならない
第二歩P2、第三歩P3は空白領域になければならない
線分P1P2, P2P3, P3P1 は全て他人の陣地を横切ってはいけない
第四歩はP1 の付近に戻って来て登録することで三角形P1P2P3 を自陣とする。
三角形P1P2P3 が他人の陣地を囲んでいてはいけない(前述の横切り判定では判定できないので別途判定)
前述の判定を自陣を構成する三角形についても行い、囲まれた分は判定に使わなくてよくなるのでリストから削除
陣地を作る途中で線分を横切られたらやりなおし

他人の領地を横切らない判定は、線分と線分が交わるかどうか判定するルーチンを使い、他人の領地を構成する全ての三角形について、三つの辺それぞれと自分の線分が交差しない、という条件で計算。実際は日本地図を四分木に分割して、各領域からそこに含まれる全ての三角形へのポインタを用意しておき検索を高速化する。作成中の線分の横切り判定も同様。
処理はFIFO で行う。四分木の最上位レベルあたりのブロックを使い領域を分割、それぞれの領域の処理を複数サーバに分散。複数領域にまたがるキューは複数サーバで同期して処理する。領域境界は山の中などを選びそういうキューをへらす。

具体的な処理

保持する変数

各プレイヤの陣地を表す三角形のリスト
各プレイヤの現在作成中の P1, P2, P3点

入って来るキューと処理

初期陣地作成
- 三角形のリストをしらべ、どれにも入ってないことを確認
  - TRUE→新たな三角形として登録
  - FALSE→できませんと返答
P1点作成
- 自陣を構成する三角形のどれかに入っていることを確認
  - TRUE→P1点登録
  - FALSE→できませんと返答
P1点キャンセル
P2点作成
- 他のプレイヤの陣地を構成する三角形のどれにも入ってない＆どの多陣の三角形の辺ともP1P2が交差しないことを確認
  - TRUE→P2点登録
  - FALSE→できませんと返答
- 他プレイヤxが作成中の線分P1P2についてしらべ、申請された線分P1P2 が交差していたらそのプレイヤのP2をキャンセルし通知。
- 各プレイヤが作成中の線分P2P3についてしらべ、申請された線分P1P2 が交差していたらそのプレイヤのP3をキャンセルし通知。
- 各プレイヤが作成中の線分P3P1についてしらべ、申請された線分P1P2 が交差していたらそのプレイヤのP3をキャンセルし通知。
P2点キャンセル
P3点作成
- 他のプレイヤの陣地を構成する三角形のどれにも入ってない＆どの多陣の三角形の辺ともP2P3が交差しない＆三角形P1P2P3 が他人の三角形を囲まないことを確認
  - TRUE→P3点登録
  - FALSE→できませんと返答
- 他プレイヤxが作成中の線分…P2作成と同じ処理
P1点到達
- 三角形P1P2P3 を登録、作成中線分リストからは外す

おまけ：線分(a1,b1)-(c1,d1) と線分(a2,b2)-(c2,d2) の交差判定を行うルーチン。

整数演算だけで出来ることに注意。

int seg_cross(int a1, int b1, int c1, int d1, // segment1 (a1,b1)-(c1,d1)
              int a2, int b2, int c2, int d2) // segment2 (a2,b2)-(c2,d2)
{
  int m11 = c1-a1;
  int m12 = a2-c2;
  int m21 = d1-b1;
  int m22 = d2-b2;

  int v1 = a2-a1;
  int v2 = b2-b1;
/* Solve (a1,b1)+s(c1-a1,d1-b1) = (a2,b2)+t(c2-a2,d2-b2) , that is,
 *       |m11 m12||s|=|v1|
 *       |m21 m22||t| |v2|
 */
  int det = m11*m22 - m21*m12;

  int s = m22*v1 -m12*v2;
  int t = -m21*v1 +m11*v2;

  if (s<0 || s>det) return 0;
  if (t<0 || t>det) return 0;
  return 1;
}

GPS陣取り仕様書：

具体的な処理

おまけ：線分(a1,b1)-(c1,d1) と 線分(a2,b2)-(c2,d2) の交差判定を行うルーチン。

おまけ：線分(a1,b1)-(c1,d1) と線分(a2,b2)-(c2,d2) の交差判定を行うルーチン。