Monotone Polygon Triangulation

단조 다각형 삼각분할(Monotone Polygon Triangulation)은 주어진 단조 다각형을 서로 겹치지 않는 $N - 2$개의 삼각형으로 분할하는 효율적인 기하 알고리즘이다. 일반적인 단순 다각형의 삼각분할은 $O(N \log N)$ 이상의 시간 복잡도가 소요되지만, 단조 다각형은 이미 좌/우 체인 구조로 정렬되어 있다는 특성을 활용해 stack 기반으로 $O(N)$ 시간 만에 고속 삼각분할을 수행할 수 있다. Complex Polygon을 여러 개의 단조 다각형으로 나누는 Monotone Partitioning 단계의 후속 처리 알고리즘으로 널리 활용된다.

Douglas-Peucker 알고리즘을 사용해 한반도 윤곽선을 단조 다각형으로 근사(백두산 부근의 한 점을 수동으로 제거해야 monotonic 해짐)한 후 알고리즘 적용

preprocess_monotone_polygon() (전처리)

• 방향성 보정: 입력 다각형의 넓이를 계산하여 시계 방향(CW)이면 반시계 방향(CCW)으로 반전
• 최상단/최하단 정점 탐색: Y좌표가 가장 높은 정점(top)과 가장 낮은 정점(bot)을 찾기
• 체인 분리:
  • top에서 bot으로 이어지는 경로는 왼쪽 체인(chain = 0)으로 지정
  • bot에서 top으로 이어지는 경로는 오른쪽 체인(chain = 1)으로 지정
• 모든 정점을 Y축 내림차순으로 정렬

triangulate_monotone_polygon() (삼각분할 메인) 스택(Stack)을 활용하여 정점을 위에서부터 하나씩 처리

• Case 1: 다른 체인의 정점을 만났거나 마지막 정점인 경우
  • 스택에 남아있는 정점들과 현재 정점을 연결하여 삼각형을 생성(Flush)
  • 처리 후 현재 정점과 이전 탑 정점을 스택에 다시 푸시
• Case 2: 같은 체인의 정점을 만난 경우
  • ccw()를 통해 다각형 내부 방향으로 볼록하게 꺾이는지 검사
  • 조건(왼쪽 체인은 반시계 방향, 오른쪽 체인은 시계 방향)을 만족하는 동안 스택에서 pop하며 삼각형을 생성
  • 조건을 만족하지 않는 지점에서 멈추고 현재 정점을 스택에 추가

