第55回　平面上における三角形の内側か外側かを外積で調べる

前回は特別編が加わったため、本編としては第53回「座標にもっとも近い線分上の点を内積で求める」の続きになる。ベクトルの内積のつぎは、外積を使ったサンプルの作成に移ろう。三角形で分割された領域があるとき、ある座標を与えて、それがどの三角形に含まれるのかを調べたい。また、座標などの多くの数値を扱うとき、スクリプトをどのように組立てたらよいのか、今回のお題で練習してみる。

平面上のふたつのベクトルの外積から互いの位置関係がわかる

三角形はもっとも単純な多角形だ。そのため、数学的に扱いやすい。たとえば、Graphics.drawTriangles()メソッドは、三角形に分けた領域をビットマップで塗った（第45回「領域をビットマップで塗る－テクスチャマッピング」以降参照⁠）⁠。すべての多角形は三角形に分けられ、自由な形状も三角形の集まりに近似できるからだ。

ベクトルの外積を使うと、座標が三角形の内側か外側かがわかる。今回のお題は、領域を三角形に分け、そのうちのどれがクリックされたのかを調べたい（図1⁠）⁠。

まず、外積の意味をおさらいしておこう（第52回「ベクトルの外積で回転の軸を定める」参照⁠）⁠。ベクトルAとBの外積A×Bは、つぎの第52回表1（再掲）のように定められる新たなベクトルだった。そして今回は、とくに「方向」に着目する。

外積の要素	求められた外積のベクトルとふたつのベクトルAとBとの関係
方向	角度	ふたつのベクトルAとBのどちらにも垂直
向き	ベクトルAからBに向かう回転で右ネジの進む向き
大きさ	\|A\|\|B\|sinθ

お題は、xy平面の三角形について考える。すると、xy平面上のベクトルの外積は、角度が必ずxy平面と垂直つまりz軸と平行になる。つぎにその方向は、ふたつのベクトルが時計回りの位置にあれば、右ネジの向きであるz軸の正方向だ。逆に、xy平面上のふたつのベクトルAとBの外積A×Bがz軸正方向だったとすると、ベクトルAの右側にBがある。

そこで、三角形の3辺を時計回りの向きのベクトルと考えよう。調べる座標が三角形の内側にある場合、1辺のベクトルとその始点からその座標へのベクトルとの外積を求める（図2⁠）⁠。3辺のベクトルすべてについて、調べる座標のベクトルが右側にあれば、すなわちその座標は三角形の内側になる。

では早速、ふたつのベクトルを与えて、右ネジの位置にあるかどうか調べる関数（xIsRight()）を定めよう。ベクトルはxy平面で考えるので、ふたつのPointオブジェクトにして引数に渡す。第1引数のベクトル（point0）の右に第2引数のベクトル（point1）があればtrue、そうでなければfalseを返す（スクリプト1⁠）⁠。

スクリプト1　ふたつのベクトルが右ネジの位置にあるかどうかを返す関数定義

function xIsRight(point0:Point, point1:Point):Boolean {
  var vector3D_0:Vector3D = new Vector3D(point0.x, point0.y, 0);
  var vector3D_1:Vector3D = new Vector3D(point1.x, point1.y, 0);
  var crossProduct:Vector3D = vector3D_0.crossProduct(vector3D_1);
  var bIsRight:Boolean = (crossProduct.z >= 0);
  return bIsRight;
}

あいにく、Pointクラスには外積を求めるメソッドはない。したがって、引数のPointオブジェクトからxy座標を取出して、Vector3Dオブジェクトとしてつくり直す。そのうえで、Vector3D.crossProduct()メソッドにより、ふたつのVector3Dオブジェクトの外積を求める。

前述のとおり、外積のベクトルが奥向き、つまりz座標が正ならふたつの引数のベクトルは右ネジの位置にある。その結果をブール（論理）値にして関数から返す。たとえば、座標（0, -1）のベクトルに対して座標（1, 0）は右側にある。したがって、このふたつをPointオブジェクトとして関数に渡せば、trueが返される。

