폴리곤 좌표와 검색할 좌표를 비교하여 해당 좌표가 폴리곤안에 들어와있는지 확인하는 PHP & Javascript함수 (point-in-polygon 알고리즘)

다각형의 폴리곤에서 좌표가 폴리곤안에 들어가 있는지 아닌지 판단한다.

 

섹터를 나누는 기능을 개발하기 위해서는 섹터의 영역인 폴리곤과 좌표계를 비교하는 개발소요가 있었다.

 

 

 

예를 들면 이것 처럼....

기본적으로 Tmap이나 Naver Map에서는 설정한 폴리곤영역에서 사전에 맵에 띄워둔 마커가 폴리곤에 포함되어있는지 확인하는 API가 존재했지만,이 과정은 언제까지나 매번 API를 통해 호출해야되는 부담이 있었고,

마커가 수천개가 되는 상황에서는 조금더 섹시한 방법을 찾기로 했다.

 

 

방법은 크게 두가지가 있었다.

 

---

 

 

1. 데이터베이스를 활용하는 방법

MySQL에 Polygon형태의 데이터를 저장해두고

MBRContains 연산자를 이용하여 SELECT를 쿼리하는 방법이다.

 

2. 데이터베이스를 활용하지 않는 방법

데이터베이스의 좌표계를 불러온뒤, 자료구조로 만들어두고 애플리케이션(PHP따위등)에서 처리하는 방법이다.

 

 

---

 

우리 서비스의 경우, 수천대의 차량에 대한 위도/경도 데이터가 매 Second마다 Insert되고,

다른 연계서비스에서도 데이터베이스를 참조하느라 데이터베이스 부하가 상당했다.

 

무엇보다 회사내에서 사용하고 있는 SELECT 쿼리를 처리하는 DBMS ORM에 대해

MBRContains 연산자 기능이 추가되었어야 했다.

결국 후자의 방법으로 데이터베이스의 부하를 최소화하면서 문제를 해결하게 되었다.

 

대충 이런식으로 사용할 수 있다.

 

이렇게 구현하는 이유는 서비스 규모가 커지면서 가급적 SQL으로 모든것을 처리하기 보다는

참조할 데이터의 특정영역만 가져온상태에서 프로그램 로직단에서

처리하는게 경험상 더 빠르게 처리되고 부하량도 상대적으로 적었다.

(데이터베이스에게 어떤 연산을 시키면 안된다.... ㅠㅠ)

 

 

무엇보다 단순 로직만으로 개발하면 JS를 사용하는 Front-end에서도 처리할 수 있음!

---

 

폴리곤에 대한 좌표계 검증에 대한 로직은 앞으로도 많이 사용되어야 함으로

별도의 함수로 만들어두었고, 사용방법은 아래와 같다.

(기본적인 배열에 대한 검증과 데이터형 검사도 함수기능내 포함시켜두었음.)

//폴리곤 좌표계
$polygon_array =  array();
$polygon_array[0] = array('37.53552567043231', 126.95672035217325);
$polygon_array[1] = array('37.52790237570185', 126.9499397277836);
$polygon_array[2] = array(37.51714676004277, 126.96959495544473);
$polygon_array[4] = array(37.52980827243268, 126.99191093444864); //key 건너뜀
$polygon_array[5] = array(37.52980827243268, 126.99191093444864); //동일한 좌표
$polygon_array[6] = array(37.537295252413486, 126.96993827819864);
$polygon_array[7] = array(37.53552567043231, '126.95672035217325');

//검색할 대상의 좌표들
$points_array = array();
$points_array['가락시장역'] = array(37.493515041951, 127.118736639621);
$points_array['래미안용산'] = array(37.529489434399, 126.967329235710);
$points_array['겹침'] = array('37.51714676004277', 126.96959495544473);

//함수실행
$array = polygon_point_check($polygon_array, $points_array);
if(is_array($array)){
	//성공하면 무조건 배열이 나온다.
    print_r($array['inside']);
    echo '<br />';
    print_r($array['outside']);
}else{
	//실패하면 무조건 String이 반환된다.
    echo 'error : '.$array;
}

위 코드대로라면, 결과는 다음과 같이 나온다.

inside, outside 배열로 구분할 수 있음.

 

 

