如何在C++中检测四条直线是否构成凸/凹四边形及多个四边形？

一、前置检查：排除无法形成四边形的情况 #

先过滤掉根本无法构成闭合四边形的直线组合，这是避免误判的核心：

• 存在三条或更多直线共点：直接排除；
• 存在三条或更多直线平行：仅能产生2个交点，无法构成闭合图形；
• 存在直线重合：等同于少于四条直线，排除；
• 交点去重后数量≠4：排除（如两组平行直线可产生4个交点，符合要求；但三线共点会导致交点数不足）。

实现思路 #

1. 用结构体存储直线的一般式 ax + by + c = 0；
2. 两两计算直线交点：通过解线性方程组得到坐标，同时处理平行（行列式为0）的情况；
3. 对交点去重（用epsilon判断浮点相等，如 fabs(x1-x2) < 1e-8 且 fabs(y1-y2) < 1e-8 视为同一点）；
4. 统计每个交点对应的直线数量，若有交点对应≥3条直线，直接判定无法形成四边形。

二、筛选合法的四边形顶点序列 #

当交点数为4且每个交点仅属于两条直线时，需将点按顺序连成闭合四边形：

• 把每个交点看作图的节点，若两个交点在同一条直线上，则在节点间连边；
• 从任意节点出发，遍历图寻找长度为4的环（每个节点仅访问一次，最终回到起点），环的节点顺序即为四边形的顶点序列；
• 若存在两个不同的环，则对应两个不同的四边形（通常一个凸、一个凹）。

三、判断凸/凹四边形 #

得到顶点序列 A, B, C, D（按顺时针或逆时针顺序）后，用叉积符号判断：

1. 计算四个相邻边的叉积：
   • cross1 = (B.x - A.x)*(C.y - B.y) - (B.y - A.y)*(C.x - B.x)（向量AB×BC）
   • cross2 = (C.x - B.x)*(D.y - C.y) - (C.y - B.y)*(D.x - C.x)（向量BC×CD）
   • cross3 = (D.x - C.x)*(A.y - D.y) - (D.y - C.y)*(A.x - D.x)（向量CD×DA）
   • cross4 = (A.x - D.x)*(B.y - A.y) - (A.y - D.y)*(B.x - A.x)（向量DA×AB）
2. 分析叉积符号：
   • 四个叉积全正或全负：凸四边形；
   • 有且仅有一个叉积符号与其他三个相反：凹四边形；
   • 存在叉积为0：退化图形（三点共线，非有效四边形）。

四、C++代码示例 #

#include <vector>
#include <cmath>
#include <algorithm>
#include <functional>

const double EPS = 1e-8;

// 点结构体
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator==(const Point& p) const {
        return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
    }
};

// 直线结构体（一般式 ax + by + c = 0）
struct Line {
    double a, b, c;
    Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {}
};

// 计算两条直线的交点，返回是否相交（true=相交，false=平行/重合）
bool getIntersection(const Line& l1, const Line& l2, Point& out) {
    double det = l1.a * l2.b - l2.a * l1.b;
    if (fabs(det) < EPS) return false;
    out.x = (l1.b * l2.c - l2.b * l1.c) / det;
    out.y = (l2.a * l1.c - l1.a * l2.c) / det;
    return true;
}

// 叉积计算：AB × AC
double cross(const Point& A, const Point& B, const Point& C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

// 判断四边形类型：0=无法形成，1=凸四边形，2=凹四边形，3=存在多个四边形
int checkQuadrilateral(const std::vector<Line>& lines) {
    if (lines.size() != 4) return 0;

    // 1. 计算所有交点并去重
    std::vector<Point> points;
    for (int i = 0; i < 4; ++i) {
        for (int j = i + 1; j < 4; ++j) {
            Point p;
            if (getIntersection(lines[i], lines[j], p)) {
                bool exists = false;
                for (const auto& pt : points) {
                    if (pt == p) { exists = true; break; }
                }
                if (!exists) points.push_back(p);
            }
        }
    }
    if (points.size() != 4) return 0;

    // 2. 检查每个交点是否仅属于两条直线
    for (const auto& p : points) {
        int cnt = 0;
        for (const auto& l : lines) {
            if (fabs(l.a * p.x + l.b * p.y + l.c) < EPS) cnt++;
        }
        if (cnt != 2) return 0;
    }

    // 3. 构建邻接表，寻找环
    std::vector<std::vector<int>> adj(4);
    for (int i = 0; i < 4; ++i) {
        for (int j = i + 1; j < 4; ++j) {
            bool onSameLine = false;
            for (const auto& l : lines) {
                if (fabs(l.a * points[i].x + l.b * points[i].y + l.c) < EPS &&
                    fabs(l.a * points[j].x + l.b * points[j].y + l.c) < EPS) {
                    onSameLine = true;
                    break;
                }
            }
            if (onSameLine) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    // 寻找所有长度为4的环
    std::vector<std::vector<int>> cycles;
    std::vector<bool> visited(4, false);
    std::vector<int> path;
    std::function<void(int, int)> dfs = [&](int curr, int prev) {
        path.push_back(curr);
        visited[curr] = true;
        if (path.size() == 4) {
            bool hasEdge = false;
            for (int neighbor : adj[curr]) {
                if (neighbor == path[0]) { hasEdge = true; break; }
            }
            if (hasEdge) cycles.push_back(path);
            visited[curr] = false;
            path.pop_back();
            return;
        }
        for (int neighbor : adj[curr]) {
            if (neighbor != prev && !visited[neighbor]) dfs(neighbor, curr);
        }
        visited[curr] = false;
        path.pop_back();
    };
    dfs(0, -1);

    if (cycles.empty()) return 0;

    // 4. 判断凸凹
    bool hasConvex = false, hasConcave = false;
    for (const auto& cycle : cycles) {
        Point A = points[cycle[0]], B = points[cycle[1]], C = points[cycle[2]], D = points[cycle[3]];
        double c1 = cross(A, B, C);
        double c2 = cross(B, C, D);
        double c3 = cross(C, D, A);
        double c4 = cross(D, A, B);

        if (fabs(c1) < EPS || fabs(c2) < EPS || fabs(c3) < EPS || fabs(c4) < EPS) continue;

        bool allPositive = (c1 > EPS && c2 > EPS && c3 > EPS && c4 > EPS);
        bool allNegative = (c1 < -EPS && c2 < -EPS && c3 < -EPS && c4 < -EPS);
        if (allPositive || allNegative) hasConvex = true;
        else hasConcave = true;
    }

    if (hasConvex && hasConcave) return 3;
    if (hasConvex) return 1;
    if (hasConcave) return 2;
    return 0;
}

关键注意事项 #

• 浮点精度问题：所有坐标比较必须使用epsilon，不能直接用==判断相等；
• 环的去重：DFS找到的环可能存在重复（如顺时针和逆时针视为同一个四边形），可通过排序环的顶点索引来去重；
• 完全四边形情况：当四条直线无平行、无三线共点时，会形成6个交点，此时需调整交点筛选逻辑，寻找由四条边组成的闭合环，这种场景下会存在多个四边形。

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