var bResult:Boolean = xIsRight(new Point(0, -1), new Point(1, 0))
trace(bResult);   // 出力: true

この関数ができあがれば、今回のお題で使う数学の話はおしまいだ。これから先は、この関数をどう使うか、さらにはスクリプトをどう組立てるかが主題になる。そこで、今感じているかもしれないふたつの疑問に答えておく。

第1に、引数のPointをすぐにVector3Dオブジェクトに直すのなら、初めからVector3Dオブジェクトで渡すか、xy座標の数値を4つ引数にした方がよいのではないかということだ。まず、Vector3Dオブジェクトにすると、xy平面の座標にいちいちz座標として0を加えなければならない。それも手間だろう。つぎに、引数を単純な数値にするという手はありえる。しかし、数多くの座標を扱うときには、座標はひとつのオブジェクトの方が捉えやすい。

第2は、そもそもほしいのは、三角形の3頂点座標を定めて、ある座標がその内側かどうかを返す関数なのではないかということだ。確かに、そのような関数は必要だ。しかし、ひとつひとつの三角形やその頂点座標、さらには三角形の集まりをどう定めて、どう扱うのか、まだ決めていない。設計を先にきちんと考えなければならない。

必要な機能を関数として定める

初めにも述べたように、領域を三角形で分けるのはGraphics.drawTriangles()メソッドがテクスチャマッピングするやり方だ。そこで、クリックしたテクスチャの三角形にアウトラインを描いてみよう。第46回「分割した三角形にビットマップを変形して塗る」のスクリプト3が「三角形の頂点座標のひとつをマウスクリックした位置に動かしてテクスチャマッピング」した（第46回図3再掲⁠）⁠。このスクリプトが矩形を4つの三角形に分けて描く部分を使い回すことにしよう。

今回のお題は、クリックした座標が含まれる三角形を調べる。したがって、第46回スクリプト3から、イベントリスナーの登録とリスナー関数の定めは除く（スクリプト2⁠）⁠。マウスクリックのイベントリスナーは、これから改めて加えてゆく。なお、マッピングする[ライブラリ]のビットマップには、[クラス]としてImageという名前がつけてある（前出第46回「分割した三角形にビットマップを変形して塗る」参照⁠）⁠。

スクリプト2　矩形のテクスチャを4つの三角形に分けてマッピング

// フレームアクション
var nCenterX:Number = stage.stageWidth / 2;
var nCenterY:Number = stage.stageHeight / 2;
var mySprite:Sprite = new Sprite();
var myGraphics:Graphics = mySprite.graphics;
var myTexture:BitmapData = new Image();
var nHalfWidth:Number = myTexture.width / 2;
var nHalfHeight:Number = myTexture.height / 2;
var vertices:Vector.<Number> = new Vector.<Number>();
var indices:Vector.<int> = new Vector.<int>();
var uvData:Vector.<Number> = new Vector.<Number>();
mySprite.x = nCenterX;
mySprite.y = nCenterY;
vertices.push(0, 0);
vertices.push(-nHalfWidth, -nHalfHeight);
vertices.push(nHalfWidth, -nHalfHeight);
vertices.push(nHalfWidth, nHalfHeight);
vertices.push(-nHalfWidth, nHalfHeight);
indices.push(0, 1, 2);
indices.push(0, 2, 3);
indices.push(0, 3, 4);
indices.push(0, 4, 1);
uvData.push(0.5, 0.5);
uvData.push(0, 0);
uvData.push(1, 0);
uvData.push(1, 1);
uvData.push(0, 1);
myGraphics.beginBitmapFill(myTexture);
myGraphics.lineStyle(2, 0xFF0000);   // 確認用
myGraphics.drawTriangles(vertices, indices, uvData);
myGraphics.endFill();
addChild(mySprite);
/*
mySprite.addEventListener(MouseEvent.MOUSE_DOWN, xDraw);
function xDraw(eventObject:MouseEvent):void {
  vertices[0] = eventObject.localX;
  vertices[1] = eventObject.localY;
  myGraphics.clear();
  myGraphics.beginBitmapFill(myTexture);
  myGraphics.drawTriangles(vertices, indices, uvData);
  myGraphics.endFill();
}
*/

