Coverage Path Planning (Boustrophedon 패턴) 알고리즘

농업용 드론의 자율 비행 경로를 생성하는 Coverage Path Planning 알고리즘에 대해 설명합니다.

개요

Coverage Path Planning (CPP) 은 로봇이나 드론이 주어진 영역을 빠짐없이 커버하는 경로를 생성하는 알고리즘입니다.

농업용 드론에서는 다음과 같은 용도로 사용됩니다:

• 농약/비료 살포
• 작물 모니터링
• 항공 촬영

Boustrophedon 패턴이란?

"Boustrophedon"은 그리스어로 "소가 밭을 가는 방식"을 의미합니다. 왕복하며 지그재그로 이동하는 패턴으로, 영역 커버리지에 가장 효율적인 방식 중 하나입니다.

    ┌─────────────────┐
    │ →→→→→→→→→→→→→→  │  라인 1 (정방향)
    │               ↓ │  턴
    │ ←←←←←←←←←←←←←←  │  라인 2 (역방향)
    │ ↓               │  턴
    │ →→→→→→→→→→→→→→  │  라인 3 (정방향)
    └─────────────────┘

---

알고리즘 흐름

┌──────────────────────────────────────────────────────────────┐
│                    입력: 폴리곤 좌표 (WGS84)                 │
│                         드론 시작 위치                       │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  1. 좌표 변환: WGS84 → 미터 (로컬 평면 좌표계)               │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  2. 폴리곤 수축: 경계에서 swathWidth/2 만큼 안쪽으로         │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  3. 좌표 정규화: 소수점 → 정수, 최소값 → 0                   │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  4. 최적 스위프 각도 탐색: 0°~180° 범위에서 최단 경로 각도   │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  5. 스위프 라인 생성: 폴리곤 중심 기준 평행선 생성           │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  6. 교차 세그먼트 계산: 스위프 라인 ∩ 폴리곤 경계            │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  7. Boustrophedon 연결: 지그재그 패턴으로 세그먼트 연결      │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  8. 시작점 최적화: 드론 위치와 가까운 끝점에서 시작          │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│  9. 좌표 역변환: 미터 → WGS84                                │
└──────────────────────────────────────────────────────────────┘
                              ↓
┌──────────────────────────────────────────────────────────────┐
│           출력: 웨이포인트 배열 (lat, lng, sprayOn)          │
└──────────────────────────────────────────────────────────────┘

---

핵심 단계별 설명

1. 좌표 변환 (WGS84 → 미터)

GPS 좌표(위도/경도)는 곡면 위의 각도 값이므로 거리 계산이 어렵습니다. 평면 좌표계로 변환하여 미터 단위로 계산합니다.

// 위도 1도당 약 111.32km
const metersPerDegreeLat = 111320

// 경도 1도당 거리는 위도에 따라 달라짐
const metersPerDegreeLng = 111320 * Math.cos(toRadians(origin.lat))

// WGS84 → 미터 변환
const latLngToMeters = (coord: Coordinate, origin: Coordinate): Point2D => {
  return {
    x: (coord.lng - origin.lng) * metersPerDegreeLng,
    y: (coord.lat - origin.lat) * metersPerDegreeLat
  }
}

2. 폴리곤 수축 (Polygon Shrinking)

드론이 농지 경계를 벗어나지 않도록 살포폭의 절반만큼 경계를 안쪽으로 수축합니다.

원본 폴리곤          수축된 폴리곤
┌──────────┐        ┌────────┐
│          │   →    │ offset │
│          │        │   ↓    │
│          │        │┌──────┐│
│          │        ││      ││
└──────────┘        │└──────┘│
                    └────────┘

알고리즘:

1. 각 변의 법선 벡터(안쪽 방향) 계산
2. 각 변을 법선 방향으로 offset만큼 이동
3. 이동된 변들의 교차점 계산 → 새로운 폴리곤 정점