struct Vertex { 
    double x, y; 
    int id; 
    int chain; // 0: 왼쪽 체인, 1: 오른쪽 체인 
    Vertex(){} 
    Vertex(double x_, double y_, int id_, int c_) : x(x_), y(y_), id(id_), chain(c_) {} 
};  
struct VertexCompare { 
    bool operator()(const Vertex& a, const Vertex& b) const { 
        if (a.y != b.y) return a.y > b.y; // Y축 내림차순 (위에서 아래로)
        return a.x < b.x;     // Y가 같다면 X축 오름차순
    } 
}; 
// 세 점의 CCW 방향성 판별 (p1 -> p2 -> p3)
inline double ccw(const Vertex& p1, const Vertex& p2, const Vertex& p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
void add_triangle_ccw(std::vector<Triple>& triangles,
    const Vertex& a, const Vertex& b, const Vertex& c) {
    const double EPS = 1e-9;
    double val = ccw(a, b, c);
    if (val > EPS) 
        triangles.push_back(Triple(a.id, b.id, c.id));
    else if (val < -EPS) 
        triangles.push_back(Triple(a.id, c.id, b.id)); // b, c 교환
    // == 0: 퇴화 삼각형이므로 추가하지 않음
}
// 1. 단조 다각형 전처리 함수 완성
std::vector<Vertex> preprocess_monotone_polygon(std::vector<Vertex>& pts) { 
    const int n = pts.size(); 
    if (n < 3) return std::vector<Vertex>(); 
    // 다각형 방향성이 CW이면 반전
    double area = 0;
    for (int i = 0; i < n; ++i) 
        area += (pts[i].x * pts[(i + 1) % n].y) - (pts[(i + 1) % n].x * pts[i].y);
    if (area < 0) std::reverse(pts.begin(), pts.end());
    // 최상단 및 최하단 탐색
    int top = 0, bot = 0; 
    for (int i = 1; i < n; ++i) { 
        if (pts[i].y > pts[top].y || 
           (pts[i].y == pts[top].y && pts[i].x < pts[top].x)) top = i; 
        if (pts[i].y < pts[bot].y || 
           (pts[i].y == pts[bot].y && pts[i].x > pts[bot].x)) bot = i; 
    } 
    
    std::vector<Vertex> aligned(n);  
    // CCW 다각형 규칙에 맞춰 명확하게 체인 분리
    // Top -> Bottom 경로는 왼쪽 체인(0),
    // Bottom -> Top 경로는 오른쪽 체인(1)
    int curr = top;
    while (curr != bot) {
        aligned[curr] = Vertex(pts[curr].x, pts[curr].y, pts[curr].id, 0);
        curr = (curr + 1) % n;
    }
    // 최하단 정점은 오른쪽 체인(1)로 강제 지정
    aligned[bot] = Vertex(pts[bot].x, pts[bot].y, pts[bot].id, 1);
    
    curr = (bot + 1) % n;
    while (curr != top) {
        aligned[curr] = Vertex(pts[curr].x, pts[curr].y, pts[curr].id, 1);
        curr = (curr + 1) % n;
    }
    // Y축 내림차순 정렬
    std::sort(aligned.begin(), aligned.end(), VertexCompare()); 
    return aligned;
}

// 2. 단조 다각형 삼각분할 메인 알고리즘 함수
std::vector<Triple> triangulate_monotone_polygon(const std::vector<Vertex>& vtx) {
    std::vector<Triple> triangles;
    const int n = vtx.size();
    if (n < 3) return triangles;

    triangles.reserve(n - 2);
    std::vector<Vertex> Stack; // stack 대신 vector 활용
    
    Stack.push_back(vtx[0]);
    Stack.push_back(vtx[1]);

    for (int i = 2; i < n; ++i) {
        Vertex curr = vtx[i];   
        // 마지막 정점: 스택에 남은 정점 중 첫 번째와 마지막을 제외한 모두와 삼각형 생성;
        if (i == n - 1) { 
            while (Stack.size() > 1) {
                Vertex v2 = Stack.back();
                Stack.pop_back();
                add_triangle_ccw(triangles, Stack.back(), v2, curr);
            }
            break; // 삼각분할 완료
        }        
        // Case 1: 서로 다른 체인의 정점을 만난 경우 (스택 전체 Flush)
        if (curr.chain != Stack.back().chain) {
            Vertex top_v = Stack.back();
            while (Stack.size() > 1) {
                Vertex v2 = Stack.back();
                Stack.pop_back();
                add_triangle_ccw(triangles, Stack.back(), v2, curr);
            }
            Stack.pop_back(); // 마지막 원소 제거
            Stack.push_back(top_v);
            Stack.push_back(curr);
        } 
        // Case 2: 같은 체인의 정점을 만난 경우
        else {
            Vertex last_popped = Stack.back();
            Stack.pop_back();
            while (!Stack.empty()) {
                double turn = ccw(Stack.back(), last_popped, curr);
                bool valid = (curr.chain == 0 && turn > 0) || (curr.chain == 1 && turn < 0);
                
                if (valid) {
                    add_triangle_ccw(triangles, curr, last_popped, Stack.back());
                    last_popped = Stack.back();
                    Stack.pop_back();
                } else break;
            }
            Stack.push_back(last_popped);
            Stack.push_back(curr);
        }
    }
    return triangles;
}