$polygon_array = array();
$polygon_array[] = array("37.530676119986", "126.96689128876");
$polygon_array[] = array("37.529961422735", "126.96521759033");
$polygon_array[] = array("37.528225700899", "126.96783542633");
$polygon_array[] = array("37.529518987671", "126.96946620941");
$polygon_array[] = array("37.530676119986", "126.96689128876");

$points_array = array();
$points_array['래미안용산더센트럴'] = array('37.529489434399','126.967329235710'); //래미안용산더센트럴 inside
$points_array['가락시장역'] = array(37.493515041951,127.118736639621); //가락시장역
$points_array['강동역1번출구'] = array(37.536967683151, 127.034701082600); //강동역1번출구
$points_array['경기대수원캠퍼스'] = array(37.303044086800,127.034701082600); //경기대수원캠퍼스

또다른 예시데이터.....

 

 

 

함수의 코드는 다음과 같다.

다른 사람들이 작성한 코드들도 많이 서칭해봤는데 객체로 구현되어 있었지만, 이정도 기능에 굳이(?) 객체로 해야할까라는 의구심이 들어 그냥 심플하게 함수로 작성했음. 복잡한 연산자나 PHP에서만 활용되는 내장함수를 사용하지 않았기 때문에 필요에 따라 JS, Go등과 같은 코드로 손쉽게 마이그레이션이 가능할것으로 보인다.

//입력값
//폴리곤 배열 : 폴리곤 영역에 대한 다차원 배열
//검색할 포인트 배열 : 검색할 좌표에 대한 다차원 리스트 배열
//겹침처리 여부 : true > 겹치면 포함 , false > 겹치면 비포함
function polygon_point_check($polygon_array, $points_array, $is_vertex = true){

    //예외처리
    if(!is_array($polygon_array) || !is_array($points_array)){
        return '폴리곤 혹은 좌표계 입력데이터가 배열이 아닙니다.';
    }

    //반환값을 사전에 정의한다.
    $output['inside'] = array();
    $output['outside'] = array();

    $polygon_array = array_unique($polygon_array, SORT_REGULAR); //중복 좌표 제거
    $polygon_array = array_values($polygon_array); //빈 키 삭제
    $polygon_array[] = $polygon_array[0]; //폴리곤이 닫혀야 됨으로 첫번째키가 마지막키로 강제 지정한다.

    //루프 바깥에 count를 달면 더 빠르다.
    $polygon_cnt = count($polygon_array);

    //겹침 계산
    foreach($points_array as $points_key => $points_xy){

        $points_key = (String)$points_key;

        //데이터검사
        if(!is_array($points_xy)){
            return $points_key.' 의 좌표가 배열이 아닙니다.';
        }
        if(count($points_xy) !== 2){
            return $points_key.' 의 좌표의 위도, 경도 배열이 잘못되었습니다.';
        }

        if(strpos($points_xy[0], '.') !== false){
            $points_xy[0] = floatval($points_xy[0]);
        }else{
            $points_xy[0] = intval($points_xy[0]);
        }
        if(strpos($points_xy[1], '.') !== false){
            $points_xy[1] = floatval($points_xy[1]);
        }else{
            $points_xy[1] = intval($points_xy[1]);
        }


        $intersections = 0; 
        for($p=0; $p<$polygon_cnt; $p++){

            //데이터 검사
            if(!is_array($polygon_array[$p])){
                return $p.' 번째 폴리곤 좌표가 배열이 아닙니다.';
            }
            if(count($polygon_array[$p]) !== 2){
                return $p.' 번째 폴리곤 좌표의 위도, 경도 배열이 잘못되었습니다.';
            }

            if(strpos($polygon_array[$p][0], '.') !== false){
                $polygon_array[$p][0] = floatval($polygon_array[$p][0]);
            }else{
                $polygon_array[$p][0] = intval($polygon_array[$p][0]);
            }
            if(strpos($polygon_array[$p][1], '.') !== false){
                $polygon_array[$p][1] = floatval($polygon_array[$p][1]);
            }else{
                $polygon_array[$p][1] = intval($polygon_array[$p][1]);
            }


            if($polygon_array[$p] === $points_xy){
                if($is_vertex){
                    //겹침허용일때
                    $output['inside'][$points_key] = $points_xy;
                }else{
                    //겹침비허용일때
                    $output['outside'][$points_key] = $points_xy;
                }
                continue;
            }

            if($p === 0){
                //첫번째 폴리곤배열은 이전과 비교할 데이터가 없음으로 넘어간다.
                continue;
            }

            if($polygon_array[$p-1][1] === $polygon_array[$p][1] &&
              $polygon_array[$p-1][1] === $points_xy[1] &&
               $points_xy[0] > min($polygon_array[$p-1][0], $polygon_array[$p][0]) &&
               $points_xy[0] < max($polygon_array[$p-1][0], $polygon_array[$p][0])
              ){
                if($is_vertex){
                    //겹침허용일때
                    $output['inside'][$points_key] = $points_xy;
                }else{
                    //겹침비허용일때
                    $output['outside'][$points_key] = $points_xy;
                }
                continue;
            }

            if($points_xy[1] > min($polygon_array[$p-1][1], $polygon_array[$p][1]) &&
              $points_xy[1] <= max($polygon_array[$p-1][1], $polygon_array[$p][1]) &&
               $points_xy[0] <= max($polygon_array[$p-1][0], $polygon_array[$p][0]) &&
               $polygon_array[$p-1][1] !== $polygon_array[$p][1]
              ){

                $xinters = ($points_xy[1] - $polygon_array[$p-1][1]) * 
                    ($polygon_array[$p][0] - $polygon_array[$p-1][0]) / 
                    ($polygon_array[$p][1] - $polygon_array[$p-1][1]) + $polygon_array[$p-1][0]; 

                if($xinters === $points_xy[0]){
                    if($is_vertex){
                        //겹침허용일때
                        $output['inside'][$points_key] = $points_xy;
                    }else{
                        //겹침비허용일때
                        $output['outside'][$points_key] = $points_xy;
                    }
                    continue;
                }

                if($polygon_array[$p-1][0] === $polygon_array[$p][0] || $points_xy[0] <= $xinters){
                    $intersections++; 
                }

            }


        }
        if($intersections % 2 !== 0){
            $output['inside'][$points_key] = $points_xy;
            continue;
        }else{
            $output['outside'][$points_key] = $points_xy;
            continue;
        }
    }

    //출력
    return $output;

}

 

 

 

 

