Phaser 3 : 凹面の当たり判定を自動で生成してみる① 閉路を検出

Phaser3ではメッシュを扱えるようになりましたが、画像からメッシュを自動で生成してくれるような機能がありません。
Unityではスプライトから自動で当たり判定や物理ボディを作成してくれるアセットが充実していますが、Phaserにはそれにあたるようなライブラリやプラグインもないようです。
ですが自分で用意した頂点に当たり判定をつける機能はあるので、スプライトから凹面メッシュを自動で生成するような仕組みを作ってみたいと思います。

閉路の検出

まずは点の集まりをつなげて多角形を作るところから始めてみたいと思います。
こちら計算幾何の基礎と領域探索 - RAMBOのページを参考に閉路の検出を行ってみたいと思います。
参考ページによると、y軸座標が最も小さい点を基準点とし、基準点から各点への角度と基準点の水平線のなす角度が小さい順にソートした点を結べば閉路が得られる、とのことです。
まずはPhaser.Math.Betweenを使って適当に点を配置します。

//適当に点を配置
for (let i = 0; i < 20; i++) {
    let point = new Phaser.Math.Vector2(Phaser.Math.Between(100, 400), Phaser.Math.Between(100, 400))
    this.points.push(point);
    this.graphics.fillPointShape(point,5);
}

次にsortを用いて基準点を設定します。

//基準点を検出
let origin = this.points.sort(function(a, b) {
    if (a.y > b.y) {
        return 1;
    } else if (b.y > a.y) {
        return  -1;
    }
}).shift();

次にsortを用いて基準点と各点との角度大きさ順に点を並べ替えます。
並べ替えた配列の先頭に基準点を戻します。

//基準点と各点を結ぶ直線と基準点の水平線との角度でソート
this.points.sort(function (p1, p2) {

    let dx1 = p1.x - origin.x;
    let dy1 = p1.y - origin.y;
    let dx2 = p2.x - origin.x;
    let dy2 = p2.y - origin.y;

    let a1 = Math.atan2(dy1, dx1);
    let a2 = Math.atan2(dy2, dx2);

    if (a1 > a2) {
        return 1;
    } else {
        return -1;
    }

});

最後に経路を描画します。

//基準点を配列に戻す
this.points.unshift(origin);

//パスを描く
for (let i = 0; i < this.points.length - 1; i++) {
    let path = new Phaser.Curves.Line([this.points[i].x,this.points[i].y,this.points[i+1].x,this.points[i+1].y])
    path.draw(this.graphics)
}

//始点と終点を結ぶ
let path = new Phaser.Curves.Line([this.points[this.points.length - 1].x, this.points[this.points.length - 1].y, origin.x, origin.y])

上記の実行結果がこちらです。

基準点から各点への直線を引いてみると三角形が作れるので、これを頂点として使用すれば凹面の当たり判定も作ることができそうです。

あとはスプライトの境界を取得すればスプライトから当たり判定を生成できそう…なのですが、この境界の判定はconvex fullと呼ばれる難しい問題のようです。
こちら[algorithm] 2D凹面を生成する効率的なアルゴリズムはありますか？ [math] [geometry] - CODE Q&A 問題解決のページにはまず辺の長さの限界を設定し、多角形をドロネー分割し辺の長さの限界以上になったものをはじく、というやり方が紹介されています。
次の記事ではドロネー分割について触れてみたいと思います。
今回のソースはこちらです。

/// <reference path="../app.ts" />

namespace MyGame {
    
    interface XY {
        x: number;
        y: number;
    }

    export class MyScene1 extends Phaser.Scene {

        //グラフィックオブジェクトを用意
        public player: Phaser.GameObjects.Image;
        public beamGroup: Phaser.GameObjects.Group;

        public graphics: Phaser.GameObjects.Graphics;
        public points: Phaser.Math.Vector2[]=[];
        public closepath: Phaser.Math.Vector2[] = [];

        constructor() {
            super({ key: 'MyScene1', active: false });
        }

        preload() {
        }

        create() {

            this.cameras.main.setBackgroundColor(0xffffff);

            this.graphics = this.add.graphics();
            this.graphics.fillStyle(0x000000);

            //適当に点を配置
            for (let i = 0; i < 10; i++) {
                let point = new Phaser.Math.Vector2(Phaser.Math.Between(100, 400), Phaser.Math.Between(100, 400))
                this.points.push(point);
                this.graphics.fillPointShape(point,5);
            }

            //基準点を検出
            let origin = this.points.sort(function(a, b) {
                if (a.y > b.y) {
                    return 1;
                } else if (b.y > a.y) {
                    return  -1;
                }
            }).shift();
            

            //基準点と各点を結ぶ直線と基準点の水平線との角度でソート
            this.points.sort(function (p1, p2) {

                let dx1 = p1.x - origin.x;
                let dy1 = p1.y - origin.y;
                let dx2 = p2.x - origin.x;
                let dy2 = p2.y - origin.y;

                let a1 = Math.atan2(dy1, dx1);
                let a2 = Math.atan2(dy2, dx2);

                if (a1 > a2) {
                    return 1;
                } else {
                    return -1;
                }

            });

            //基準点を配列に戻す
            this.points.unshift(origin);

            //パスを描く
            for (let i = 0; i < this.points.length - 1; i++) {
                this.graphics.lineStyle(1,0x000000);
                let path = new Phaser.Curves.Line([this.points[i].x,this.points[i].y,this.points[i+1].x,this.points[i+1].y])
                path.draw(this.graphics)

                this.graphics.lineStyle(1,0x888888);
                let path2 = new Phaser.Curves.Line([this.points[0].x, this.points[0].y, this.points[i+1].x, this.points[i+1].y])
                path2.draw(this.graphics)

            }

            //始点と終点を結ぶ
            let path = new Phaser.Curves.Line([this.points[this.points.length - 1].x, this.points[this.points.length - 1].y, origin.x, origin.y])

            path.draw(this.graphics);
        }

        update() {
        }
    }
}