矩形裁剪多边形、矩形裁剪直线

    前段时间因为项目需要进行优化，此时需要用到裁剪算法，因此网上找了下，也看了一些文献啥的，找了一些还可以，不是特别复杂，但是有bug的代码，自己也是根据需要进行了修改，实在不想花时间在实现上了，且任务也是紧迫。其实逻辑和数学挺重要的，至少现在用到了很多数学知识。逻辑，业务还需要不断学习和加强。感谢网友分享...
cut.hpp

#ifndef CUT_HPP_INCLUDED
#define CUT_HPP_INCLUDED

#include <stdint.h> //typedef short int int16_t;
                    //typedef unsigned short int uint16_t;

///< 多边形剪切
#define Rectangle_Right 1
#define Rectangle_Bottom 2
#define Rectangle_Left 3
#define Rectangle_Top 4
#define CutCount_N 50

typedef struct _Point
{
    int16_t x;
    int16_t y;
} Point;

///< 直线起始点
typedef struct _RtVector
{
    Point sp;
    Point ep;
}RtVector;

///< 矩形框
typedef struct _Rectangle
{
        int16_t x;
        int16_t y;
        uint16_t width;
        uint16_t height;
} Rectangle;

/**
  * @brief 矩形裁剪直线
  * @param[in/out] vector - 直线的起始点坐标
  * @param[in] rect - 矩形框范围
  * @return 成功裁剪true,裁剪结果保存在vector中，如果不再裁剪区域范围则返回false.
  * @note 此接口如果裁剪结果为一个点相交，则算作不再裁剪区域范围内.
  */
bool _rtPruneLB(RtVector * vector, Rectangle rect);

/**
  * @brief 矩形裁剪多边形
  * @param[in] Xwmax - 矩形框x轴最大值
  * @param[in] Xwmin - 矩形框x轴最小值
  * @param[in] Ywmax - 矩形框y轴最大值
  * @param[in] Ywmin - 矩形框y轴最小值
  * @param[in] n - 多边形顶点个数
  * @param[in] x - 多边形x坐标点
  * @param[in] y - 多边形y坐标
  * @param[out] xout - 裁剪得到的多边形具有一定顺序的x坐标点序
  * @param[out] yout - 裁剪得到的多边形具有一定顺序的y坐标点序
  * @return 返回裁剪后的多边形的顶点个数，如果不再裁剪区域范围则返回0.
  * @note 调用约定:
  * 1> 多边形顶点序列要么都是顺时针【裁剪得到的多边形是顺时针点序】，要么都是逆时针【裁剪得到的多边形是逆时针点序】；
  * 2> xout和yout的数组大小至少为20;
  * 注意：
  * 1> xout和yout具有一一对应关系；
  */
int clip_polygon(int Xwmax, int Xwmin,
                 int Ywmax, int Ywmin,
                 int n, float * x, float * y,
                 float * xout, float * yout);

#endif // CUT_HPP_INCLUDED

cut.cpp

#include "cut.hpp"
#include <iostream>
#include "cut.hpp"

using namespace std;

static void clip_single_edge(int edge, int type,
                             int nin, float * xin,
                             float * yin, int * nout,
                             float * xout, float * yout);

static void test_intersect(int edge, int type,
                           float x1, float y1,
                           float x2, float y2,
                           float * xout, float * yout,
                           int * yes, int * is_in);

bool _rtPruneLB(RtVector * vector, Rectangle rect)
{
    RtVector dest;
    bool flag = false;
    float u1 = 0, u2 =1;
    int p[4], q[4], i;
    float r;

    p[0] = vector->sp.x - vector->ep.x;
    p[1] = vector->ep.x - vector->sp.x;
    p[2] = vector->sp.y - vector->ep.y;
    p[3] = -vector->sp.y + vector->ep.y;
    q[0] = vector->sp.x - rect.x;
    q[1] = rect.x + rect.width - vector->sp.x;
    q[2] = vector->sp.y - rect.y;
    q[3] = rect.y + rect.height - vector->sp.y;

    ///< 排除在矩形边框之外，并且平行于矩形边线的直线
    if (0 == p[0] && (vector->sp.x < rect.x || vector->sp.x > (rect.x + rect.width)))
    {
        return false;
    }
    if (0 == p[2] && (vector->sp.y < rect.y || vector->sp.y > (rect.y + rect.height)))
    {
        return false;
    }

    for(i = 0; i < 4; ++i)
    {
        r = (float)q[i] / (float)p[i];
        if (p[i] < 0)
        {
            u1 = max(u1,r);
            if(u1 > u2)
            {
                flag = true;
            }
        }
        if (p[i] > 0)
        {
            u2 = min(u2, r);
            if (u1 > u2)
            {
                flag = true;
            }
        }
        if (0 == p[i] && p[i] < 0)
        {
            flag = true;
        }
    }

    if (flag)
    {
        return false;
    }

    dest.sp.x = vector->sp.x - u1 *(vector->sp.x - vector->ep.x);
    dest.sp.y = vector->sp.y - u1 *(vector->sp.y - vector->ep.y);
    dest.ep.x = vector->sp.x - u2 *(vector->sp.x - vector->ep.x);
    dest.ep.y = vector->sp.y - u2 *(vector->sp.y - vector->ep.y);

     ///< 裁剪结果为一个点，返回false
    if ((dest.sp.x == dest.ep.x) && (dest.sp.y == dest.ep.y))
    {
        return false;
    }

    vector->sp.x = dest.sp.x;
    vector->sp.y = dest.sp.y;
    vector->ep.x = dest.ep.x;
    vector->ep.y = dest.ep.y;

    return true;
}

