一、問題描述

---

已知兩個多邊形Polygon1和Polygon2，分別由點集C1={P1,P2,...,Pm}和C2={Q1,Q2,...,Qn}表示，求這兩個多邊形的交集。

二、算法思想

---

兩個多邊形相交后，其頂點要么是兩個多邊形邊的交點，要么是在多邊形內(nèi)部的點。

三、算法步驟

---

1. 計算兩個多邊形每條邊之間的交點。

2. 計算包含在多邊形內(nèi)部的點。

3. 將交點和多邊形內(nèi)部的點，按逆時針(或順時針)排序，得出最終的點集。

四、代碼實現(xiàn)

---

代碼基本實現(xiàn)如下：

4.1 頭文件

PolygonIntersection.h

#pragma once
#include <iostream>
#include "opencv2/opencv.hpp"

using namespace std;
using namespace cv;

//點集排序
//若點a大于點b,即點a在點b順時針方向,返回true,否則返回false
bool PointCompare(const cv::Point &a, const cv::Point &b, const cv::Point &center)
{
    if (a.x >= 0 && b.x < 0)
        return true;
    if (a.x == 0 && b.x == 0)
        return a.y > b.y;
    //向量OA和向量OB的叉積
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;
    //向量OA和向量OB共線，以距離判斷大小
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.y) + (b.y - center.y) * (b.y - center.y);

    return d1 > d2;
}
// 順時針方向排序
void ClockwiseSortPoints(std::vector<cv::Point> &vPoints)
{
    //計算重心
    cv::Point center;
    int count_size = vPoints.size();
    double x = 0, y = 0;
    for (int i = 0; i < count_size; i++)
    {
        x += vPoints[i].x;
        y += vPoints[i].y;
    }
    center.x = (int)x / count_size;
    center.y = (int)y / count_size;

    //冒泡排序
    for (int i = 0; i < count_size - 1; i++)
    {
        for (int j = 0; j < count_size - i - 1; j++)
        {
            if (PointCompare(vPoints[j], vPoints[j + 1], center))
            {
                cv::Point tmp = vPoints[j];
                vPoints[j] = vPoints[j + 1];
                vPoints[j + 1] = tmp;
            }
        }
    }

    return;
}

//判斷點是否在多邊形內(nèi)部/
//  The function will return YES if the point x,y is inside the polygon, or
//  NO if it is not.  If the point is exactly on the edge of the polygon,
//  then the function may return YES or NO.
bool IsPointInPolygon(const std::vector<cv::Point> &poly, const cv::Point &pt)
{
    int i, j;
    bool c = false;
    int count = poly.size();
    for (i = 0, j = count - 1; i < count; j = i++)
    {
        if ((((poly[i].y <= pt.y) && (pt.y < poly[j].y)) ||
            ((poly[j].y <= pt.y) && (pt.y < poly[i].y)))
            && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x))
        {
            c = !c;
        }
    }

    return c;
}

 ///線段相交判斷//
//排斥實驗
bool IsRectCross(const cv::Point &p1, const cv::Point &p2, const cv::Point &q1, const cv::Point &q2)
{
    bool ret = min(p1.x, p2.x) <= max(q1.x, q2.x) &&
        min(q1.x, q2.x) <= max(p1.x, p2.x) &&
        min(p1.y, p2.y) <= max(q1.y, q2.y) &&
        min(q1.y, q2.y) <= max(p1.y, p2.y);

    return ret;
}
//跨立判斷
bool IsLineSegmentCross(const cv::Point &pFirst1, const cv::Point &pFirst2, const cv::Point &pSecond1, const cv::Point &pSecond2)
{
    long line1, line2;
    line1 = pFirst1.x * (pSecond1.y - pFirst2.y) +
        pFirst2.x * (pFirst1.y - pSecond1.y) +
        pSecond1.x * (pFirst2.y - pFirst1.y);
    line2 = pFirst1.x * (pSecond2.y - pFirst2.y) +
        pFirst2.x * (pFirst1.y - pSecond2.y) +
        pSecond2.x * (pFirst2.y - pFirst1.y);
    if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
        return false;

    line1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
        pSecond2.x * (pSecond1.y - pFirst1.y) +
        pFirst1.x * (pSecond2.y - pSecond1.y);
    line2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
        pSecond2.x * (pSecond1.y - pFirst2.y) +
        pFirst2.x * (pSecond2.y - pSecond1.y);
    if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
        return false;

    return true;
}

