在项目中有用线段切割多边形的需求。所以在网上找到了一篇比较好的实现。
  原博客地址：多边形切割

1. 求出多边形和线段的所有交点。把多边形本身的点，和遍历到的交点，按遍历的顺序放入数组 points 中。
2. 找到和第一个交点最近的交点（第二个或是最后一个，因为多边形可能有线段交叉的情况），判断从第一个交点开始，线段是位于多边形内部还是外部。
3. 从多边形的第一个交点开始遍历 points。如果多边形被切割，多边形一定从交点处被切分，两个新的多边形都在交点处有个顶点，该顶点要加入两个多边形中。对于非交点的顶点，判断是属于新的多边形还是旧的多边形，加入对应的数组中。

C++ 代码

  用 c++ 代码实现了一遍。项目中多边形都是用 int 表示的，所以这里的 point、line 都是用 int 实现。cutPolygon 类是算法实现的核心，不需要太过关注其它类。

头文件

#include <vector>
#include <climits>
#include <cfloat>
#include <cmath>

using namespace std;

class point {
public:
    point() : _x(INT_MIN), _y(INT_MIN) {}
    point(int x, int y) : _x(x), _y(y) {}
//    point(const point& p) : _x(p._x), _y(p._y) {} // 不用写，会默认生成

    point       operator+(const point& p) const {
        return point(_x + p._x, _y + p._y);
    }

    point       operator-(const point& p) const {
        return point(_x - p._x, _y - p._y);
    }

    void        operator+=(const point& p) {
        _x += p._x; _y += p._y;
    }

    void        operator-=(const point& p) {
        _x -= p._x; _y -= p._y;
    }

    bool        operator==(const point& p) const {
        return p._x == _x && p._y == _y;
    }

    bool        operator!=(const point& p) const {
        return p._x != _x || p._y != _y;
    }

    bool        operator<(const point& p) const {
        return _x < p._x || (_x == p._x && _y < p._y);
    }

    int         x() const { return _x; }
    int         y() const { return _y; }

    void        setX(int x) { _x = x; }
    void        setY(int y) { _y = y; }

    double      distance(const point& p);

private:
    int         _x;
    int         _y;
};

const double EPSINON = 0.000001;

class pointF {
public:
    pointF(double x = DBL_MIN, double y = DBL_MIN) : _x(x), _y(y) {}
    pointF(const point& p) : _x(p.x()), _y(p.y()) {}

    double      x() const { return _x; }
    double      y() const { return _y; }
    bool        valid() const { return _x != DBL_MIN && _y != DBL_MIN; }
    point       toPoint() const;

    bool        operator==(const point& p) {
        return fabs(p.x() - _x) < EPSINON && fabs(p.y() - _y) < EPSINON;
    }

    bool        operator==(const pointF& p) {
        return fabs(p.x() - _x) < EPSINON && fabs(p.y() - _y) < EPSINON;
    }

private:
    double      _x, _y;
};

class line {
public:
    line() {}
    line(const point& p1, const point& p2) : _p1(p1), _p2(p2) {}
    line(int x1, int y1, int x2, int y2) : _p1(x1, y1), _p2(x2, y2) {}

    point       p1() const { return _p1; }
    point       p2() const { return _p2; }

private:
    point       _p1, _p2;
};

class polygon : public vector<point> {
public:
    polygon(unsigned size = 0) : vector<point>(size) {}
    polygon(const vector<point>& vec) {
        reserve(vec.size());
        insert(end(), vec.begin(), vec.end());
    }
};

class cutPolygon
{
public:
    cutPolygon() {};
    // 线段对多边形进行切割，返回多边形数组，如果没有被切割，返回空
    vector<polygon>     lineCutPolygon(line& l, polygon& poly);

    // 求 ab 和 ac 的叉积
    static int      abCrossAc(const point& a, const point& b, const point& c) {
        return cross(b.x() - a.x(), b.y() - a.y(), c.x() - a.x(), c.y() - a.y());
    }

