ご存知のように、最近、モバイルプラットフォーム向けのゲームを開発するための技術は非常に急速に開発されています。 ゲームはさまざまなエンジンと言語で書かれています。この記事では、特定の言語/エンジンが優れているのか、劣っているのかについては説明しません（そうではありませんか？）。 開発者は、新しく興味深く便利なゲームコントロールを考案しようとしています。 プレイヤーとして、私はゲームで幾何学的要素を使用するのが大好きです。 たとえば、モバイルデバイス用のゲームJuggernautなど。
描画された2D形状を決定するためのアルゴリズムについて説明します。 エンジンのバージョンをActionScript 3.0で作成しました。 必要に応じて（およびジオメトリの基本的な知識があれば）、他の任意のものに実装できます。
そのため、既存の図との類似性の割合を手描きの数字で決定する必要があります。
基本的なジオメトリ
アルゴリズムを実装するには、平面上の基本的なジオメトリ式が必要です。
[F1]セクションの長さ：
len = sqrt((x2-x1)^2 + (y2-y1)^2);
[F2]方向ベクトルとライン法線：
// directX = x2-x1; directY = y2-y1; // normaleX = -directY; normaleY = directX;
[F3]平面内の線の方程式Ax + By + C = 0
線の方程式から係数A、B、Cを取得するには、この線の2つの点を知って、これを行うことができます。
A = -normaleX; B = -normaleY; C = -A*x1 - B*y1;
[F4]ポイントの位置は比較的まっすぐです。
数式Ax + By + Cが値を代入するときにゼロより大きい値を与える場合、ポイントは線の上にあると想定します。 値がゼロの場合、ポイントはこのラインに属します。 線の最初の点が画面の左側にあり、2番目の点が右にあることを想像してください。したがって、この線の上（画面の上部）にあるすべての点は、方程式の線を置き換えるときに正の値を与えます。 最初の（初期）ポイントと2番目の（最終）ポイントの位置を理解することは非常に重要です：ポイントp = {x、y}およびq = {x、y}があり、式を使用して方向（および法線ベクトル）を計算する場合：
directX = qx-px; directY = qy-py;
、その後、最初の（初期）ポイントはpになり、2番目の（最終）ポイントはqになります。
[F5]ポイントをセグメントに所属させる
点oは、これらの点を通る線上にあり、セグメントの2つの与えられた点の間にある場合、セグメントpqに属します。 メンバーシップアルゴリズムは次のとおりです。
-ポイントが線上にあるかどうかを判断する（ [F4] ）
-セグメント（ [F4] ） opおよびoqの長さを見つけます。これらの値の少なくとも1つがセグメントpqの長さより大きい場合、点oはセグメントpqの内側にありません
[F6]無限に長い線の交点
// , l1 = {p1,p2}; l2 = {p1,p2}; // d = (l2.p2.y-l2.p1.y)*(l1.p2.x-l1.p1._x) - (l2.p2.x-l2.p1.x)*(l1.p2.y-l1.p1.y); a = (l2.p2.x-l2.p1.x)*(l1.p1.y-l2.p1._y) - (l2.p2.y-l2.p1.y)*(l1.p1.x-l2.p1.x) // x0 = l1.p1.x + a*(l1.p2.x-l1.p1.x)/d y0 = l1.p1.y + a*(l1.p2.y-l1.p1.y)/d
d = 0の場合、線は平行であることに注意してください。
[F7] 2つのセグメントの交点。 無限線と線分との交点。
2つの終了セグメントまたは無限線と終了セグメントの交差がチェックされる場合、最初に2つの無限線の交差ポイントを決定し（ [F6] ）、このポイントがすべての関連セグメントに属するかどうかをチェックする必要があります（ [F5] ）。
三角形-すべての基礎としての基本多角形
ご存知のように、三角形は最も単純なポリゴンです。 ポリゴンの多くの計算は三角形に関連付けられているため、それらを操作するためのいくつかの式を示します。
[F8]三角形の幾何学的中心
三角形（またはCentroid ）の中心は、三角形のポイントの座標の算術平均です。 次の式で決定されます。
x0 = (a.x+b.x+cx)/3; y0 = (a.y+b.y+cy)/3;
[F9]三角形の面積
三角形の点の座標のみがわかっている場合、2つの辺の長さにこれらの辺間の角度のサインを掛けることで、その面積を決定できます。
[F10]平面上のポリゴン
平面内のポリゴンPは、一連の頂点によって定義されます： v1、v2、...、vn 、ここでnは頂点の数です。 ポリゴンには、隣接する頂点を接続することで形成されるエッジがあります： e1 = {v1、v2}、e2 = {v2、v3}、...、en = {vn、v1} 。
[F11]ポリゴン境界ボックス
境界ボックスは、 bounds = {x、y、width、height}オブジェクトによって定義されます。ここで、xとyはポリゴンの頂点の最小座標であり、幅と高さは頂点の最大座標と最小座標の差です。
[F12]ポリゴンセンター
中心は通常、異なるエンティティを意味します。たとえば、ポイントシステムの中心やエリア上の重心などです。次のアルゴリズムで計算される重心を使用します。 ポリゴンを三角形に分割する必要がありますが、何であれ、頂点を順番に使用するだけです。 三角形の中心とその面積の積の合計を求め、この量をポリゴンの総面積で割ります。 ポリゴンの面積は、三角形の面積の合計として計算されます。
// var triangles:Array = ... ; // var centerX:Number = 0; var centerY:Number = 0; // var polygonSquare:Number = 0; // for (i=0; i<triangles.length; i++) { var triangle = triangles[i]; centerX += triangle.center.x*triangle.square; centerY += triangle.center.y*triangle.square; polygonSquare += triangle.square; } centerX /= polygonSquare; centerY /= polygonSquare;
[F13]ポリゴンを基準にしたポイントの位置
時計回りに移動したときに、このポイントがすべてのエッジに対して「ボトム」である場合、ポイントはポリゴンの内側に配置されます。 線に対する点の位置は、式F4によって決定できます。 ポイントがすべてのエッジに対して「上」にある場合、ポリゴンの外側にあります
[F14]無限の線と多角形の交差
線lと多角形Pの交点を決定するには、式[F7]を使用して、線lとすべてのセグメントe1、e2 ...との交点をすべて見つける必要があります。
形状の類似性を判断する
では、入り口には何がありますか？ 元の図面-頂点のセットv1、v2、...、vnで定義されたテンプレートポリゴンがあり、描画プロセス中に受け取ったポイントのセットで構成される描画ポリゴンがあります。 比較を開始する前に、描画ポリゴンをテンプレートポリゴンに「縮小」する必要があります。 つまり テンプレートを使用して、ポリゴンの中心が一致し、描画ポリゴンがバウンディングボックス（bounds.widthとbounds.height）の最大類似寸法となるように、圧縮（スケール）と変位（変換）の変換を適用する必要があります。
ポリゴン削減アルゴリズム：
// var template = ... ; // var draw = ... ; // var scaleW:Number = template.bounds.width/draw.bounds.width; // var scaleH:Number = template.bounds.height/draw.bounds.height; // var scale:Number = (scaleW+scaleH)/2; // draw.matrixScale(scale); // // X var dx:Number = draw.centerWeight.x-template.centerWeight.x; // Y var dy:Number = draw.centerWeight.y-template.centerWeight.y; // draw.matrixTranslate(dx, dy);
centerWeightはポリゴンの重心であることに注意してください。
2つのアルゴリズムによって図形の類似性を判断できます。それらをRadialとDimensionalと呼びましょう。 それらを分解してみましょう。
ラジアルアルゴリズム
描画されたポリゴンをテンプレートに合わせたら、それらの比較を開始できます。 ラジアル法の本質は次のとおりです。 中心からレイをリリースし、このレイとポリゴンの交点を見つけます。 交点間の距離を見つけて覚えておいてください。 次に、特定の角度ステップで新しいレイを描画し、交点間の距離を見つけます。 最後に得られた交差点間の距離を加算して、特定の値を取得します。 この値が低いほど、描画された図がテンプレートに近くなります。 画像に例を示します。
放出される光線が多いほど、検証はより正確になります。 エラーを設定することもできます。たとえば、ビームとポリゴンの交差点間の平均長さが、テンプレートポリゴンの境界ボックスの幅/高さ（または算術平均幅と高さ）とどれだけ異なるかを設定できます。 フラッシュドライブでアルゴリズムの動作を確認できます。
全体的なアルゴリズム
全体的なアルゴリズムは、2つの境界ポリゴンを定義し、その中に描画されたポリゴンのすべてのポイントを配置することです。 つまり テンプレートの2つのクローンを作成し、それらに圧縮変換を適用する必要があります。1つは小さい側に、もう1つは大きい側に適用します。 次に、大きいポリゴンの内側と小さいポリゴンの外側にあるすべてのポイントをチェックします。その後、この領域に入らなかったポイントの割合を判断できます。 しきい値のパーセンテージは、描画された図の精度のレベルです。
UPD：次元アルゴリズムの例はこちらです。
参照資料
ActionScriptでの実装に使用されるライブラリ： FPGeometry2d.swcおよびFPGeomControl.swc