第7回　多対多の関係を賢く扱う

図1●問題として与えられた四角形の初期状態の例

　私は待ち合わせが苦手です。人の顔を覚えるのがまったく不得意で，ましてや多くの人の中から見つけ出すとなるともうパニックになってしまうからです。そういうときに限って携帯電話を忘れていたりして…。

　「多量のデータの中から条件に合致するものを探索する」ことは本当に大変です。一番の問題は，時間がかかるところでしょう。1対多で検索する場合はともかく，多対多で探索するときには，アルゴリズムの優劣がモノをいいます。今回はその一例として「四角形の重なり具合を調べる方法」を取り上げ，ここからアルゴリズムの工夫の仕方について紹介します。

　今回紹介する方法は，シューティング・ゲームのプログラミングにおける「当たり判定」としてよく知られています。ゲーム・プログラミングの世界では，限られた時間の中で非常に多くの処理を実行しなければなりません。当たり判定もその一つで，例えば画面中に出ているプレーヤと多くの敵や弾などが，それぞれぶつかっていないかどうかを調べる必要があります。

　もちろん「多くのデータの中から一つのデータを探す」というのは，どんな局面でもよく使われるものです。顧客リストの中から複数の条件にマッチする人を探索する，多くのURLから目的のURLを探す，多数の接続先の中から目的の接続先を探す，などいっぱいあります。

四角形が重なる条件を水平方向と垂直方向で考える

　冒頭の問題に戻りましょう。四角形が重なるといっても，図2のようにいろいろあります。元からある四角形の頂点のいずれかが，新たに置いた四角形の内部にあれば，その四角形は重なっています（図2(a)）。でも図2(b)のように四角形が重なっているときは，頂点が含まれません。このため新たに置いた四角形の内部に頂点を持つ四角形だけを探せばいい，というわけにはいきません。

図2●四角形が重なると言ってもいろいろな場合がある。(a)のような場合は頂点が新たに置いた四角形の内部に含まれるが，(b)のような場合は含まれない

　水平方向の辺だけを取り出して調べて見ましょう（図3）。まずは，新たに置いた四角形に「重ならない」四角形を探す方法を考えます。新たに置いた四角形の左側の頂点（「L」とします）の左側に注目してください。すると，四角形の右側の頂点が，Lより左にある四角形は，重ならないことがわかります（図3の「重ならない四角形(その1)」）。

図3●水平方向だけに注目して，新たに置いた四角形に重なる条件を見つける

　それでは，右側の頂点がLより右にある四角形はすべて重なるかというとそんなことはありません。四角形の左側の頂点が，新たに置いた四角形の右側の頂点（「R」とします）よりも右にある場合は，やはり重なりません（図3の「重ならない四角形(その2)」）。したがって，右側の頂点がLよりも右にあり，左側の頂点がRよりも左にある四角形が，新たに置いた四角形に重なっている四角形ということになります。

　左から右に向けて値が大きくなるように座標軸をとってこの条件を表すと

Lの座標 ＜= 右側の頂点の座標

Rの座標 ＞= 左側の頂点の座標

となります＊2。垂直方向についても同様に考えます。新たに置いた四角形の上側の頂点を「T」，下側の頂点を「B」とすると，重なっている条件として

Tの座標 ＜= 下側の頂点の座標

Bの座標 ＞= 上側の頂点の座標

という式が得られます。これら四つの条件がすべて成立している四角形が，新たに置いた四角形に重なっている四角形というわけです。

　リスト1はこれを実装した例です。四角形は，左上の座標（left，top）と，四角形の幅と高さ（width，height）を示すt_rect型の構造体で表します。元からある四角形はt_rect型構造体を要素に持つ配列rectarrayに，新たに置く四角形は変数rectsrcで定義しています。rectsearch関数で，rectarrayの要素を一つずつ取り出し，rectsrcと比較します。四角形の右側の頂点のx座標と下側の頂点の y座標をそれぞれ，left＋width，top＋heightで表していることに注意してください。

  typedef struct {
    int left;
    int top;
    int width;
    int height;
  } t_rect;

  /* 元から置いてある四角形*/
  #define RECTARRAYLIMIT (32)
  t_rect rectarray[RECTARRAYLIMIT] = {
    {76, 3, 17, 31},
      …
    {32, 4, 7, 26},
  };

  /* 新たに置いた四角形*/
  t_rect rectsrc = {8, 16, 10, 12};

  /* 重なっているかどうかを調べる*/
  void rectsearch(void)
  {
    int i;
    for (i = 0; i < RECTARRAYLIMIT; i++) {
      if ((rectarray[i].left + rectarray[i].width >=
           rectsrc.left) &&
          (rectarray[i].left <=
           rectsrc.left + rectsrc.width) &&
          (rectarray[i].top + rectarray[i].height >=
           rectsrc.top) &&
          (rectarray[i].top <=
           rectsrc.top + rectsrc.height)) {
         /* 四角形が重なった*/
          …
    }
  }
}