폴리곤과 폴리곤을 비교하여 겹쳐졌는지 확인하기 (Polygon and Polygon Overlapping for PHP & Javascript)

지도에서 폴리곤의 섹터영역을 설정할때 섹터가 중복되지 않도록 제한해야 한다.

이전에 특정좌표가 폴리곤영역내에 존재하는지 확인하는 Point-in-Polygon 알고리즘을 활용하여 해결했는데,

이번에는 폴리곤과 폴리곤을 비교하여 서로 겹쳐졌는지 확인하는 기능을 개발하였다.

폴리곤 좌표와 검색할 좌표를 비교하여 해당 좌표가 폴리곤안에 들어와있는지 확인하는 PHP함수

(하루가 멀다고 자꾸자꾸 새롭게 개발할게 마구마구 튀어나오고 있는중임)

 

 

 

테스트를 위해 여러개의 폴리곤 좌표계를 활용하였다.

비교 대상이 되는 기본 폴리곤 하나와

기본 폴리곤과 동일한 폴리곤과의 비교,

완전히 겹쳐지지 않는 폴리곤과의 비교,

일부가 겹쳐져 있는 폴리곤과의 비교를 진행하였다.

 

(아래의 코드는 PHP버전으로 만들었고 맨밑으로 내리면 Javascript로 만든 버전이 있다.)

$polygon_basic = array();
$polygon_basic[] = array("37.535003862601", "126.96876525879");
$polygon_basic[] = array("37.527925065235", "126.95966720581");
$polygon_basic[] = array("37.526382161255", "126.97317123413");
$polygon_basic[] = array("37.535003862601", "126.96876525879");
echo '검색대상 폴리곤 : ';
print_r($polygon_basic);
echo '<br /><br />';

unset($polygon_target);
$polygon_target = array();
$polygon_target[] = array("37.535003862601", "126.96876525879");
$polygon_target[] = array("37.527925065235", "126.95966720581");
$polygon_target[] = array("37.526382161255", "126.97317123413");
$polygon_target[] = array("37.535003862601", "126.96876525879");
echo '검색대상 폴리곤과 동일한 폴리곤 : ';
print_r($polygon_target);
echo '<br />';
if(polygon_polygon_check($polygon_basic, $polygon_target)){
    echo '겹쳐짐';
}else{
    echo '겹쳐지지 않음';
}
echo '<br /><br />';

unset($polygon_target);
$polygon_target = array();
$polygon_target[] = array("37.530375494199", "126.9843006134");
$polygon_target[] = array("37.517834307061", "126.97839332581");
$polygon_target[] = array("37.515626326429", "126.9711971283");
$polygon_target[] = array("37.519892539273", "126.98927879334");
$polygon_target[] = array("37.530375494199", "126.9843006134");
echo '겹쳐지지 않는 폴리곤 : ';
print_r($polygon_target);
echo '<br />';
if(polygon_polygon_check($polygon_basic, $polygon_target)){
    echo '겹쳐짐';
}else{
    echo '겹쳐지지 않음';
}
echo '<br /><br />';

 

실행결과는 다음과 같다.

(위도경도의 좌표계는 String형이든 Float형이든 아무렇게나 막써도 작동되도록 해놨음.)

아주 잘된다.

 

 

 

폴리곤을 백터화 하여 비교하고자 했으나,

너무나 귀찮아서 무식한 방법으로 일단은 해결했다.

(나중에 다시 제대로 개발해야 할듯 ㅋㅋ)

 

일단 2개의 폴리곤을 각각 가져온뒤, 폴리곤을 구성하고 있는 꼭지점들을 서로 이어붙여서 각각의 선들로 표현한다.

삼각형일때는 선이 3개가 나올거고,

팔각형일때는 선이 8개가 나올거다.

 

2개의 폴리곤으로부터 나온 선들을 모두 비교하여 선과 선이 겹쳐져 있는지를 확인하는 방법이다.

단순히 선과 선이 겹쳐져 있는 경우뿐만 아니라 선과 선이 동일한 경우도 존재하고,

