point-in-polygon 알고리즘으로 국내외 판단하기

 

 

트리플 웹 일정판을 개발하면서 특정 위경도 좌표 지점이 국내인지 해외인지 판단하는 방법이 필요했습니다.

구글 지도 API에서 제공하는 reverse geocoding같은 방법을 통해 해결할 수도 있지만, 추가적인 API 사용을 위해 비용을 지불하는 대신 수학적으로 가볍게 처리할 수 있는 방법을 찾아봤습니다.

 

📌 Point-In-Polygon 알고리즘

다각형의 교점을 이용해서 판단하기

 

 

위와 같은 다각형에서 붉은 점을 A 라고 하겠습니다.

이때 좌표 A 가 다각형 안에 존재하는지 판단하기 위해서는 해당 지점을 기준으로 수평선을 그어서 교차되는 변의 개수를 세어주면 됩니다.

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

 

방향은 상관없고, 한쪽으로만 그어주면 됩니다. 이때 교차되는 지점을 node 라고 표현하겠습니다.

만약 node 의 개수가 홀수라면 다각형의 내부에, 짝수라면 외부에 존재하는 것입니다.

 

node가 꼭짓점에 존재하는 경우

node 가 꼭짓점에 있는 경우를 고려해 보면 다음과 같습니다.

 

 

두 경우 모두 한 변에 대해서 수평 직선의 교차 조건을 설정해 주면 중복되는 node 를 제거할 수 있습니다.

예를 들어 첫 번째 다각형에서 변 a 가 두 정점 a'1 과 a'2 로 이루어진다고 할 때, a'1 <= X < a'2 에 포함되는 경우에만 교점으로 판단하는 것입니다.

 

node의 X축 좌표값 구하기

교점의 Y 축 좌표는 기준점과 동일한데, 그러면 X 축 좌표값은 어떻게 알 수 있을까요?

이때 2차원 직선의 방정식 을 사용해서 구할 수 있습니다.

 

https://www.sarthaks.com/223593/derive-the-equation-the-straight-line-passing-through-the-point-x1-y1-and-having-the-slope

 

m (기울기) : (y - y1) / (x - x1)

x = (y - y1) / m + x1

 

코드로 옮겨보자

위 내용들을 코드로 구현하면 다음과 같습니다.

const GEO_POLYGON = [
    // ...
]

const SIZE = GEO_POLYGON.length

export function isPointInPolygon(point) {
  const target = getLatLng(point)

  let end = SIZE - 1
  let isInside = false

  for (let start = 0; start < SIZE; start += 1) {
    const { lat: slat, lng: slng } = getLatLng(GEO_POLYGON[start])
    const { lat: elat, lng: elng } = getLatLng(GEO_POLYGON[end])

        // ✅ Y 축 좌표가 (start, end) 로 이루어진 변에 포함되는지 판단합니다.
    const isYIntersect =
      (slat < target.lat && target.lat <= elat) ||
      (elat < target.lat && target.lat <= slat)

    if (isYIntersect) {
            // ✅ 직선의 방정식으로 교점의 X 좌표를 구합니다.
      const gradient = (elat - slat) / (elng - slng)
      const x = slng + (target.lat - slat) / gradient

            // ✅ 기준 좌표보다 왼쪽에 위치하는 교점만 포함시킵니다.
      if (x < target.lng) {
        isInside = !isInside
      }
    }

    end = start
  }

  return isInside
}

 

📌 주의사항

Point-In-Polygon 알고리즘은 2차원 평면을 가정하고 정의된 것이기 때문에 실제 위경도 좌표계에 대입해서 사용하면 지구의 곡률 때문에 오차가 발생합니다.

다만 대한민국의 경우 대륙의 면적이 이 오차의 영향을 받을 만큼 크지는 않기 때문에 해당 알고리즘을 이용해서 판단했습니다.

 

📌 참고자료

Determining Whether A Point Is Inside A Complex Polygon