Graphics.drawTriangles()メソッドを用いているので、頂点座標と頂点番号がそれぞれVectorオブジェクトで変数（verticesとindices）に納められている。ここからいきなり、すべての頂点のベクトルを調べて、座標の含まれる三角形を取出そうとする人もあるだろう。できるなら、それでもよい。しかし、多くの人は混乱するか、途方に暮れるに違いない。

こういうときは、必要な機能をひとつひとつ小分けにして、部品を組上げるようにつくるとよい。部品は基本的に関数で考える。まず、ひとつの三角形が定められなければならない。これは頂点番号3つの組を、Vectorオブジェクトに取出せばよさそうだ。つぎに、すべての三角形を調べようとしたとき、予め三角形の個数を知りたい。

そこで、関数をふたつ定める。第1に、頂点番号のVectorオブジェクト（indices）を調べて、三角形がいくつあるかを返す関数（xGetNumTriangles()）だ。第2の関数（xGetTriangleAt()）は、何番目の三角形かという序数を引数に受取って、頂点番号3つが納められたVectorオブジェクト（intベース型）を返す。

// スクリプト2のフレームアクションに追加
mySprite.addEventListener(MouseEvent.MOUSE_DOWN, xDrawTriangle);
function xDrawTriangle(eventObject:MouseEvent):void {
  var nLength:uint = xGetNumTriangles();
  for (var i:uint = 0; i < nLength; i++) {
    var triangleIndices:Vector.<int> = xGetTriangleAt(i);
    trace(triangleIndices);
  }
}
function xGetNumTriangles():uint {
  var numTriangles:uint = uint(indices.length / 3);
  return numTriangles;
}
function xGetTriangleAt(nIndex:int):Vector.<int> {
  var nIndices:int = 3;
  var n:int = nIndex * nIndices;
  var triangleIndices:Vector.<int> = new Vector.<int>(nIndices);
  for (var i:uint = 0; i < nIndices; i++) {
    triangleIndices[i] = indices[uint(n + i)];
  }
  return triangleIndices;
}