Javascript 소스코드는 다음과 같다.

 

var polygon_array = new Array();
polygon_array[0] = new Array('37.53552567043231', 126.95672035217325);
polygon_array[1] = new Array('37.52790237570185', 126.9499397277836);
polygon_array[2] = new Array(37.51714676004277, 126.96959495544473);
polygon_array[4] = new Array(37.52980827243268, 126.99191093444864); //key 건너뜀
polygon_array[5] = new Array(37.52980827243268, 126.99191093444864); //동일한 좌표
polygon_array[6] = new Array(37.537295252413486, 126.96993827819864);
polygon_array[7] = new Array(37.53552567043231, '126.95672035217325');
console.log('검색대상폴리곤',polygon_array);

var points_array = new Array();
points_array['가락시장역'] = new Array(37.493515041951, 127.118736639621);
points_array['래미안용산'] = new Array(37.529489434399, 126.967329235710);
points_array['겹침'] = new Array('37.51714676004277', 126.96959495544473);
console.log('좌표배열',points_array);

console.log(polygon_point_check(polygon_array, points_array));



function polygon_point_check(polygon_array, points_array, is_vertex = true){

    //다차원배열에서의 중복된 데이터삭제하는 내장함수
    function array_unique(input_array){
        input_array = JSON.parse(JSON.stringify(input_array)); //json stringify는 빈배열을 null로 바꿔준다.
        input_array = input_array.filter((element, i) => element !== null && element !== undefined && element !== '' ); //빈키 삭제
        return [...new Set(input_array.join("|").split("|"))].map((v) => v.split(",")).map((v) => v.map((a) => +a)); //중복된 배열을 삭제한다.
    };

    //예외처리
    if(!Array.isArray(polygon_array) || !Array.isArray(points_array)){
        return '폴리곤 혹은 좌표계 입력데이터가 배열이 아닙니다.';
    }

    //반환값을 사전에 정의한다.
    let output = new Array();
    output['inside'] = new Array();
    output['outside'] = new Array();

    //중복배열 삭제 및 데이터형변환
    polygon_array = array_unique(polygon_array);
    polygon_array.push(polygon_array[0]);


    //루프 바깥에 count를 달면 더 빠르다.
    let polygon_cnt = polygon_array.length;

    for(let points_key in points_array){

        points_key = String(points_key);
        let points_xy = points_array[points_key];

        //데이터검사
        if(!Array.isArray(points_xy)){
            return points_key+' 의 좌표가 배열이 아닙니다.';
        }

        if(points_xy.length !== 2){
            return points_key+' 의 좌표의 위도, 경도 배열이 잘못되었습니다.';
        }


        if(String(points_xy[0]).indexOf('.') !== -1){
            points_xy[0] = parseFloat(points_xy[0]);
        }else{
            points_xy[0] = parseInt(points_xy[0]);
        }
        if(String(points_xy[1]).indexOf('.') !== -1){
            points_xy[1] = parseFloat(points_xy[1]);
        }else{
            points_xy[1] = parseInt(points_xy[1]);
        }

        let intersections = 0;
        for(let p=0; p<polygon_cnt; p++){

            //데이터검사
            if(!Array.isArray(polygon_array[p])){
                return p+' 번째 폴리곤 좌표가 배열이 아닙니다.';
            }
            if(polygon_array[p].length !== 2){
                return p+' 번째 폴리곤 좌표의 위도, 경도 배열이 잘못되었습니다.';
            }

            if(String(polygon_array[p][0]).indexOf('.') !== -1){
                polygon_array[p][0] = parseFloat(polygon_array[p][0]);
            }else{
                polygon_array[p][0] = parseInt(polygon_array[p][0]);
            }
            if(String(polygon_array[p][1]).indexOf('.') !== -1){
                polygon_array[p][1] = parseFloat(polygon_array[p][1]);
            }else{
                polygon_array[p][1] = parseInt(polygon_array[p][1]);
            }

            if(polygon_array[p].toString() === points_xy.toString()){
                if(is_vertex){
                    //겹침허용일때
                    output['inside'][points_key] = points_xy;
                }else{
                    //겹침비허용일때
                    output['outside'][points_key] = points_xy;
                }
                continue;
            }

            if(p === 0){
                //첫번째 폴리곤배열은 이전과 비교할 데이터가 없음으로 넘어간다.
                continue;
            }

            if(polygon_array[p-1][1] === polygon_array[p][1] &&
              polygon_array[p-1][1] === points_xy[1] &&
               points_xy[0] > Math.min(polygon_array[p-1][0], polygon_array[p][0]) &&
               points_xy[0] < Math.max(polygon_array[p-1][0], polygon_array[p][0])
              ){
                if(is_vertex){
                    //겹침허용일때
                    output['inside'][points_key] = points_xy;
                }else{
                    //겹침비허용일때
                    output['outside'][points_key] = points_xy;
                }
                continue;
            }


            if(points_xy[1] > Math.min(polygon_array[p-1][1], polygon_array[p][1]) &&
              points_xy[1] <= Math.max(polygon_array[p-1][1], polygon_array[p][1]) &&
               points_xy[0] <= Math.max(polygon_array[p-1][0], polygon_array[p][0]) &&
               polygon_array[p-1][1] !== polygon_array[p][1]
              ){

                let xinters = (points_xy[1] - polygon_array[p-1][1]) * 
                    (polygon_array[p][0] - polygon_array[p-1][0]) / 
                    (polygon_array[p][1] - polygon_array[p-1][1]) + polygon_array[p-1][0]; 

                if(xinters === points_xy[0]){
                    if(is_vertex){
                        //겹침허용일때
                        output['inside'][points_key] = points_xy;
                    }else{
                        //겹침비허용일때
                        output['outside'][points_key] = points_xy;
                    }
                    continue;
                }

                if(polygon_array[p-1][0] === polygon_array[p][0] || points_xy[0] <= xinters){
                    intersections++; 
                }

            }


        }

        if(intersections % 2 !== 0){
            output['inside'][points_key] = points_xy;
            continue;
        }else{
            output['outside'][points_key] = points_xy;
            continue;
        }

    }

    return output;

};