int clip_polygon(int Xwmax, int Xwmin,
                 int Ywmax, int Ywmin,
                 int n, float * x, float * y,
                 float * xout, float * yout)
{
    float x1[CutCount_N] = {0}, y1[CutCount_N] = {0};
    int n1 = 0;

    clip_single_edge(Xwmax, Rectangle_Right, n, x, y, &n1, x1, y1);
    clip_single_edge(Ywmax, Rectangle_Bottom, n1, x1, y1, &n1, xout, yout);
    clip_single_edge(Xwmin, Rectangle_Left, n1, xout, yout, &n1, x1, y1);
    clip_single_edge(Ywmin, Rectangle_Top, n1, x1, y1, &n1, xout, yout);

    if (n1 > 1) ///< 排除某些剪切情况下，最后一个点重复的情况
    {
        if (xout[n1 - 1] == xout[n1 - 2] && yout[n1 - 1] == yout[n1 - 2])
        {
            return n1 - 1;
        }
    }

    return n1;
}

void clip_single_edge(int edge, int type,
                      int nin, float * xin,
                      float * yin, int * nout,
                      float * xout, float * yout)
{
    int j = 0, k = 0, yes, is_in;
    float x, y, x_intersect, y_intersect;

    if (0 == nin)
    {
        return;
    }

    x = xin[nin - 1];
    y = yin[nin - 1];
    for (j = 0; j < nin; ++j)
    {
        test_intersect(edge, type, x, y, xin[j], yin[j], &x_intersect, &y_intersect, &yes, &is_in);
        if (yes)
        {
            xout[k] = x_intersect;
            yout[k] = y_intersect;
            ++k;
        }
        if (is_in)
        {
            xout[k] = xin[j];
            yout[k] = yin[j];
            ++k;
        }
        x = xin[j];
        y = yin[j];
    }
    (*nout) = k;

    return;
}

void test_intersect(int edge, int type,
                    float x1, float y1,
                    float x2, float y2,
                    float * xout, float * yout,
                    int * yes, int * is_in)
{
    float m;
    (*is_in) = (*yes) = 0;

    if (x1 != x2)
    {
        m = (float)((float)y2-(float)y1)/((float)x2-(float)x1);
    }

    switch(type)
    {
    case Rectangle_Right :
    {
        if (x2 <= edge)
        {
            (*is_in) = 1;
            if (x1 > edge)
            {
                (*yes) = 1;
            }
        }
        else
        {
            if (x1 <= edge)
            {
                (*yes) = 1;
            }
        }
    }
        break;
    case Rectangle_Bottom:
    {
        if (y2 <= edge)
        {
            (*is_in) = 1;
            if (y1 > edge)
            {
                (*yes) = 1;
            }

        }
        else
        {
            if (y1 <= edge)
            {
                (*yes) = 1;
            }

        }
    }
        break;
    case Rectangle_Left:
    {
        if (x2 >= edge)
        {
            (*is_in) = 1;
            if (x1 < edge)
            {
                (*yes) = 1;
            }

        }
        else
        {
            if (x1 >= edge)
            {
                (*yes) = 1;
            }
        }
    }
        break;
    case Rectangle_Top:
    {
        if (y2 >= edge)
        {
            (*is_in) = 1;
            if (y1 < edge)
            {
                (*yes) = 1;
            }
        }
        else
        {
            if (y1 >= edge)
            {
                (*yes) = 1;
            }
        }
    }
        break;
    default:
        break;
    }

    if ((*yes))
    {
        if ((type == Rectangle_Right) || (type == Rectangle_Left))
        {
            (*xout) = edge;
            (*yout) = y1 + m * ((*xout) - x1);
        }
        else
        {
            if (x1 == x2)
            {
                if (Rectangle_Bottom == type && (y1 <= edge || y2 <= edge))
                {
                    (*xout) = x1;
                    (*yout) = edge;
                }
                if (Rectangle_Top == type && (y1 >= edge || y2 >= edge))
                {
                    (*xout) = x1;
                    (*yout) = edge;
                }
            }
            else
            {
                (*yout) = edge;
                (*xout) = x1 + ((*yout) - y1)/m;
            }
        }
    }
    return;
}

测试：main.cpp

#include <iostream>
#include "cut.hpp"

using namespace std;

int main()
{
   int i;
   int xwmax=300, xwmin=50, ywmax=250, ywmin=150;

   float x[]={10,300,300};     ///< 直角三角形在右边
   float y[]={200,230,200};
   int n = 3;

   float xout[CutCount_N]={0};
   float yout[CutCount_N]={0};
   int cutCount = 0;

   cutCount = clip_polygon(xwmax, xwmin, ywmax, ywmin, n, x, y, xout, yout);

   cout << cutCount << endl;
   for (i = 0; i < cutCount; ++i)
   {
        cout << "x: " << xout[i] << "   y: " << yout[i] << endl;
   }

   return 0;
}