そして、マウスクリックのイベントリスナーに関数(xDrawTriangle()）を加えた。インスタンスをクリックすると、取りあえずは動作確認としてテクスチャマッピングのための三角形がいくつあるかを調べて、forループですべての三角形の頂点番号の組を[出力]する（図3⁠）⁠。

あとは、三角形の3頂点番号から、それぞれの座標を返す関数があれば、前掲スクリプト1の座標位置を調べる関数（xIsRight()）につなげられそうだ。その関数（xGetVertices()）には、頂点番号の整数が納められたVectorオブジェクトを引数に渡す。すると、頂点座標のVectorオブジェクト（vertices）からその番号の座標を取出してPointオブジェクトにし、3頂点のPointエレメントが加えられたVectorオブジェクトで返す。

前掲スクリプト2に、すでに定めてあった関数（xGetNumTriangles()とxGetTriangleAt()）も含めて書き加えたのが、つぎのスクリプト3だ。インスタンスをクリックすると、すべての三角形の3頂点座標が[出力]される（図4⁠）⁠。

スクリプト3　テクスチャマッピングしたすべての三角形の頂点座標を調べる

// フレームアクション
var nCenterX:Number = stage.stageWidth / 2;
var nCenterY:Number = stage.stageHeight / 2;
var mySprite:Sprite = new Sprite();
var myGraphics:Graphics = mySprite.graphics;
var myTexture:BitmapData = new Image();
var nHalfWidth:Number = myTexture.width / 2;
var nHalfHeight:Number = myTexture.height / 2;
var vertices:Vector.<Number> = new Vector.<Number>();
var indices:Vector.<int> = new Vector.<int>();
var uvData:Vector.<Number> = new Vector.<Number>();
mySprite.x = nCenterX;
mySprite.y = nCenterY;
vertices.push(0, 0);
vertices.push(-nHalfWidth, -nHalfHeight);
vertices.push(nHalfWidth, -nHalfHeight);
vertices.push(nHalfWidth, nHalfHeight);
vertices.push(-nHalfWidth, nHalfHeight);
indices.push(0, 1, 2);
indices.push(0, 2, 3);
indices.push(0, 3, 4);
indices.push(0, 4, 1);
uvData.push(0.5, 0.5);
uvData.push(0, 0);
uvData.push(1, 0);
uvData.push(1, 1);
uvData.push(0, 1);
myGraphics.beginBitmapFill(myTexture);
myGraphics.lineStyle(2, 0xFF0000);   // 確認用
myGraphics.drawTriangles(vertices, indices, uvData);
myGraphics.endFill();
addChild(mySprite);
mySprite.addEventListener(MouseEvent.MOUSE_DOWN, xDrawTriangle);
function xDrawTriangle(eventObject:MouseEvent):void {
  var nLength:uint = xGetNumTriangles();
  for (var i:uint = 0; i < nLength; i++) {
    var triangleIndices:Vector.<int> = xGetTriangleAt(i);
    var triangleVertices:Vector.<Point> = xGetVertices(triangleIndices);
    trace(triangleVertices);
  }
}
function xGetNumTriangles():uint {
  var numTriangles:uint = uint(indices.length / 3);
  return numTriangles;
}
function xGetTriangleAt(nIndex:int):Vector.<int>  {
  var nIndices:int = 3;
  var n:int = nIndex * nIndices;
  var triangleIndices:Vector.<int> = new Vector.<int>(nIndices);
  for (var i:uint = 0; i < nIndices; i++) {
    triangleIndices[i] = indices[uint(n + i)];
  }
  return triangleIndices;
}
function xGetVertices(triangle:Vector.<int>):Vector.<Point> {
  var nLength:uint = triangle.length;
  var triangleVertices:Vector.<Point> = new Vector.<Point>(nLength);
  for (var i:uint = 0; i < nLength; i++) {
    var nIndex:int = triangle[i];
    var n:int = nIndex * 2;
    var myPoint:Point = new Point(vertices[n], vertices[int(n + 1)]);
    triangleVertices[i] = myPoint;
  }
  return triangleVertices;
}

クリックした三角形にアウトラインを描く

いよいよお題の本丸となる関数（xInsideTriangle()）を定める。三角形の3頂点座標のVectorオブジェクトと調べる座標のPointオブジェクトを引数に渡して、その座標が三角形の内側にあるかどうかブール値で返す。第1引数（triangle）のVectorオブジェクトには、前掲スクリプト3で加えた関数（xGetVertices()）の戻り値と同じく、3頂点の座標をPointエレメントとして納める。

function xInsideTriangle(triangle:Vector.<Point>, myPoint:Point):Boolean {
  var nLength:uint = triangle.length;
  var pointStart:Point = triangle[nLength - 1];
  for (var i:uint = 0; i < nLength; i++) {
    var pointEnd:Point = triangle[i];
    var point0:Point = pointEnd.subtract(pointStart);
    var point1:Point = myPoint.subtract(pointStart);
    var bIsRight:Boolean = xIsRight(point0, point1);
    if (!bIsRight) {
      return false;
    }
    pointStart = pointEnd;
  }
  return true;
}

三角形の辺のベクトルは、ふたつの頂点座標の引き算で求める。Pointクラスは引き算をPoint.subtract()メソッドで定めている。ベクトルには方向があり、終点の座標から始点の座標を差引く[1]⁠。

引かれるPointオブジェクト.subtract（引くPointオブジェクト）

forループの中で、三角形の3辺のベクトルをひとつずつとり上げ（point0⁠）⁠、同じ始点（pointStart）から調べる座標（myPoint）までのベクトル（point1）が右ネジの位置にあるかを前掲スクリプト1の関数（xIsRight()）で調べている。

調べる座標が右ネジの位置になければ、三角形の外だということなので、ループ処理を直ちに止め（returnステートメント）てfalseを返す。逆にループが最後まで中断されなければ、調べる座標が3辺に対して右ネジの位置、つまり三角形の内側になるので、戻り値をtrueとする。

つぎは、マウスクリックのリスナー関数（xDrawTriangle()）だ。引数に受取ったMouseEventオブジェクトのMouseEvent.localXとMouseEvent.localYプロパティから、クリックした座標が得られる。その座標をPointオブジェクト（pointMouse）にし、forループで取出した三角形の3頂点座標のVectorオブジェクト（triangleVertices）とともに引数として、先ほど定めた関数（xInsideTriangle）を呼出す。

function xDrawTriangle(eventObject:MouseEvent):void {
  var nX:Number = eventObject.localX;
  var nY:Number = eventObject.localY;
  var pointMouse:Point = new Point(nX, nY);
  var nLength:uint = xGetNumTriangles();
  for (var i:uint = 0; i < nLength; i++) {
    var triangleIndices:Vector.<int> = xGetTriangleAt(i);
    var triangleVertices:Vector.<Point> = xGetVertices(triangleIndices);
    var bInsideTriangle:Boolean = xInsideTriangle(triangleVertices, pointMouse);
    if (bInsideTriangle) {
      xDrawOutline(triangleVertices);   // 三角形のアウトラインを描く
      return;
    }
  }
}

各三角形は互いに重なり合うことはない前提なので、クリックした座標を含む三角形が見つかれば、returnステートメントで関数の処理を終える。その三角形にはアウトラインを描くことにし、そのための関数（xDrawOutline()）をつぎに定める。

var outlineSprite:Sprite = new Sprite();
var outlineGraphics:Graphics = outlineSprite.graphics;
mySprite.addChild(outlineSprite);
function xDrawOutline(triangleVertices:Vector.<Point>):void {
  var nLength:uint = triangleVertices.length;
  var pointLast:Point = triangleVertices[nLength - 1];
  outlineGraphics.clear();
  outlineGraphics.lineStyle(2, 0x0000FF);
  outlineGraphics.moveTo(pointLast.x, pointLast.y);
  for (var i:uint = 0; i < nLength; i++) {
    var myPoint:Point = triangleVertices[i];
    outlineGraphics.lineTo(myPoint.x, myPoint.y);
  }
}

アウトラインは別のSpriteインスタンス（outlineSprite）をつくって、そこに描くことにした。あとは、Graphicsクラスの描画メソッドを使って、三角形の3頂点座標を結んでいる[2]⁠。

以上のつくり込みをしたフレームアクション全体が、つぎのスクリプト4だ。関数の数は増え、ボリュームもそれなりに膨らんだ。しかし、必要な機能をひとつひとつ関数にして、部品を組上げるようにスクリプティングしたので、戸惑うことは少なかったのではないか。

スクリプト4　クリックした三角形にアウトラインを描く

// フレームアクション
var nCenterX:Number = stage.stageWidth / 2;
var nCenterY:Number = stage.stageHeight / 2;
var mySprite:Sprite = new Sprite();
var outlineSprite:Sprite = new Sprite();
var myGraphics:Graphics = mySprite.graphics;
var outlineGraphics:Graphics = outlineSprite.graphics;
var myTexture:BitmapData = new Image();
var nHalfWidth:Number = myTexture.width / 2;
var nHalfHeight:Number = myTexture.height / 2;
var vertices:Vector.<Number> = new Vector.<Number>();
var indices:Vector.<int> = new Vector.<int>();
var uvData:Vector.<Number> = new Vector.<Number>();
mySprite.x = nCenterX;
mySprite.y = nCenterY;
vertices.push(0, 0);
vertices.push(-nHalfWidth, -nHalfHeight);
vertices.push(nHalfWidth, -nHalfHeight);
vertices.push(nHalfWidth, nHalfHeight);
vertices.push(-nHalfWidth, nHalfHeight);
indices.push(0, 1, 2);
indices.push(0, 2, 3);
indices.push(0, 3, 4);
indices.push(0, 4, 1);
uvData.push(0.5, 0.5);
uvData.push(0, 0);
uvData.push(1, 0);
uvData.push(1, 1);
uvData.push(0, 1);
myGraphics.beginBitmapFill(myTexture);
myGraphics.drawTriangles(vertices, indices, uvData);
myGraphics.endFill();
addChild(mySprite);
mySprite.addChild(outlineSprite);
mySprite.addEventListener(MouseEvent.MOUSE_DOWN, xDrawTriangle);
function xDrawTriangle(eventObject:MouseEvent):void {
  var nX:Number = eventObject.localX;
  var nY:Number = eventObject.localY;
  var pointMouse:Point = new Point(nX, nY);
  var nLength:uint = xGetNumTriangles();
  for (var i:uint = 0; i < nLength; i++) {
    var triangleIndices:Vector.<int> = xGetTriangleAt(i);
    var triangleVertices:Vector.<Point> = xGetVertices(triangleIndices);
    var bInsideTriangle:Boolean = xInsideTriangle(triangleVertices, pointMouse);
    if (bInsideTriangle) {
      xDrawOutline(triangleVertices);
      return;
    }
  }
}
function xDrawOutline(triangleVertices:Vector.<Point>):void {
  var nLength:uint = triangleVertices.length;
  var pointLast:Point = triangleVertices[nLength - 1];
  outlineGraphics.clear();
  outlineGraphics.lineStyle(2, 0x0000FF);
  outlineGraphics.moveTo(pointLast.x, pointLast.y);
  for (var i:uint = 0; i < nLength; i++) {
    var myPoint:Point = triangleVertices[i];
    outlineGraphics.lineTo(myPoint.x, myPoint.y);
  }
}
function xGetNumTriangles():uint {
  var numTriangles:uint = uint(indices.length / 3);
  return numTriangles;
}
function xGetTriangleAt(nIndex:int):Vector.<int>  {
  var nIndices:int = 3;
  var n:int = nIndex * nIndices;
  var triangleIndices:Vector.<int> = new Vector.<int>(nIndices);
  for (var i:uint = 0; i < nIndices; i++) {
    triangleIndices[i] = indices[uint(n + i)];
  }
  return triangleIndices;
}
function xGetVertices(triangle:Vector.<int>):Vector.<Point> {
  var nLength:uint = triangle.length;
  var triangleVertices:Vector.<Point> = new Vector.<Point>(nLength);
  for (var i:uint = 0; i < nLength; i++) {
    var nIndex:int = triangle[i];
    var n:int = nIndex * 2;
    var myPoint:Point = new Point(vertices[n], vertices[int(n + 1)]);
    triangleVertices[i] = myPoint;
  }
  return triangleVertices;
}
function xInsideTriangle(triangle:Vector.<Point>, myPoint:Point):Boolean {
  var nLength:uint = triangle.length;
  var pointStart:Point = triangle[nLength - 1];
  for (var i:uint = 0; i < nLength; i++) {
    var pointEnd:Point = triangle[i];
    var point0:Point = pointEnd.subtract(pointStart);
    var point1:Point = myPoint.subtract(pointStart);
    var bIsRight:Boolean = xIsRight(point0, point1);
    if (!bIsRight) {
      return false;
    }
    pointStart = pointEnd;
  }
  return true;
}
function xIsRight(point0:Point, point1:Point):Boolean {
  var vector3D_0:Vector3D = new Vector3D(point0.x, point0.y,0);
  var vector3D_1:Vector3D = new Vector3D(point1.x, point1.y,0);
  var crossProduct:Vector3D = vector3D_0.crossProduct(vector3D_1);
  var bIsRight:Boolean = (crossProduct.z >= 0);
  return bIsRight;
}

[ムービープレビュー]で動きを確かめてみよう。テクスチャマッピングされたインスタンスをクリックすると、その座標を含む三角形にアウトラインが描かれる（図5⁠）⁠。

次回は、やはり外積を使って、もう少し見栄えのするサンプルをつくるつもりだ。

今回解説した次のサンプルファイルがダウンロードできます。

スクリプト2～4のサンプルファイル（CS5形式/約111KB）