선의 시작이나 끝지점이 다른 폴리곤의 선 상위에 놓여있는 경우도 존재했기 때문에,

여러가지 경우의 수가 대응되게끔 개발을 진행했다.

 

 

 

작성한 PHP함수는 다음과 같다.

코드 내부에 주석을 달아두었음으로 코드내용에 대해서는 별도의 설명은 없다. 끝.

function polygon_polygon_check($polygon1, $polygon2){
		
    //함수 입력데이터 검사
    if(!is_array($polygon1) || !is_array($polygon2)){
        return false;
    }

    //중복,빈 좌표 제거
    $polygon1 = array_unique($polygon1, SORT_REGULAR); 
    $polygon1 = array_values($polygon1); 
    $polygon1[] = $polygon1[0]; 

    $polygon2 = array_unique($polygon2, SORT_REGULAR); 
    $polygon2 = array_values($polygon2); 
    $polygon2[] = $polygon2[0]; 


    $polygon1_cnt = count($polygon1)-1;
    if($polygon1_cnt < 3){
        //삼각형이상 되어야 함.
        return false;
    }

    $polygon2_cnt = count($polygon2)-1;
    if($polygon2_cnt < 3){
        //삼각형이상 되어야 함.
        return false;
    }

    //폴리곤을 꼭지점 단위로 선으로 만든뒤,
    //그 선들끼리 서로 겹쳐짐을 비교하여 폴리곤이 겹쳐져 있는지 검사한다.
    for($p=$polygon1_cnt; $p>=0; $p--){
        if($p-1 >= 0){

            //데이터형 변환
            if(strpos($polygon1[$p][0], '.') !== false){
                $polygon1[$p][0] = floatval($polygon1[$p][0]);
            }else{
                $polygon1[$p][0] = intval($polygon1[$p][0]);
            }
            if(strpos($polygon1[$p][1], '.') !== false){
                $polygon1[$p][1] = floatval($polygon1[$p][1]);
            }else{
                $polygon1[$p][1] = intval($polygon1[$p][1]);
            }
            if(strpos($polygon1[$p-1][0], '.') !== false){
                $polygon1[$p-1][0] = floatval($polygon1[$p-1][0]);
            }else{
                $polygon1[$p-1][0] = intval($polygon1[$p-1][0]);
            }
            if(strpos($polygon1[$p-1][1], '.') !== false){
                $polygon1[$p-1][1] = floatval($polygon1[$p-1][1]);
            }else{
                $polygon1[$p-1][1] = intval($polygon1[$p-1][1]);
            }

            //꼭지점을 이어서 선형으로 변경한다.
            $polyline1 = array();
            $polyline1[0] = array($polygon1[$p][0], $polygon1[$p][1]);
            $polyline1[1] = array($polygon1[$p-1][0], $polygon1[$p-1][1]);


            //폴리곤을 꼭지점 단위로 선으로 만든다.
            for($q=$polygon2_cnt; $q>=0; $q--){
                if($q-1 >= 0){

                    //데이터형 변환
                    if(strpos($polygon2[$q][0], '.') !== false){
                        $polygon2[$q][0] = floatval($polygon2[$q][0]);
                    }else{
                        $polygon2[$q][0] = intval($polygon2[$q][0]);
                    }
                    if(strpos($polygon2[$p][1], '.') !== false){
                        $polygon2[$q][1] = floatval($polygon2[$q][1]);
                    }else{
                        $polygon2[$q][1] = intval($polygon2[$q][1]);
                    }
                    if(strpos($polygon2[$q-1][0], '.') !== false){
                        $polygon2[$q-1][0] = floatval($polygon2[$q-1][0]);
                    }else{
                        $polygon2[$q-1][0] = intval($polygon2[$q-1][0]);
                    }
                    if(strpos($polygon2[$q-1][1], '.') !== false){
                        $polygon2[$q-1][1] = floatval($polygon2[$q-1][1]);
                    }else{
                        $polygon2[$q-1][1] = intval($polygon2[$q-1][1]);
                    }

                    //꼭지점을 이어서 선형으로 변경한다.
                    $polyline2 = array();
                    $polyline2[0] = array($polygon2[$q][0], $polygon2[$q][1]);
                    $polyline2[1] = array($polygon2[$q-1][0], $polygon2[$q-1][1]);

                    //선과 선이 동일할때 가차없이 겹쳐짐으로 처리
                    if($polyline1 === $polyline2){
                        return true;
                    }

                    //선과 선의 교차점 계산하기

                    $under = ($polyline2[1][1] - $polyline2[0][1]) * ($polyline1[1][0] - $polyline1[0][0]) - ($polyline2[1][0] - $polyline2[0][0]) * ($polyline1[1][1] - $polyline1[0][1]);
                    if($under == 0){
                        //동일한 선상일 때는 겹쳐짐으로 처리
                        return true;
                    }

                    $t = ($polyline2[1][0] - $polyline2[0][0]) * ($polyline1[0][1] - $polyline2[0][1]) - ($polyline2[1][1] - $polyline2[0][1]) * ($polyline1[0][0] - $polyline2[0][0]);
                    $s = ($polyline1[1][0] - $polyline1[0][0]) * ($polyline1[0][1] - $polyline2[0][1]) - ($polyline1[1][1] - $polyline1[0][1]) * ($polyline1[0][0] - $polyline2[0][0]);
                    if($t == 0){
                        //근사치가 무조건 0으로 나옴
                        continue;
                    }
                    if($s == 0){
                        //근사치가 무조건 0으로 나옴
                        continue;
                    }

                    //근사치 계산
                    $t_under = $t / $under;
                    $s_under = $s / $under;

                    if($t_under <= 0 || $t_under > 1 || $s_under <= 0 || $s_under > 1){
                        //under를 나눈값이 0~0.99999999... 의 근사치라면 겹쳐져 있지 않다.
                        continue;
                    }

                    //겹쳐짐
                    return true;

                }
            }


        }
    }

    //그외 2개의 폴리곤은 서로 겹쳐지지 않는다.
    return false;

}

 

 

 

 

