一、问题描述

在做gerber类文件解析的时候遇到的这类问题，里面常见的是使用给一个圆或者一个矩形，沿着一条轨迹线绘制一个更大的形状，这就要求，在每绘制出一条新的轨迹线段的时候，原有的多边形就需要扩展到更大，而每一段线段的外轮廓生成如果也是用多边形合并的话，运算量会太大，因此，需要一个稍微运算量少一些的算法来生成单挑轨迹线的外轮廓。

二、一些简单图形的算法

2.1 圆

圆的是最好处理的，直接求解轨迹线的垂线的起始角度，两边各取半个圆合并起来即可

    int sectorToPolygon(Pointd center,
                        double radius,
                        double start_angle,
                        double end_angle,
                        Polygond &poly,
                        double precision)
    {
        double arc_length = (end_angle - start_angle) * radius;
        int num_segments = std::max(6,
                                    static_cast<int>(arc_length / precision));
        num_segments = std::min(num_segments, 18);
        double angle_increment = (end_angle - start_angle) / num_segments;
        for (int i = 0; i <= num_segments; ++i)
        {
            double angle = start_angle + angle_increment * i;
            double x = center.x + radius * cos(angle);
            double y = center.y + radius * sin(angle);
            poly.vPts.emplace_back(Pointd(x, y));
        }
        return 0;
    }

    int CircleBrushOutline(const Pointd &ptStart,
                           const Pointd &ptEnd,
                           double radius,
                           Polygond &poly,
                           int precision)
    {
        // 计算线段的方向角度
        double angle = atan2(ptEnd.y - ptStart.y, ptEnd.x - ptStart.x);

        // 添加起始圆的半圆轮廓
        sectorToPolygon(ptStart, radius, angle + M_PI / 2, angle + 3 * M_PI / 2, poly, precision);
        sectorToPolygon(ptEnd, radius, angle - M_PI / 2, angle + M_PI / 2, poly, precision);

        return 0;
    }

2.2 矩形

矩形的也比较简单，只要搞明白轨迹线的绘制方向属于哪个象限即可搞定

    int rectangleToPolygon(Pointd topLeft, double width,
                           double height,
                           Polygond &poly)
    {
        poly.vPts.emplace_back(topLeft.x, topLeft.y);
        poly.vPts.emplace_back(topLeft.x + width, topLeft.y);
        poly.vPts.emplace_back(topLeft.x + width, topLeft.y + height);
        poly.vPts.emplace_back(topLeft.x, topLeft.y + height);
        return 0;
    }
    int RectBrushOutline(const Pointd &ptStart,
                         const Pointd &ptEnd,
                         double width,
                         double height,
                         Polygond &poly)
    {
        Vecd vMove = ptEnd - ptStart;
        double angle = atan2(vMove.y, vMove.x);
        angle = angle > 0 ? angle : 2 * M_PI + angle;
        double length = vMove.length();

        Pointd ptHalf = Pointd(width / 2, height / 2);

        if (length < 1e-6) // 原地
        {
            rectangleToPolygon(ptStart - ptHalf, width, height, poly);
        }
        else if (abs(vMove.x) < 1e-6) // 垂直
        {
            Pointd ptTopLeft = Pointd(ptStart.x, min(ptStart.y, ptEnd.y)) - Pointd(width / 2, height / 2);
            rectangleToPolygon(ptTopLeft, width, height + length, poly);
        }
        else if (abs(vMove.y) < 1e-6) // 水平
        {

            Pointd ptTopLeft = Pointd(min(ptStart.x, ptEnd.x), ptStart.y) - Pointd(width / 2, height / 2);
            rectangleToPolygon(ptTopLeft, width + length, height, poly);
        }
        else // 其他位置
        {
            Polygond poly2;
            rectangleToPolygon(ptStart - ptHalf, width, height, poly);
            rectangleToPolygon(ptEnd - ptHalf, width, height, poly2);

            // 根据角度，剔除对应的角点
            if (angle > 0 && angle < M_PI / 2) // 第一象限
            {
                poly.vPts.erase(poly.vPts.begin() + 2);
                poly.vPts.emplace_back(poly2.vPts[1]);
                poly.vPts.emplace_back(poly2.vPts[2]);
                poly.vPts.emplace_back(poly2.vPts[3]);
            }
            else if (angle > M_PI / 2 && angle < M_PI) // 第二象限
            {
                poly.vPts.pop_back();
                poly.vPts.emplace_back(poly2.vPts[2]);
                poly.vPts.emplace_back(poly2.vPts[3]);
                poly.vPts.emplace_back(poly2.vPts[0]);
            }
            else if (angle > M_PI && angle < 3 * M_PI / 2) // 第三象限
            {
                poly.vPts.erase(poly.vPts.begin());
                poly.vPts.emplace_back(poly2.vPts[3]);
                poly.vPts.emplace_back(poly2.vPts[0]);
                poly.vPts.emplace_back(poly2.vPts[1]);
            }
            else // 第四象限
            {
                poly.vPts.erase(poly.vPts.begin());
                poly.vPts.emplace_back(poly2.vPts[0]);
                poly.vPts.emplace_back(poly2.vPts[1]);
                poly.vPts.emplace_back(poly2.vPts[2]);
            }
        }

        return 0;
    }

三、 一般凸多边形

上面两种简单的多边形各有各的算法，但是有没有更常规的针对一般凸多边形的呢？肯定是有的，我想了一段时间，大概主要的方向还是从角度和距离方面来进行判断处理，

正多边形平移

如图，我最终想到的一种办法是，先检查poly1上面的点离移动路径最近和最远的点作为分割点，即G和C点，将多边形分割为GHABC和CDEFG两部分，但是分成两部分之后，具体应该使用那一部分还需要判断，那这时候作线段AI的中垂线，从C或G点取前后相邻的两点，比如取C相邻的B和D点，这两个点谁离中垂线的距离更远，则取其所属的一半多边形为这一侧外轮廓，这里是B更远，则这一侧取GHABC，反之，另一侧的取距离近的平移后的部分为外轮廓，即取CDEFG平移后的KLMNO，则最终的轨迹绘制成的多边形为GHABCKLMNO。