다각선(Path)를 다각형(Polygon)으로 만들기

📖 개요

도로 정보(Path)를 일정 폭을 가진 폴리곤의 형태로 서버에 넘겨야할 요구사항이 있었다.

처음엔 ChatGPT의 힘을 빌리려했으나 소스가 많이 없는 탓인지 요구를 너무 두루뭉술하게 했던 탓인지 멍청한 답만 내뱉고 학습시키기도 번거로워서 직접 구현하기로했다.

그래서 결국 실제 내가 원하는 요구사항(선을 다각형으로 변경했을 때 렌더링 결과)들을 여러 테스트 케이스로 설정해두고 수식을 통해 직접 구현하기로 하였다.

구현한 내용은 지도 상 위경도를 바탕으로 작업했지만 코드에서 기준값만 변경하면 일반적인 좌표계 상에서도 충분히 사용할 수 있을 것이다.

머리를 쥐어짰던 흔적이 남아있는 사진들...🥲

 

구현 사항을 적기에 앞서 말하자면 절대 맞는 풀이가 아니며 허점과 한계가 많은 수식이다. 글의 마지막에 라이브러리를 이용해 정석적으로 구현한 부분도 작성할테니 솔루션이 필요하신 분은 마지막을 참고하시면 된다.

---

✍️ 구현

🧐 Approximate Logic

1. 점 P1과 점 P2사이의 각도를 구한다.
2. 각도에 따라 dx, dy 값을 P1, P2 각각 더하고 빼주어 P1’, P1”, P2’, P2” 총 네 개의 점을 만들어 준다.
3. P1’, P1”이 이미 존재할 경우 그 값을 기준으로 dx, dy 값을 빼준다.
4. P0, P1, P2 총 세 점에서 P1의 각도를 구하여 중복으로 처리된 P1’, P1”의 중복된 델타값에 가중치를 곱해준다.
5. Array’(P1’, P2’, P3’, …), Array”(P1”, P2”, P3”, …) 두 배열에 각각의 점들을 저장한다.
6. 반복하며 마지막 점은 연산하지 않는다.
7. 순행, 역행의 순서로 배열을 나열해주면 폴리곤 완성🙀

 

⌨️ Code

1. 너비를 실제 Metric으로 받기 위해 Meter를 위경도로 환산해주는 함수가 필요했고 아래와 같다

function getLatLngDeltaFromDistance(
  distanceInMeter: number,
): { lat: number; lng: number } {
  const EARTH_RADIUS = 6371000 // 지구 반지름 (미터)
  const SEOUL_MEDIUM_LATITUDE = 37.5 // 한국 33~39, 한반도 ~43 
  const latDelta = (180 / Math.PI) * (distanceInMeter / EARTH_RADIUS) // 위도 변화량
  const lngDelta = latDelta / Math.cos((Math.PI / 180) * SEOUL_MEDIUM_LATITUDE) // 경도 변화량 (서울 위도 기준)
  return { lat: latDelta, lng: lngDelta }
}
// ! 원래는 위도에 따라 경도의 거리 단위가 달라지게 되나, 한국 기준으로 작성

 

2. 두 점 사이의 각을 구할 때는 Math.atan()함수와 Math.atan2()를 사용할 수 있다. Math.atan()는 (-π/2, π/2) 범위의 값을 반환하고 Math.atan2()는 (-π, π)를 반환한다. 좌표계 전체를 커버하기 위해 atan2를 사용했다.

 

3. 두 점 사이의 각을 θ라고 하고, 진행방향이 우상향이며, θ가 0도일 때 P2를 기준으로 위도(Latitude)만 증감하며, θ가 90도일 때 경도(Longitude)만 증감한다. 이에 서로 sin, cos 함수와 관계가 있음을 알 수 있고 dx, dy는 다음과 같다.  

const radians = Math.atan2(p2[0] - p1[0], p2[1] - p1[1])

const dx = Math.sin(radians) * getLatLngDeltaFromDistance(width).lng
const dy = Math.cos(radians) * getLatLngDeltaFromDistance(width).lat

 

4. 첫 점 과 마지막 점을 제외하고는 연결된 선분이 두 개이기 때문에 P1으로써 한 번, P2로써 한 번 총 두 번씩 연산이 된다. 이로 인해 서로다른 delta 값이 중복으로 연산되며 가중치 계산이 필요하다. 테스트 케이스를 통해 가중치는 P0, P1, P2를 연결하는 P1의 각도에 따라 달라지는 것을 알게되었고, 직선일 때(n*π) 1/2, 직각일 때 (n/2*π) 1임을 알아냈다. 이를 만족하는 아래의 주기함수를 통해 weight를 구해 중복된 delta값에 곱해주었다.