bool GetCrossPoint(const cv::Point &p1, const cv::Point &p2, const cv::Point &q1, const cv::Point &q2, long &x, long &y)
{
    if (IsRectCross(p1, p2, q1, q2))
    {
        if (IsLineSegmentCross(p1, p2, q1, q2))
        {
            //求交點
            long tmpLeft, tmpRight;
            tmpLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
            tmpRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) - p1.x * (p2.y - p1.y) * (q2.x - q1.x);

            x = (int)((double)tmpRight / (double)tmpLeft);

            tmpLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
            tmpRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x - p2.x) * (q2.y - q1.y) * (p1.y - p2.y) - q2.y * (q1.x - q2.x) * (p2.y - p1.y);
            y = (int)((double)tmpRight / (double)tmpLeft);
            return true;
        }
    }
    return false;
}
 ///線段相交結(jié)束//

 //多邊形交集
bool PolygonClip(const std::vector<cv::Point> &poly1, const std::vector<cv::Point> &poly2, std::vector<cv::Point> &interPoly)
{
    if (poly1.size() < 3 || poly2.size() < 3)
    {
        return false;
    }

    long x, y;
    //計算多邊形交點
    int count1 = poly1.size();
    int count2 = poly2.size();
    for (int i = 0; i < count1; i++)
    {
        int poly1_next_idx = (i + 1) % count1;
        for (int j = 0; j < count2; j++)
        {
            int poly2_next_idx = (j + 1) % count2;
            if (GetCrossPoint(poly1[i], poly1[poly1_next_idx],
                poly2[j], poly2[poly2_next_idx],
                x, y))
            {
                interPoly.push_back(cv::Point(x, y));
            }
        }
    }

    //計算多邊形內(nèi)部點
    for (int i = 0; i < count1; i++)
    {
        if ( IsPointInPolygon(poly2, poly1[i]) )
        {
            interPoly.push_back(poly1[i]);
        }
    }
    for (int i = 0; i < count2; i++)
    {
        if ( IsPointInPolygon(poly1, poly2[i]) )
        {
            interPoly.push_back(poly2[i]);
        }
    }

    if (interPoly.size() <= 0)
        return false;

    //點集排序
    ClockwiseSortPoints(interPoly);

    return true;
}

4.2 主函數(shù)調(diào)用實現(xiàn)

main.cpp

#include "PolygonIntersection.h"

int main()
{
    std::vector<cv::Point> poly1;
    std::vector<cv::Point> poly2;
    // 多邊形1 點集賦值
    poly1.push_back(cv::Point(50,30));
    poly1.push_back(cv::Point(100, 30));
    poly1.push_back(cv::Point(100, 130));
    poly1.push_back(cv::Point(50, 130));
    // 多邊形2 點集賦值
    poly2.push_back(cv::Point(75, 80));
    poly2.push_back(cv::Point(125, 80));
    poly2.push_back(cv::Point(125, 180));
    poly2.push_back(cv::Point(75, 180));

    std::vector<cv::Point> interPoly;
    bool status = PolygonClip(poly1, poly2, interPoly);

    cv::Mat result = cv::Mat::zeros(300, 300, CV_8UC3);

    int count1 = poly1.size();
    for (int i = 0; i<count1; i++)
    {
        cv::Point p1 = poly1[i];
        cv::Point p2 = poly1[(i + 1) % count1];
        cv::line(result, p1, p2, cv::Scalar(255, 0, 0), 2, 8, 0);
    }

    int count2 = poly2.size();
    for (int i = 0; i < count2; i++)
    {
        cv::Point p1 = poly2[i];
        cv::Point p2 = poly2[(i + 1) % count2];
        cv::line(result, p1, p2, cv::Scalar(0, 255, 0), 2, 8, 0);
    }

    int count3 = interPoly.size();
    for (int i = 0; i < count3; i++)
    {
        cv::Point p1 = interPoly[i];
        cv::Point p2 = interPoly[(i + 1) % count3];
        cv::line(result, p1, p2, cv::Scalar(0, 0, 255), 2, 8, 0);
    }


    return 0;
}

4.3 結(jié)果

紅色矩形框的頂點就是兩個多邊形相交的點

五、參考資料

---

https://www.cnblogs.com/dwdxdy/p/3232110.html文章來源地址http://www.zghlxwxcb.cn/news/detail-528281.html