// 폴리곤 방향(CW/CCW) 확인 - Signed Area 사용
const isCounterClockwise = (polygon: Point2D[]): boolean => {
  let signedArea = 0
  for (let i = 0; i < polygon.length; i++) {
    const j = (i + 1) % polygon.length
    signedArea += polygon[i].x * polygon[j].y
    signedArea -= polygon[j].x * polygon[i].y
  }
  return signedArea > 0
}

// 법선 벡터 계산 (안쪽 방향)
const dx = p2.x - p1.x
const dy = p2.y - p1.y
const length = Math.sqrt(dx * dx + dy * dy)

// CCW: 왼쪽 90도 회전, CW: 오른쪽 90도 회전
const nx = isCCW ? -dy / length : dy / length
const ny = isCCW ? dx / length : -dx / length

3. 최적 스위프 각도 탐색

폴리곤 형태에 따라 최적의 비행 각도가 달라집니다. 좁고 긴 폴리곤은 긴 변과 평행하게 비행하면 턴 횟수가 줄어들어 효율적입니다.

const findOptimalSweepAngle = (polygon: Point2D[], spacing: number): number => {
  let minLength = Infinity
  let optimalAngle = 0

  // 0° ~ 180° 범위에서 5° 간격으로 탐색
  for (let angle = 0; angle < 180; angle += 5) {
    const pathLength = calculatePathLengthForAngle(polygon, angle, spacing)

    if (pathLength < minLength) {
      minLength = pathLength
      optimalAngle = angle
    }
  }

  // 최적 각도 근처에서 1° 간격으로 정밀 탐색
  for (let angle = optimalAngle - 5; angle <= optimalAngle + 5; angle++) {
    const pathLength = calculatePathLengthForAngle(polygon, angle, spacing)

    if (pathLength < minLength) {
      minLength = pathLength
      optimalAngle = angle
    }
  }

  return optimalAngle
}

4. 스위프 라인 생성

폴리곤 중심을 기준으로 일정 간격의 평행선을 생성합니다.

const generateSweepLines = (
  polygon: Point2D[],
  angle: number,      // 스위프 각도 (도)
  spacing: number     // 라인 간격 (미터)
): Line[] => {
  const angleRad = toRadians(angle)
  const centroid = calculatePolygonCentroid(polygon)

  // 스위프 방향의 수직 방향 (라인이 배치되는 방향)
  const perpAngle = angleRad + Math.PI / 2

  // 폴리곤을 수직 방향에 투영하여 범위 계산
  let minProj = Infinity
  let maxProj = -Infinity

  for (const point of polygon) {
    const relX = point.x - centroid.x
    const relY = point.y - centroid.y
    const proj = relX * Math.cos(perpAngle) + relY * Math.sin(perpAngle)
    minProj = Math.min(minProj, proj)
    maxProj = Math.max(maxProj, proj)
  }

  // 라인 생성
  const lines: Line[] = []
  const numLines = Math.ceil((maxProj - minProj) / spacing) + 1

  for (let i = 0; i < numLines; i++) {
    const offset = minProj + i * spacing

    // 라인 중심점 계산
    const centerX = centroid.x + offset * Math.cos(perpAngle)
    const centerY = centroid.y + offset * Math.sin(perpAngle)

    // 충분히 긴 라인 생성
    const dx = diagonal * Math.cos(angleRad)
    const dy = diagonal * Math.sin(angleRad)

    lines.push({
      start: { x: centerX - dx, y: centerY - dy },
      end: { x: centerX + dx, y: centerY + dy }
    })
  }

  return lines
}

5. 교차 세그먼트 계산

각 스위프 라인과 폴리곤 경계의 교차점을 계산하여 실제 비행할 세그먼트를 추출합니다.

