라인스위핑

라인 스위핑(Line Sweeping)은 주로 기하학적 문제를 해결하는 데 사용되는 알고리즘 기법입니다. 이 방법은 주어진 입력을 "스위프"하는 가상의 수직선(또는 수평선)을 사용하여 문제를 해결합니다. 이 기법은 주로 교차점 찾기, 다각형의 면적 계산, 그리고 여러 기하학적 객체의 관계를 분석하는 데 사용됩니다.

라인 스위핑의 기본 아이디어는 다음과 같습니다:

모든 이벤트를 정렬합니다. 이벤트는 일반적으로 선분의 시작점과 끝점, 또는 다른 기하학적 객체의 중요한 점들입니다.
스위프 라인을 이동시키면서 현재 상태를 유지하고, 각 이벤트에 대해 필요한 작업을 수행합니다.
예제: 두 선분의 교차점 찾기
아래는 C++로 작성된 간단한 라인 스위핑 알고리즘의 예제입니다. 이 코드는 두 선분의 교차점을 찾는 기능을 수행합니다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

struct Point {
    int x, y;
};

struct Segment {
    Point p1, p2;
};

bool operator<(const Segment& s1, const Segment& s2) {
    return std::min(s1.p1.x, s1.p2.x) < std::min(s2.p1.x, s2.p2.x);
}

bool doIntersect(Segment s1, Segment s2) {
    // 교차 여부를 판단하는 함수 (단순화된 예)
    // 실제 구현에서는 더 복잡한 기하학적 계산이 필요합니다.
    return (s1.p1.x < s2.p2.x && s2.p1.x < s1.p2.x);
}

std::vector<std::pair<Segment, Segment>> findIntersections(const std::vector<Segment>& segments) {
    std::set<Segment> activeSegments;
    std::vector<std::pair<Segment, Segment>> intersections;

    // 모든 선분을 정렬하여 이벤트를 생성
    std::vector<Segment> events = segments;
    std::sort(events.begin(), events.end());

    for (const auto& seg : events) {
        // 현재 선분을 active set에 추가
        activeSegments.insert(seg);

        // 교차점 찾기
        for (const auto& activeSeg : activeSegments) {
            if (activeSeg != seg && doIntersect(activeSeg, seg)) {
                intersections.emplace_back(activeSeg, seg);
            }
        }
    }

    return intersections;
}

int main() {
    std::vector<Segment> segments = {
        {{1, 1}, {4, 4}},
        {{1, 4}, {4, 1}},
        {{5, 5}, {6, 6}}
    };

    auto intersections = findIntersections(segments);

    for (const auto& intersection : intersections) {
        std::cout << "Intersection between segments: ("
                  << intersection.first.p1.x << ", " << intersection.first.p1.y << ") and ("
                  << intersection.second.p1.x << ", " << intersection.second.p1.y << ")\n";
    }

    return 0;
}