    static int      cross(int x1, int y1, int x2, int y2) {
        return x1 * y2 - x2 * y1; // 用 int 可能会越界
    }

    static int      dot(int x1, int y1, int x2, int y2) {
        return x1 * x2 + y1 * y2;
    }

    // 判断 p 是否在 l 上。必要条件：p 和 l 在同一条直线上。 >0 不在，=0 与端点重合，<0 在
    static int      pointOnLine(const point& p, const line& l) {
        return dot(l.p1().x() - p.x(), l.p1().y() - p.y(), l.p2().x() - p.x(), l.p2().y() - p.y());
    }

private:
    //返回值：[n,p] n:0相交，1在共有点，-1不相交  p:交点
    pair<int, point>    lineCrossPoint(line l1, line l2);
    // 点p发出的右射线和线段p1-p2的关系, -1:不相交，0:相交，1：点在线段上
    int                 rayPointToLine(pointF &p, pointF p1, pointF p2);
    // -1:在多边形外部, 0:在多边形内部, 1:在多边形边线内, 2:跟多边形某个顶点重合
    int                 isPointInPolygon(pointF p, polygon &poly);
};

源文件

#include "cutPolygon.h"
#include <iostream>

cutPolygon::cutPolygon()
{

}

pair<int, point> cutPolygon::lineCrossPoint(line l1, line l2)
{
    point a = l1.p1(), b = l1.p2(), c = l2.p1(), d = l2.p2();
    /* 向量 axb
     * 叉积小于0表示:向量b在向量a的顺时针方向
     * 大于0表示向量b在向量a的逆时针方向
     * 等于0表示向量a与向量b平行
     */
    int d1 = abCrossAc(a, b, c);
    int d2 = abCrossAc(a, b, d);
    int d3 = abCrossAc(c, d, a);
    int d4 = abCrossAc(c, d, b);

    if (d1 == 0 && d2 == 0)
        return {-1, point()};

    // d1 * d2 小于0 表示点 c 和 d 在线段 ab(l1) 的两侧
    // 规范相交
    if (d1 * d2 < 0 && d3 * d4 < 0) {
        point res;
        res.setX((c.x() * d2 - d.x() * d1) / (d2 - d1));
        res.setY((c.y() * d2 - d.y() * d1) / (d2 - d1));
        return {0, res};
    }

    // 不规范相交
    // c 在 线段 l1 上, 并且 d 不在
    if (d1 == 0 && pointOnLine(c, l1) <= 0) {
        return {1, c};
    }

    // d 在线段 l1 上
    if (d2 == 0 && pointOnLine(d, l1) <= 0) {
        return {1, d};
    }

    // a 在线段 l2 上, 结合后面调用，所以返回 0
    if (d3 == 0 && pointOnLine(a, l2) <= 0) {
        return {0, a};
    }

    if (d4 == 0 && pointOnLine(b, l2) <= 0) {
        return {0, b};
    }

    // 不相交
    return {-1, point()};
}

int cutPolygon::rayPointToLine(pointF &p, pointF p1, pointF p2)
{
    double maxX = max(p1.x(), p2.x());
    double minY = min(p1.y(), p2.y());
    double maxY = max(p1.y(), p2.y());

    // 射线与边无交点的情况, （射线与下端点相交也当作无交点，为了处理和多边形顶点相交的情况）
    if (p.y() <= minY || p.y() > maxY || p.x() > maxX) {
        return -1;
    }

    double x = p1.x() + ((p2.x() - p1.x()) / (p2.y() - p1.y())) * (p.y() - p1.y());

    if (x > p.x())
        return 0;

    if (x == p.x())
        return 1;
    return -1;
}

int cutPolygon::isPointInPolygon(pointF p, polygon &poly)
{
    int count = 0;
    for (unsigned i = 0; i < poly.size(); ++i) {
        if (p == poly[i])
            return 2;

        point pa = poly[i];
        point pb = poly[0];
        if (i < poly.size() - 1) {
            pb = poly[i + 1];
        }
        if (pa.y() == pb.y()) // 跳过和 x 轴平行的边
            continue;
        int re = rayPointToLine(p, pa, pb);
        if (re == 1)
            return 1;
        if (re == 0)
            ++count;
    }
    if (count % 2)
        return 0;
    return -1;
}

