二维坐标形状按偏移量K扩张收缩的算法实现问题咨询

问题说明 #

需求为实现二维对象按指定偏移量K完成扩张或收缩，给定原始坐标点序列为{ {5,0}, {0,0}, {0,-5}, {5,-5}, {5,-10}, {0,-10} }（黄色标记形状），目标偏移量K=1，预期效果如下：

最初采用的实现思路为计算形状中心点，再基于中心点对每个坐标做缩放调整，该方案仅适用于正方形这类中心对称的闭合形状，针对非对称形状、开放形状无法得到正确结果。原有错误实现代码如下：

void myFun() {
        std::vector<std::pair<double, double>> co, CO;
        co = { { {5,0}, {0,0}, {0,-5}, {5,-5}, {5,-10}, {0,-10} } };
        double x = 0, y = 0;
        double n = co.size();
        for (auto it : co) {
            x += it.first; y += it.second;
        }
        std::pair<double, double> o = { x / n, y / n };
        int K = 1;
        for (auto it : co) {
            std::pair<double, double> inc = { (it.first - o.first) * K, (it.second - o.second) * K };
            CO.push_back({ o.first - inc.first, o.second - inc.second });
        }
        reverse(CO.begin(), CO.end());
        for (auto it: CO) {}
    }

错误代码运行得到的形状效果如下：

错误原因 #

原有方案本质是以所有顶点的质心为原点做整体几何缩放，和「形状所有边沿垂直方向偏移固定距离K」的需求完全不符：

• 缩放操作中，顶点位移距离和该点到质心的距离成正比，离质心越远位移越大，无法保证所有边的偏移距离一致
• 对于非中心对称形状、开放折线，缩放必然导致形状扭曲，和预期偏移效果偏差极大

正确实现逻辑 #

二维形状的等距偏移（也叫轮廓偏移、缓冲生成）的标准实现步骤如下：

1. 逐段遍历相邻顶点组成的边，为每条边计算垂直于边方向、长度为K的单位法向量，方向根据扩张/收缩需求选择，将原边的两个端点沿法向量平移K距离，得到和原边平行的偏移边
2. 对相邻的两条偏移边求交点，该交点就是偏移后形状的对应顶点
3. 特殊场景处理：
   • 开放折线的首尾两个顶点无相邻边，直接沿所在边的法向量平移K即可，不需要求交
   • 闭合多边形需要额外处理最后一条边和第一条边的交点，形成闭合轮廓
   • 偏移量过大时可能出现边自相交，复杂场景需要额外引入多边形裁剪逻辑剔除自交区域

针对当前开放折线场景，修正后的可运行核心代码如下：

#include <vector>
#include <cmath>
#include <utility>

using Point = std::pair<double, double>;

// 计算两点欧氏距离
inline double calc_dist(const Point& a, const Point& b) {
    double dx = b.first - a.first;
    double dy = b.second - a.second;
    return std::sqrt(dx * dx + dy * dy);
}

// 计算两条无限直线的交点，入参为两条直线上各自的两个点
Point calc_line_intersect(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    double x1 = p1.first, y1 = p1.second;
    double x2 = p2.first, y2 = p2.second;
    double x3 = p3.first, y3 = p3.second;
    double x4 = p4.first, y4 = p4.second;

    double denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    double t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
    return {x1 + t * (x2 - x1), y1 + t * (y2 - y1)};
}

/**
 * @brief 对二维折线/多边形做等距偏移
 * @param src 原始顶点序列
 * @param offset_K 偏移距离
 * @param is_outward true为向外扩张，false为向内收缩
 * @param is_closed 是否为闭合多边形
 * @return 偏移后的顶点序列
 */
std::vector<Point> shape_offset(const std::vector<Point>& src, double offset_K, bool is_outward, bool is_closed = false) {
    std::vector<Point> res;
    int pt_count = src.size();
    if (pt_count < 2) return res;

    double dir = is_outward ? 1.0 : -1.0;
    std::vector<std::pair<Point, Point>> offset_edges;

    // 生成所有偏移后的平行边
    int edge_count = is_closed ? pt_count : pt_count - 1;
    for (int i = 0; i < edge_count; i++) {
        const Point& p1 = src[i];
        const Point& p2 = is_closed && i == pt_count -1 ? src[0] : src[i+1];
        double dx = p2.first - p1.first;
        double dy = p2.second - p1.second;
        double edge_len = calc_dist(p1, p2);
        // 垂直于边的单位法向量
        double nx = (-dy / edge_len) * offset_K * dir;
        double ny = (dx / edge_len) * offset_K * dir;
        offset_edges.emplace_back(
            Point{p1.first + nx, p1.second + ny},
            Point{p2.first + nx, p2.second + ny}
        );
    }

    if (is_closed) {
        // 闭合多边形：所有顶点都是相邻偏移边的交点
        for (int i = 0; i < edge_count; i++) {
            int next_i = (i + 1) % edge_count;
            res.push_back(calc_line_intersect(
                offset_edges[i].first, offset_edges[i].second,
                offset_edges[next_i].first, offset_edges[next_i].second
            ));
        }
    } else {
        // 开放折线：首点取第一条偏移边起点，尾点取最后一条偏移边终点，中间点取相邻边交点
        res.push_back(offset_edges.front().first);
        for (int i = 0; i < edge_count - 1; i++) {
            res.push_back(calc_line_intersect(
                offset_edges[i].first, offset_edges[i].second,
                offset_edges[i+1].first, offset_edges[i+1].second
            ));
        }
        res.push_back(offset_edges.back().second);
    }

    return res;
}

// 调用示例
void myFun() {
    std::vector<Point> origin_pts = { {5,0}, {0,0}, {0,-5}, {5,-5}, {5,-10}, {0,-10} };
    double K = 1;
    // 开放折线向外偏移1单位
    std::vector<Point> offset_pts = shape_offset(origin_pts, K, true, false);
}

• 上述代码针对题目给出的开放折线场景，运行后可得到和预期一致的偏移结果
• 若需要处理闭合多边形，只需要将调用参数is_closed设为true即可
• 若需支持大偏移量下的无自相交效果，可在生成偏移顶点后增加自相交裁剪步骤，常规业务场景下上述核心逻辑可满足需求

内容的提问来源于stack exchange，提问作者Perdente