내용추가)

PHP의 서버사이드 로직뿐만 아니라 프론트엔드에서도 한번 걸러야되서 Javascript로 동일한 기능을 포팅했다.

아래는 Javascript버전의 함수 및 테스트코드이다.

(PHP에서는 array_unique 라고하는 내장함수 있어서 좀 쉬웠는데 JS에는 그와 동일한 함수를 만들어야되서 애 좀 먹었음)

var polygon_basic = new Array();
polygon_basic[0] = new Array("37.535003862601", "126.96876525879");
polygon_basic[1] = new Array("37.527925065235", "126.95966720581");
polygon_basic[2] = new Array("37.526382161255", "126.97317123413");
polygon_basic[3] = new Array("37.535003862601", "126.96876525879");
document.write('검색대상폴리곤 : '+polygon_basic+'<br /><br />');

var polygon_target = new Array();
polygon_target[0] = new Array("37.535003862601", "126.96876525879");
polygon_target[1] = new Array("37.527925065235", "126.95966720581");
polygon_target[2] = new Array("37.526382161255", "126.97317123413");
polygon_target[3] = new Array("37.535003862601", "126.96876525879");
document.write('완전히동일한폴리곤 : '+polygon_target+'<br />');
if(polygon_polygon_check(polygon_basic, polygon_target)){
    document.write('겹쳐짐<br /><br />');
}else{
    document.write('겹쳐지지 않음<br /><br />');
}

var polygon_target = new Array();
polygon_target[0] = new Array("37.530375494199", "126.9843006134");
polygon_target[1] = new Array(37.527834307061, 126.96839332581);
polygon_target[2] = new Array("37.515626326429", "126.9711971283");
polygon_target[3] = new Array("37.519892539273", "126.98927879334");
polygon_target[4] = new Array("37.519892539273", "126.98927879334");
polygon_target[5] = new Array("37.530375494199", "126.9843006134");
document.write('겹쳐진폴리곤 : '+polygon_target+'<br />');
if(polygon_polygon_check(polygon_basic, polygon_target)){
    document.write('겹쳐짐<br /><br />');
}else{
    document.write('겹쳐지지 않음<br /><br />');
}