const calculateIntersectionSegments = (
  sweepLines: Line[],
  polygon: Point2D[],
  angle: number
): Segment[] => {
  const segments: Segment[] = []

  for (let i = 0; i < sweepLines.length; i++) {
    const line = sweepLines[i]

    // 라인과 폴리곤의 모든 교차점 계산
    const intersections = linePolygonIntersection(line, polygon)

    if (intersections.length >= 2) {
      // 교차점을 스위프 방향으로 정렬
      intersections.sort((a, b) =>
        projectOntoAxis(a, angle) - projectOntoAxis(b, angle)
      )

      // 첫 번째와 마지막 교차점이 세그먼트
      segments.push({
        start: intersections[0],
        end: intersections[intersections.length - 1],
        lineIndex: i
      })
    }
  }

  return segments
}

6. Boustrophedon 연결

세그먼트들을 지그재그 패턴으로 연결하고, 각 구간에 살포 여부(sprayOn)를 표시합니다.

const connectSegmentsWithSprayInfo = (segments: Segment[]): Waypoint[] => {
  const waypoints: Waypoint[] = []
  let reverseDirection = false

  // 라인 인덱스별로 그룹화 후 순서대로 연결
  for (const lineIndex of sortedLineIndices) {
    const lineSegments = lineGroups.get(lineIndex)!

    // 이전 라인에서 현재 라인으로 턴할 때 (살포 OFF)
    if (!isFirstSegment) {
      const turnEndPoint = reverseDirection ? firstSeg.end : firstSeg.start
      waypoints.push({
        lat: turnEndPoint.y,
        lng: turnEndPoint.x,
        sprayOn: false  // 턴 구간은 살포 OFF
      })
    }

    // 세그먼트 연결 (살포 ON)
    if (reverseDirection) {
      // 역방향: end → start
      waypoints.push({ ...seg.end, sprayOn: true })
      waypoints.push({ ...seg.start, sprayOn: true })
    } else {
      // 정방향: start → end
      waypoints.push({ ...seg.start, sprayOn: true })
      waypoints.push({ ...seg.end, sprayOn: true })
    }

    reverseDirection = !reverseDirection  // 방향 전환
  }

  return waypoints
}

---

구현 코드

전체 흐름 (메인 함수)

export const generateCoveragePathWithSpray = (
  polygonCoords: Coordinate[],    // 폴리곤 좌표 (WGS84)
  dronePosition: Coordinate,       // 드론 시작 위치
  options: PathPlanningOptions = {}
): Waypoint[] => {
  const {
    swathWidth = 5.0,        // 살포 폭 (미터)
    overlapRatio = 0.1,      // 오버랩 비율 (10%)
    boundaryOffset = 2.5     // 경계 오프셋 (살포폭/2)
  } = options

  // 1. WGS84 → 미터 좌표 변환
  const origin = polygonCoords[0]
  const polygonMeters = polygonCoords.map(c => latLngToMeters(c, origin))
  const startPointMeters = latLngToMeters(dronePosition, origin)

  // 2. 경계 오프셋 적용 (폴리곤 수축)
  const shrunkPolygon = shrinkPolygon(polygonMeters, boundaryOffset)

  // 3. 좌표 정규화
  const normResult = normalizeCoordinates(
    shrunkPolygon,
    startPointMeters,
    COORDINATE_SCALE_FACTOR
  )

  // 4. 유효 라인 간격 계산
  const effectiveSpacing = swathWidth * (1 - overlapRatio) * COORDINATE_SCALE_FACTOR

  // 5. 최적 스위프 각도 찾기
  const optimalAngle = findOptimalSweepAngle(
    normResult.normalizedPolygon,
    effectiveSpacing
  )

  // 6. 스위프 라인 생성
  const sweepLines = generateSweepLines(
    normResult.normalizedPolygon,
    optimalAngle,
    effectiveSpacing
  )

  // 7. 교차 세그먼트 계산
  const segments = calculateIntersectionSegments(
    sweepLines,
    normResult.normalizedPolygon,
    optimalAngle
  )

  // 8. Boustrophedon 패턴으로 연결
  const waypointsWithSpray = connectSegmentsWithSprayInfo(segments)

  // 9. 시작점 기준 최적화 (경로 뒤집기 여부)
  const optimizedWaypoints = optimizeForStartPoint(
    waypointsWithSpray,
    normResult.normalizedStartPoint
  )

  // 10. WGS84로 역변환
  const finalWaypoints = optimizedWaypoints.map(wp => {
    const denormalized = denormalizeCoordinates(wp, normResult)
    const wgs84 = metersToLatLng(denormalized, origin)
    return {
      lat: wgs84.lat,
      lng: wgs84.lng,
      sprayOn: wp.sprayOn
    }
  })

  return finalWaypoints
}

