多边形凹凸性的判断、自相交判断

说明该博文转载自弱花3kou 的文章 [OpenGL] 绘制并且判断凹凸多边形、自相交多边形分析凸多边形凹多边形自相交代码#include <iostream>#include <ctime>#include <math.h>#include <vector>using namespace std;// 定义点struct Pos {int x;i

Neverland_LY

7679人浏览 · 2020-09-12 09:53:58

Neverland_LY · 2020-09-12 09:53:58 发布

文章目录

说明

该博文参考弱花3kou 的文章 [OpenGL] 绘制并且判断凹凸多边形、自相交多边形

分析

凸多边形

在这里插入图片描述

凹多边形

在这里插入图片描述

自相交

在这里插入图片描述

代码

#include <iostream>
#include <ctime>
#include <math.h>
#include <vector>

using namespace std;

// 定义点
struct Pos {
    int x;
    int y;
};

// 定义边
struct Edge {
    int x1, x2;
    int y1, y2;
    int vx;
    int vy;
    int a, b, c;
};

// 定义多边形
struct Poly {
    // 点集
    int xx[100];
    int yy[100];

    // 边集
    Edge Edges[100];

    int plotNums = 0; //点数量
    int edgeNums = 0; //边数量

    // 记录凹点
    int conv = 0;
};

Poly poly;


// 求交点坐标，这里的A、B、C是直线方程 Ax + By + C = 0 的参数，求交点是利用向量叉乘计算得到的
// 具体可查看博客：用叉积求二维直线交点
// https://www.jianshu.com/p/3468c9967fc7
Pos CrossPos(int p1, int p2) {
    Pos res;
    int A1 = poly.Edges[p1].a;
    int B1 = poly.Edges[p1].b;
    int A2 = poly.Edges[p2].a;
    int B2 = poly.Edges[p2].b;
    int C1 = poly.Edges[p1].c;
    int C2 = poly.Edges[p2].c;

    int m = A1 * B2 - A2 * B1;
    if (m == 0)
        cout << "第" << p1 << "边和第" << p2 << "边" << "无交点" << endl;
    else {
        res.x = (C2 * B1 - C1 * B2) / m;
        res.y = (C1 * A2 - C2 * A1) / m;
    }
    return res;

}

// 判断点是否在线段内，意思就是判断点是否在矩形框内
bool JudgeInLine(Pos pos, Edge edge) {
    int maxX = edge.x1 >= edge.x2 ? edge.x1 : edge.x2;
    int minX = edge.x1 <= edge.x2 ? edge.x1 : edge.x2;
    int maxY = edge.y1 >= edge.y2 ? edge.y1 : edge.y2;
    int minY = edge.y1 <= edge.y2 ? edge.y1 : edge.y2;
    if (pos.x <= maxX && pos.x >= minX && pos.y <= maxY && pos.y >= minY) {
        return true;
    }
    return false;
}

// 求叉积 返回正负值
int CrossProduct(int n) {
    n = n % poly.edgeNums;
    int np = (n + 1) % poly.edgeNums;
    return (poly.Edges[n].vx * poly.Edges[np].vy - poly.Edges[np].vx * poly.Edges[n].vy) >= 0 ? 1 : -1;
}


// 判断是什么多边形
bool Judge() {
    /*输出边信息*/
    for (int i = 0; i < poly.edgeNums; i++) {
        cout << "Vx：" << poly.Edges[i].vx << "  " << "Vy：" << poly.Edges[i].vy << "  " << "A：" << poly.Edges[i].a << "  " << "B：" << poly.Edges[i].b << "  " << "C：" << poly.Edges[i].c << endl;
    }

    /*判断自交*/
    Pos interPos;
    if (poly.edgeNums > 3)
        for (int i = 0; i < poly.edgeNums; i++) {
            interPos = CrossPos(i, (i + 2) % poly.edgeNums);
            if (JudgeInLine(interPos, poly.Edges[i]) && JudgeInLine(interPos, poly.Edges[(i + 2) % poly.edgeNums])) {
                cout << "该多边形为自相交多边形" << endl;
                return false;
            }
        }

    /*判断凹凸*/
    // 判断向量叉积 是否为同一正负
    int judge;
    if (CrossProduct(0) >= 0)
        judge = 1;
    else
        judge = -1;
    //判断每一个角，两边向量乘积是否同符号
    for (int i = 1; i <= poly.edgeNums; i++) {
        if (judge * CrossProduct(i) < 0) {
            poly.conv = i;
            ChangePoly();
            cout << "该多边形为凹多边形" << endl;
            return false;
        }
    }
    cout << "该多边形为凸多边形" << endl;
    return true;
}