var polygon_target = new Array();
polygon_target[0] = new Array("37.530375494199", "126.9843006134");
polygon_target[1] = new Array("37.517834307061", "126.97839332581");
polygon_target[2] = new Array("37.515626326429", "126.9711971283");
polygon_target[3] = new Array("37.519892539273", "126.98927879334");
polygon_target[4] = new Array("37.530375494199", "126.9843006134");
document.write('겹쳐지지않는폴리곤 : '+polygon_target+'<br />');
if(polygon_polygon_check(polygon_basic, polygon_target)){
    document.write('겹쳐짐<br /><br />');
}else{
    document.write('겹쳐지지 않음<br /><br />');
}



function polygon_polygon_check(polygon1, polygon2){

    //다차원배열에서의 중복된 데이터삭제하는 내장함수
    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(polygon1) || !Array.isArray(polygon2)){
        return false;
    }

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

    polygon2 = array_unique(polygon2);
    polygon2.push(polygon2[0]);

    let polygon1_cnt = polygon1.length - 1;
    if(polygon1_cnt < 3){
        //삼각형이상이 되어야함
        return false;
    }

    let polygon2_cnt = polygon2.length - 1;
    if(polygon2_cnt < 3){
        //삼각형이상이 되어야함
        return false;
    }

    for(let p=polygon1_cnt; p>=0; p--){
        if(p-1 >= 0){
            //꼭지점을 이어서 선형으로 변경한다.
            let polyline1 = new Array();
            polyline1[0] = new Array(polygon1[p][0], polygon1[p][1]);
            polyline1[1] = new Array(polygon1[p-1][0], polygon1[p-1][1]);

            for(let q=polygon2_cnt; q>=0; q--){
                if(q-1 >= 0){
                    //꼭지점을 이어서 선형으로 변경한다.
                    let polyline2 = new Array();
                    polyline2[0] = new Array(polygon2[q][0], polygon2[q][1]);
                    polyline2[1] = new Array(polygon2[q-1][0], polygon2[q-1][1]);


                    //선과 선이 동일할때 가차없이 겹쳐짐으로 처리
                    if(polyline1.toString() === polyline2.toString()){
                        return true;
                    }

                    //선과 선의 교차점 계산하기

                    let under = (polyline2[1][1] - polyline2[0][1]) * (polyline1[1][0] - polyline1[0][0]) - (polyline2[1][0] - polyline2[0][0]) * (polyline1[1][1] - polyline1[0][1]);
                    if(under == 0){
                        //동일한 선상일 때는 겹쳐짐으로 처리
                        return true;
                    }

                    let t = (polyline2[1][0] - polyline2[0][0]) * (polyline1[0][1] - polyline2[0][1]) - (polyline2[1][1] - polyline2[0][1]) * (polyline1[0][0] - polyline2[0][0]);
                    let s = (polyline1[1][0] - polyline1[0][0]) * (polyline1[0][1] - polyline2[0][1]) - (polyline1[1][1] - polyline1[0][1]) * (polyline1[0][0] - polyline2[0][0]);
                    if(t == 0){
                        //근사치가 무조건 0으로 나옴
                        continue;
                    }
                    if(s == 0){
                        //근사치가 무조건 0으로 나옴
                        continue;
                    }

                    //근사치 계산
                    let t_under = t / under;
                    let s_under = s / under;

                    if(t_under <= 0 || t_under > 1 || s_under <= 0 || s_under > 1){
                        //under를 나눈값이 0~0.99999999... 의 근사치라면 겹쳐져 있지 않다.
                        continue;
                    }

                    //겹쳐짐
                    return true;

                }
            }
        }
    }

    //그외 2개의 폴리곤은 서로 겹쳐지지 않는다.
    return false;

};