/**
*  아마도 틀린 식일 것이다. 대부분의 케이스에서 정상적으로 동작하지만 
*  각이 좁은 예각의 경우 폴리곤이 좁아지며 찌그러진다.
**/
/* 0.75 + 0.25 * sin(2x-0.5π) */
const weight = 0.75 + 0.25 * Math.sin(2 * radians - 0.5 * Math.PI)

/**
*  복잡한 식을 더 간소화 하고 예각일 때의 케이스를 좀 더 대응할 수 있도록 향상시켰으나
*  여전히 드라마틱하게 좁은 예각의 경우 폴리곤이 좁아지며 찌그러진다.
**/
/* 0.5 * cos(x) + 1 */
const weight = 0.5 * Math.cos(radians) + 1

 

5. dx, dy만큼 보정한 정점들로 폴리곤을 만들 수 있는 방법에는 여러가지가 있지만 간단히 구하기 위해서는 아 래와 같은 방법 들이 있으며 점 순서가 기존 Polyline 순서와 동일하게 시작하고 가독성이 좋아보여 a 방식으로 폴리곤을 만들어주었다.

a. 순행 Array’ , 역행 Array”
b. 역행 Array’ , 순행 Array”
c. 순행 Array” , 역행 Array’
d. 역행 Array” , 순행 Array’

결과물

⛔️ 한계

• 두 점이 예각으로 이루어져있을 경우 폴리곤이 과하게 좁아짐
• 다양한 위치 및 국가(위도)에서 사용 불가능

---

✅ 대안(이라 쓰고 정석이라 읽는다.)

http://www.gisdeveloper.co.kr/?p=6375 (참고. 해당 블로그는 지리데이터를 다룬다면 무조건 즐겨찾기 해놓기를 추천한다.)

[OpenLayers] 지오메트리(Geometry)에 대한 공간 연산(JSTS.js 사용) – GIS Developer

글을 참고, jsts 라이브러리를 이용하면 가능할 것을 확인하였다. (역시 더욱 찾다보니 능력자들이 해놓은 게 있었다.)

jsts는 기하학적 기능을 제공하는 jts 라이브러리를 토대로 만들어진 javascript 라이브러리이다.

javascript typescript의 줄임말이 아니다.

 

추가로 https://stackoverflow.com/questions/36132689/how-to-convert-polyline-with-weight-to-polygon-in-leaflet 답변에서 해답을 얻었고, 코드에 조금 수정을 더했다.

type Position = [number, number]
type Path = Position[]

const pathToPolygon = (polyline: Path, width: number) => {
  // pathCoords should be an array of jsts.geom.Coordinate
  const pathCoords = polyline.map(p => new jsts.geom.Coordinate(...p))
  const geometryFactory = new jsts.geom.GeometryFactory()

  // on what distance new polygon should be built
  const distance = (width * 0.001) / 111.12
  const shell = geometryFactory.createLineString(pathCoords)

  // building a new polygon
  const polygon = shell.buffer(distance)

  // finally get your new polygon coordinates
  const polygonCoords: Polygon = polygon
    .getCoordinates()
    .map(coords => [coords.x, coords.y])
  return polygonCoords
}

결과물 2

위의 직접 만든 방식과는 달리 훨씬 매끄러운 결과물을 보여준다.

 

해당 방식의 특징은 각 정점(vertex)에 반지름 r만큼의 원을 만들어주고 그것들을 잇는 방식이라 polygon의 모서리가 곡선이 되며 그만큼 polygon을 표현하기 위한 point들이 많아진다는 점이다.

(참고로 위의 직접 만든 코드의 경우에는 n개의 정점으로 이루어진 Path를 Polygon으로 만들었을 때 n*2개의 정점으로 이루어진 Polygon이 나온다.)

---

🤔 후기

아무래도 개인 프로젝트가 아니라 회사 일로 하는 거다보니 일정이 있었고, 그 일정에 맞추다보니 좀 탄탄한 결과가 나오지 않았던 것 같다.

생각하지 못한 케이스도 있었고 수식을 더 면밀히 짜보거나 살펴보지 못했다.

대략적인 접근과 시도는 좋았으나 중간에 어떠한 오류가 있었던 것같다.

기회가 된다면 내가 만든 코드를 더 고도화시켜서 오픈소스화 시켜보고 싶다.