이슈

Cesium의 내장 함수를 활용하면 기본적으로 도형의 위치를 판단할 수 있다.

하지만 도형을 그리는 기능을 개발하는 과정에서 문제가 생겼다.

1) 도형의 교차 여부 판단의 문제

2) 도형이 hole인 경우 도형의 내부에 있는지 외부에 있는지에 대한 판단의 문제

해결 방안

위와 같은 문제들로 인하여 기본적인 기능으로는 한계를 느껴 기능을 새로 구현하는 방법을 택했다.

도형의 위치를 판단하기 위해서는 몇 가지 단계를 검증해야 한다.

1) CCW를 활용하여 점들 사이의 방향성 확인

2) 방향성 정보를 활용하여 두 직선의 교차 관계 확인

3) 두 직선의 교차 관계를 활용하여 두 도형의 내부 외부 관계 확인

구현

1) CCW를 활용하여 점들 사이의 방향성 확인

(출처: https://www.acmicpc.net/blog/view/27)

임의의 위치의 3개의 점이 나타날 수 있는 형태는 벡터의 외적을 통해 나온 결과로 정의할 수 있다.

• 음수인 경우 시계 방향
• 0인 경우 일직선
• 양수인 경우 반시계 방향

코드는 다음과 같다.

function ccw(c1, c2, c3){
    const [x1, y1] = c1;
    const [x2, y2] = c2;
    const [x3, y3] = c3;
    const r = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);
    if(r > 0) {
        return 1
    } else if(r == 0) {
        return 0
    } else {
        return -1
    }
}

2) 방향성 정보를 활용하여 두 직선의 교차 관계 확인

CCW 알고리즘은 활용하면 두 직선이 교차하는지 안 하는지를 판단할 수 있다.

직선 A(x1, x2)와 직선 B(x3, x4) 가 있다고 가정해 보자.

직선 A의 점들 x1, x2과 직선 B의 한 점 x3에 대해 CCW(x1, x2, x3)를 했을 때
시계 방향이 나왔다고 가정해 보자.

마찬가지로 직선 A의 점들 x1, x2과 직선 B의 한 점 x4에 대해 CCW(x1, x2, x4)를 했을 때
반시계 방향이 나왔다고 가정해 보자.

직선 A의 입장에서 x3는 시계 방향 x4는 반시계 방향이 나오게 되는데 이 경우가 바로 직선이 교차하는 경우다.

하지만 위의 그림처럼 직선 A와 직선 B가 교차하지 않으면서 위의 조건을 만족하는 경우가 존재한다.

이러한 예외가 존재하기 때문에 직선 B도 직선 A의 각 점에 대해 CCW를 해야 한다.

또한 직선 A와 직선 B가 완전히 겹쳤을 때의 케이스도 예외로 존재하지만 해당 케이스는 실제 도형을 그리는 과정에서는 발생하지 않는 경우라고 판단하여 스킵 하였다.

해당 상황을 구현한 코드는 아래와 같다.

function line_intersection(l1, l2){
    const [c1, c2] = l1;
    const [c3, c4] = l2;
    return ccw(c1,c2,c3) * ccw(c1,c2,c4) < 0 && ccw(c3,c4,c1) * ccw(c3,c4,c2) < 0;
}

3) 두 직선의 교차 관계를 활용하여 두 도형의 내부 외부 관계 확인

도형을 직선의 집합이라고 생각해 보면 두 도형 간의 내부/외부 판단은 각 직선별 교차 여부에 따라 판단이 가능해진다.

도형 A와 도형 B가 있다고 가정해 보자.

내부 판단 조건

도형 B가 도형 A의 내부에 위치하기 위해서는 다음과 같은 조건을 만족해야 한다.

• 도형 B의 모든 직선은 도형 A의 모든 직선과 교차하지 않아야 한다.
  

function get_line(index, polygon) {
    const coord_a = polygon[index];
    const coord_b = polygon[index == polygon.length - 1 ? 0 : index + 1];
    return [coord_a, coord_b];
}

function polygon_in_polygon(inner_polygon, outer_polygon){
    for(let i=0; i<inner_polygon.length; i++){
        const inner_line = get_line(i, inner_polygon);
        for(let j=0; j<outer_polygon.length; j++){
            const outer_line = get_line(j, outer_polygon);
            if(line_intersection(inner_line, outer_line)) {
                return false;
            }
        }
    }
    return true;
}

