用C++实现Weiler-Atherton

Weiler-Atherton算法是一个用于计算多边形交和差的算法。下面是一个用C++实现Weiler-Atherton算法的示例代码：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 点结构体
struct Point {
    double x;
    double y;
    Point(double x, double y) : x(x), y(y) {}
};

// 线段结构体
struct Segment {
    Point start;
    Point end;
    Segment(Point start, Point end) : start(start), end(end) {}
};

// 计算两个点之间的距离
double distance(Point p1, Point p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

// 判断两个点是否相等
bool isEqual(Point p1, Point p2) {
    return distance(p1, p2) < 1e-5;
}

// 判断点是否在线段上
bool isOnSegment(Segment s, Point p) {
    double d1 = distance(s.start, p);
    double d2 = distance(s.end, p);
    double d = distance(s.start, s.end);
    return isEqual(d1 + d2, d);
}

// 计算两线段的交点
Point getIntersection(Segment s1, Segment s2) {
    double a1 = s1.end.y - s1.start.y;
    double b1 = s1.start.x - s1.end.x;
    double c1 = s1.end.x * s1.start.y - s1.start.x * s1.end.y;
    double a2 = s2.end.y - s2.start.y;
    double b2 = s2.start.x - s2.end.x;
    double c2 = s2.end.x * s2.start.y - s2.start.x * s2.end.y;
    double det = a1 * b2 - a2 * b1;
    if (fabs(det) < 1e-5) {
        return Point(0, 0);
    }
    double x = (b1 * c2 - b2 * c1) / det;
    double y = (a2 * c1 - a1 * c2) / det;
    Point p(x, y);
    if (isOnSegment(s1, p) && isOnSegment(s2, p)) {
        return p;
    }
    return Point(0, 0);
}

// 根据交点切割多边形
vector<Point> clipPolygon(vector<Point> polygon, Segment s) {
    vector<Point> result;
    for (int i = 0; i < polygon.size(); i++) {
        Point p1 = polygon[i];
        Point p2 = polygon[(i + 1) % polygon.size()];
        Segment seg(p1, p2);
        Point intersection = getIntersection(seg, s);
        if (intersection.x != 0 || intersection.y != 0) {
            result.push_back(intersection);
        }
        if (isOnSegment(seg, p2)) {
            result.push_back(p2);
        }
    }
    return result;
}

// 判断点是否在多边形内部
bool isInsidePolygon(Point p, vector<Point> polygon) {
    Segment ray(p, Point(100000, p.y));
    vector<Point> intersections;
    for (int i = 0; i < polygon.size(); i++) {
        Point p1 = polygon[i];
        Point p2 = polygon[(i + 1) % polygon.size()];
        Segment seg(p1, p2);
        Point intersection = getIntersection(ray, seg);
        if (intersection.x != 0 || intersection.y != 0) {
            intersections.push_back(intersection);
        }
    }
    if (intersections.size() % 2 == 0) {
        return false;
    }
    return true;
}

// 计算多边形交
vector<Point> getIntersection(vector<Point> polygon1, vector<Point> polygon2) {
    vector<Point> result;
    for (int i = 0; i < polygon1.size(); i++) {
        Point p1 = polygon1[i];
        Point p2 = polygon1[(i + 1) % polygon1.size()];
        Segment seg(p1, p2);
        vector<Point> clippedPolygon = clipPolygon(polygon2, seg);
        if (clippedPolygon.size() > 0) {
            clippedPolygon.push_back(p2);
            if (result.size() > 0 && !isEqual(result.back(), clippedPolygon.front())) {
                result.push_back(clippedPolygon.front());
            }
            result.insert(result.end(), clippedPolygon.begin(), clippedPolygon.end());
        } else if (isInsidePolygon(p1, polygon2)) {
            result.push_back(p1);
        }
    }
    return result;
}

// 计算多边形差
vector<Point> getDifference(vector<Point> polygon1, vector<Point> polygon2) {
    vector<Point> result;
    for (int i = 0; i < polygon1.size(); i++) {
        Point p1 = polygon1[i];
        Point p2 = polygon1[(i + 1) % polygon1.size()];
        Segment seg(p1, p2);
        vector<Point> clippedPolygon = clipPolygon(polygon2, seg);
        if (clippedPolygon.size() == 0) {
            result.push_back(p1);
        } else if (!isEqual(p1, clippedPolygon.front())) {
            result.push_back(p1);
        }
    }
    return result;
}

// 输出点坐标
void printPoints(vector<Point> points) {
    for (int i = 0; i < points.size(); i++) {
        cout << "(" << points[i].x << ", " << points[i].y << ") ";
    }
    cout << endl;
}

int main() {
    vector<Point> polygon1;
    polygon1.push_back(Point(0, 0));
    polygon1.push_back(Point(5, 0));
    polygon1.push_back(Point(5, 5));
    polygon1.push_back(Point(0, 5));
    vector<Point> polygon2;
    polygon2.push_back(Point(1, 1));
    polygon2.push_back(Point(6, 1));
    polygon2.push_back(Point(6, 6));
    polygon2.push_back(Point(1, 6));
    cout << "Polygon 1: ";
    printPoints(polygon1);
    cout << "Polygon 2: ";
    printPoints(polygon2);
    vector<Point> intersection = getIntersection(polygon1, polygon2);
    cout << "Intersection: ";
    printPoints(intersection);
    vector<Point> difference = getDifference(polygon1, polygon2);
    cout << "Difference: ";
    printPoints(difference);
    return 0;
}

上述代码实现了Weiler-Atherton算法的基本功能，包括计算多边形交和差。其中，clipPolygon函数用于根据线段切割多边形，isInsidePolygon函数用于判断点是否在多边形内部，getIntersection函数用于计算多边形交，getDifference函数用于计算多边形差。通过这些函数的组合，可以实现Weiler-Atherton算法的完整实现。