유틸리티 함수들

// 두 점 사이 거리
const distance2D = (p1: Point2D, p2: Point2D): number => {
  const dx = p2.x - p1.x
  const dy = p2.y - p1.y
  return Math.sqrt(dx * dx + dy * dy)
}

// 폴리곤 면적 계산 (Shoelace formula)
const calculatePolygonArea = (polygon: Point2D[]): number => {
  let area = 0
  for (let i = 0; i < polygon.length; i++) {
    const j = (i + 1) % polygon.length
    area += polygon[i].x * polygon[j].y
    area -= polygon[j].x * polygon[i].y
  }
  return Math.abs(area / 2)
}

// 폴리곤 중심점 계산
const calculatePolygonCentroid = (polygon: Point2D[]): Point2D => {
  let sumX = 0, sumY = 0
  for (const point of polygon) {
    sumX += point.x
    sumY += point.y
  }
  return {
    x: sumX / polygon.length,
    y: sumY / polygon.length
  }
}

// 직선-폴리곤 교차점 계산
const linePolygonIntersection = (line: Line, polygon: Point2D[]): Point2D[] => {
  const intersections: Point2D[] = []

  for (let i = 0; i < polygon.length; i++) {
    const j = (i + 1) % polygon.length
    const edge = { start: polygon[i], end: polygon[j] }

    const intersection = lineIntersection(line, edge)
    if (intersection) {
      intersections.push(intersection)
    }
  }

  return intersections
}

---

시각적 예시

사각형 농지

입력:                        출력 (스위프 각도 0°):
┌──────────────┐            ┌──────────────┐
│              │            │ →→→→→→→→→→→→ │ spray: ON
│              │     →      │             ↓│ spray: OFF (턴)
│              │            │ ←←←←←←←←←←←← │ spray: ON
│              │            │↓             │ spray: OFF (턴)
│              │            │ →→→→→→→→→→→→ │ spray: ON
└──────────────┘            └──────────────┘

경계 오프셋 적용

   원본 경계         수축된 경계 (비행 경로)
┌──────────────┐       ┌──────────────┐
│              │       │  ┌────────┐  │
│              │   →   │  │ 실제   │  │
│              │       │  │ 비행   │  │
│              │       │  │ 영역   │  │
│              │       │  └────────┘  │
└──────────────┘       └──────────────┘
경계 밖 살포 방지    offset = swathWidth / 2

---

파라미터 설명

라인 간격 계산

effectiveSpacing = swathWidth × (1 - overlapRatio)
                 = 5.0m × (1 - 0.1)
                 = 4.5m

예상 비행 시간

const estimatedTime = totalDistance / DRONE_AVG_SPEED
// 예: 500m / 5m/s = 100초

---

주의사항

1. 좌표계 주의: WGS84(GPS)와 미터 좌표계 변환 시 위도에 따른 경도 스케일 보정 필요
2. 폴리곤 방향: CW/CCW에 따라 법선 벡터 방향이 달라짐
3. 오목 폴리곤: 스위프 라인이 폴리곤과 여러 번 교차할 수 있음 (여러 세그먼트 생성)
4. 수축 실패: 너무 좁은 영역이나 복잡한 형태는 수축 후 유효하지 않을 수 있음

---

참고 자료

• Coverage Path Planning Method for Agricultural Spraying UAV in Arbitrary Polygon Area
• Optimal Polygon Decomposition for UAV Survey Coverage Path Planning