외부 판단 조건

도형 B가 도형 A의 외부에 위치하려면 다음 조건을 만족해야 한다.

• 도형 B의 모든 점에 대하여 도형 A와 관통하는 가상의 직선을 그었을 때 교차하는 직선의 개수가 짝수여야 한다.

아래 코드는 한 점에 대하여 도형의 외부를 판단하는 코드이다.
이것을 응용해서 도형 B의 모든 점에 대하여 도형 A와 비교해 보면 원하는 결과를 얻을 수 있을 것이다.

function point_in_polygon(point, polygon){
    const infinity_line = [point, (1000000001, point[1]+1)]
    let cnt = 0;
    for(let i=0; i<polygon.length; i++) {
      line = [polygon[i], polygon[i == polygon.length-1 ? 0 : i+1]]
      if(line_intersection(infinity_line, line)) {
        cnt++;
      }
    }
    return cnt % 2 == 1;
}

전체 코드

function ccw(c1, c2, c3){
    const [x1, y1] = c1;
    const [x2, y2] = c2;
    const [x3, y3] = c3;
    const r = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);
    if(r > 0) {
        return 1
    } else if(r == 0) {
        return 0
    } else {
        return -1
    }
}

function line_intersection(l1, l2){
    const [c1, c2] = l1;
    const [c3, c4] = l2;
    return ccw(c1,c2,c3) * ccw(c1,c2,c4) < 0 && ccw(c3,c4,c1) * ccw(c3,c4,c2) < 0;
}

function get_line(index, polygon) {
    const coord_a = polygon[index];
    const coord_b = polygon[index == polygon.length - 1 ? 0 : index + 1];
    return [coord_a, coord_b];
}

function point_in_polygon(point, polygon){
    const infinity_line = [point, (1000000001, point[1]+1)]
    let cnt = 0;
    for(let i=0; i<polygon.length; i++) {
      line = [polygon[i], polygon[i == polygon.length-1 ? 0 : i+1]]
      if(line_intersection(infinity_line, line)) {
        cnt++;
      }
    }
    return cnt % 2 == 1;
}

function polygon_in_polygon(inner_polygon, outer_polygon){
    for(let i=0; i<inner_polygon.length; i++){
        const inner_line = get_line(i, inner_polygon);
        for(let j=0; j<outer_polygon.length; j++){
            const outer_line = get_line(j, outer_polygon);
            if(line_intersection(inner_line, outer_line)) {
                return false;
            }
        }
    }
    return true;
}

검증 결과

const innerPolygon = [
    [126.8992388857407,37.516710021710544],
    [126.90168380428308,37.51738982954409],
    [126.9009169479137,37.515393323661776],
    [126.90044781225242,37.51545772791107],
    [126.89902236158935,37.515543600156974]
];

const innerPolygon2 = [
    [126.89751958474302,37.51689085359373],
    [126.89833891945284,37.51681262787424],
    [126.89741337468804,37.51653582851612]
];
const outerPolygon = [
    [126.90077323166837,37.516313585487545],
    [126.90045381892233,37.51543292563556],
    [126.89952020455789,37.51517851872021],
    [126.89856202404765,37.51556992425281],
    [126.89829175610383,37.51660714734857],
    [126.89907796684133,37.51731168033362],
    [126.9010435162342,37.5173116665251],
    [126.9018296927714,37.51603958195428],
    [126.90143655608993,37.51494365208521],
    [126.89998700208572,37.514513125257956],
    [126.9018050636472,37.51429782277592],
    [126.90264043161399,37.51517846596399],
    [126.90308274347228,37.51662665661408],
    [126.90271425776659,37.51776174621863],
    [126.89986419519305,37.518290191958286],
    [126.89782491084274,37.518231481955794],
    [126.89679302471801,37.51703767427132],
    [126.89674392246489,37.51586345549346],
    [126.89777583992974,37.51465011443287],
    [126.90003614392883,37.51494367190438],
    [126.90111717575847,37.515413345891695],
    [126.90114176426334,37.51617658780607]
];

polygon_in_polygon(innerPolygon, outerPolygon); // false
polygon_in_polygon(innerPolygon2, outerPolygon);// true