ユーザの住所が配達を承る範囲内かどうかを調べる必要があったので

実装を行っていましたところ，
https://www.nttpc.co.jp/technology/number_algorithm.html
にとてもよいアルゴリズムがあったのでこれをLaravel（PHP）で使えるようにしようと言うのが今回です．

Crossing Number Algorithm

調べたい範囲の多角形と，点を用意します．
点から真横に線を伸ばす．
多角形内に点があれば多角形の辺との交差数は奇数，外なら偶数になる

ざっとこんなイメージですがいいですかね．詳しくはサイト読んでください．
特殊ケースが４つぐらいあるので，そこは気をつけないといけません．

Laravelでの実装

多角形の準備

config\const.phpに判定したい多角形を準備します．
最初の座標と最後の座標は一緒にしてね．
下記の例だと，四角形だけど準備する点は５つです．

今回はGoogleMapAPI使うので，latとlngで区別します．latをy軸（縦方向），lngをx軸（横方向）として捉えてます．
lng,latの順のほうが良かったな．数学っぽいし．

config\const.php

    'DeliveryArea'=>[
        ["lat"=>1.0,"lng"=>0.0],
        ["lat"=>2.0,"lng"=>0.0],
        ["lat"=>2.0,"lng"=>1.0],
        ["lat"=>1.0,"lng"=>1.0],
        ["lat"=>1.0,"lng"=>0.0],
    ]

配達可能エリアとかそうそう変わらんだろってことで，constに指定．
config('const.DeliveryArea);だけで配列として使えるから便利だよね～．

ユーザの住所

これはGoogleMapAPIのGeoCodingを使います．詳しくは調べてネ．

言語を指定
APIキーを指定（極秘事項です．気をつけてね）
リクエスト出して，jsonをもらってくる．
よしなに返す．

ここでは，arrayにして同時に返してます．受け取るときは，list関数で受け取ればいいかなと．
ああああ　とか変な住所が入ってきたら，ZERO_RESULTが返ってくるらしいので，それで判定しました．

Polygon.php

    public static function geo($addr)
    {
        mb_language("Japanese"); //文字コードの設定
        mb_internal_encoding("UTF-8");

        $address = $addr;

        if (config('app.debug')) {
            //テスト環境, ローカル環境用の記述
            $myKey = "デバッグ用のキー";
        } else {
            $myKey = "本番環境用のキー";
        }

        $address = urlencode($address);

        $url = "https://maps.googleapis.com/maps/api/geocode/json?address=" . $address . "+CA&key=" . $myKey;

        $contents = file_get_contents($url);
        $jsonData = json_decode($contents, true);

        if($jsonData["status"]=="ZERO_RESULTS"){
            $lat = null;
            $lng = null;
        }else{
            $lat = $jsonData["results"][0]["geometry"]["location"]["lat"];
            $lng = $jsonData["results"][0]["geometry"]["location"]["lng"];
        }
        return array($lat, $lng);
    }

内外判定

まんまあったのをPHPの形式に直しただけです．あと，geo関数でnull返したので，それを扱うときの条件式を追加．
あと，判定の結果がどうなのかtrueとfalseで返してます．
交点の数が知りたい場合は，$cnを返せばOKでした．

Polygon.php

public static function isPointinPolygon($point,$PolygonArray){
        $cn = 0;
        if($point["lat"]==null){
            $point["lat"]=0.0;
        }
        if($point["lng"]==null){
            $point["lng"]=0.0;
        }
        for($i = 0; $i < count($PolygonArray) - 1; $i++){
            // 上向きの辺。点Pがy軸方向について、始点と終点の間にある。ただし、終点は含まない。(ルール1)
            if( (($PolygonArray[$i]["lat"] <= $point["lat"]) && ($PolygonArray[$i+1]["lat"] > $point["lat"]))
                // 下向きの辺。点Pがy軸方向について、始点と終点の間にある。ただし、始点は含まない。(ルール2)
                || (($PolygonArray[$i]["lat"] > $point["lat"]) && ($PolygonArray[$i+1]["lat"] <= $point["lat"])) ){
                // ルール1,ルール2を確認することで、ルール3も確認できている。
                // 辺は点pよりも右側にある。ただし、重ならない。(ルール4)
                // 辺が点pと同じ高さになる位置を特定し、その時のxの値と点pのxの値を比較する。
                $vt = ($point["lat"] - $PolygonArray[$i]["lat"]) / ($PolygonArray[$i+1]["lat"]- $PolygonArray[$i]["lat"]);
                if($point["lng"] < ($PolygonArray[$i]["lng"] + ($vt * ($PolygonArray[$i+1]["lng"] - $PolygonArray[$i]["lng"])))){
                    ++$cn;
                }
            }
        }
        if($cn%2 == 0){
            return false;//偶数点だと外部
        }
        else{
            return true;//奇数点だと内部
        }
    }

実際の使い方

考えられる状況は，ECサイトでのカート機能とかかと．
ユーザの住所みて，配送料に追加するとか，割引するとかかなと．

この場合は，latとlngをあとづけしたので既存ユーザのlatとlngのデータはnullになってる，けどaddrのデータはあるって人がいるのでこんなことしてるけど，普通は会員登録時とかマイページで情報編集したときにlatとlngを取る．

で，住所の文字列をgeo使ってlatとlngに変換して，ユーザ情報を保存．そのまま内外判定の関数に渡してます．

引数の１つ目はlatとlng要素の配列．
引数の２つ目は判定したいエリアの配列．

trueかfalse返すので自分の好きなように処理して，bladeにかえしてます．

CartController.php

<?php
use App\Utils\Polygon as Polygon;
//　useはよしなに

class CartController extends Controller
{
    public function indexcart()
    {
            $Areaadd = 0;
            $message = "";
            if( Auth::user()->lat == null || Auth::user()->lng == null){
                list($lat,$lng) = Polygon::geo(Auth::user()->addr);
                if($lat == null || $lng == null){
                    //取得してもなお不正な場合
                    $message = "ちゃんと住所入れてくれ";
                }else{
                    User::where('id',Auth::id())->update([
                       'lat'=>$lat,
                       'lng'=>$lng
                    ]);
                }
            }

            if(Polygon::isPointinPolygon(["lat"=>Auth::user()->lat,"lng"=>Auth::user()->lng],config('const.DeliveryArea')) == false)
            {//   lat=1.5 lng=0.5とかなら範囲内
                $Areaadd += 999999999;
                $message = "届けてやるぜ";
            }else{//   lat=0.0 lng=0.0は範囲外
                $message = "すまん遠すぎる";
            }

            return view('user.cart')->with('message',$message)->with('Areaadd',$Areaadd);
    }
}

Githubにも置いてます．

以上です．