vector<polygon> cutPolygon::lineCutPolygon(line &l, polygon &poly)
{
    vector<polygon> res;
    vector<point> points;
    vector<unsigned> pointIndex;

    for (unsigned i = 0; i < poly.size(); ++i) {
        points.push_back(poly[i]);

        point a = poly[i];
        point b = poly[0];
        if (i < poly.size() - 1)
            b = poly[i + 1];

        auto c = lineCrossPoint(l, line(a, b));
        if (c.first == 0) { // 和线段相交
            pointIndex.push_back(points.size());
            points.push_back(c.second);
        } else if (c.first == 1) {
            if (c.second == a) {
                pointIndex.push_back(points.size() - 1);
            } else {
                pointIndex.push_back(points.size());
            }
        }
    }

    if (pointIndex.size() < 2)
        return res;

    point cp0 = points[pointIndex[0]];
    point cp1 = points[pointIndex[1]];

    int r = isPointInPolygon(pointF(1.0 * (cp0.x() + cp1.x()) / 2, 1.0 * (cp0.y() + cp1.y()) / 2), poly);
    bool inPoly = (r >= 0);
    point last = points[pointIndex[pointIndex.size() - 1]];
    // 找到距离当前交点最近的交点, (多边形可能有交叉的情况)
    if (pointIndex.size() > 2 && cp0.distance(cp1) > cp0.distance(last)) {
        cp1 = last;
        r = isPointInPolygon(pointF(1.0 * (cp0.x() + cp1.x()) / 2, 1.0 * (cp0.y() + cp1.y()) / 2), poly);
        inPoly = (r < 0);
    }

    bool firstInPolygon = inPoly;

    unsigned index = 0;
    unsigned startIndex = pointIndex[index];
    polygon oldPoints, newPoints;
    unsigned count = 0;

    oldPoints.push_back(points[startIndex]);
    if (inPoly)
        newPoints.push_back(points[startIndex]);

    index++;
    count++;
    startIndex++;

    while (count < points.size()) {
        if (startIndex == points.size())
            startIndex = 0;
        point p = points[startIndex];
        if (startIndex == pointIndex[index]) {
            index++;
            if (index >= pointIndex.size())
                index = 0;
            if (inPoly) {
                newPoints.push_back(p);
                res.push_back(newPoints);
                newPoints.clear();
            } else {
                newPoints.clear();
                newPoints.push_back(p);
            }
            oldPoints.push_back(p);
            if (!inPoly && count < points.size() - 1) {
                point p1 = points[pointIndex[index]];
                pointF midPoint(1.0 * (p.x() + p1.x()) / 2, 1.0 * (p.y() + p1.y()) / 2);
                int r = isPointInPolygon(midPoint, poly);
                inPoly = (r >= 0);
            } else {
                inPoly = !inPoly;
            }
        } else {
            if (inPoly)
                newPoints.push_back(p);
            else
                oldPoints.push_back(p);
        }
        startIndex++;
        count++;
    }
    if (inPoly) {
        if (!firstInPolygon && newPoints.size() > 1) {
            newPoints.push_back(points[pointIndex[0]]);
            res.push_back(newPoints);
        } else {
            for (unsigned i = 0; i < newPoints.size(); ++i) {
                oldPoints.push_back(newPoints[i]);
            }
        }
    }
    res.push_back(oldPoints);
    return res;
}

point pointF::toPoint() const
{
    if (valid()) {
        int x = static_cast<int>(round(_x));
        int y = static_cast<int>(round(_y));
        return point(x, y);
    } else {
        return point();
    }
}

double point::distance(const point &p)
{
    double dx = _x - p.x();
    double dy = _y - p.y();
    return sqrt(dx * dx + dy * dy);
}