Help us understand the problem. What is going on with this article?

Laravelで多角形の内外判定を行うアルゴリズムの実装案

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

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

Crossing Number Algorithm

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

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

Laravelでの実装

多角形の準備

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

今回は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に変換して,ユーザ情報を保存.そのまま内外判定の関数に渡してます.

引数の1つ目はlatとlng要素の配列.
引数の2つ目は判定したいエリアの配列.

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にも置いてます.

https://github.com/a-msy/laravel-utils/blob/master/Polygon.php

以上です.

a-msy
情報系大学生してます。 Laravelは友であり,敵. https://hiite.netと
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away