1. 项目概述与核心价值最近在做一个图形编辑器的项目里面有个功能需求是让用户能自由绘制多边形然后对这个多边形进行一些后续的几何操作比如填充、碰撞检测或者计算质心。但问题很快就来了用户随手画的图形大概率是个“凹多边形”也就是图形内部至少有一个内角大于180度或者更直观地说图形“凹”进去一块。对于很多图形算法来说凹多边形是个麻烦精——计算填充区域时扫描线算法会变得复杂做碰撞检测比如分离轴定理效率会降低甚至计算面积和重心都可能出错。所以一个常见的预处理步骤就是先判断用户画的这个多边形是凸的还是凹的如果是凹的就把它“近似”成一个或多个凸多边形。这个“凸凹性识别及凹多边形近似为凸多边形”的功能就是我这次要分享的核心内容并且我会用Qt和C来实现它。这个功能听起来有点学术但在实际开发中非常实用。如果你是做CAD软件、游戏开发特别是2D物理引擎、GIS地理信息系统或者任何涉及图形处理和计算的领域几乎都会碰到这个问题。用Qt来做是因为它的QPolygonF等图形类非常方便而且能直观地展示结果用C来实现核心算法则是为了追求极致的性能。整个过程会涉及到向量叉积判断、多边形顶点顺序、以及经典的凹多边形三角剖分或凸包分解算法。我会从最基础的数学原理讲起一步步带你实现并分享我在调试过程中踩过的那些坑比如如何处理共线点、顶点顺序是顺时针还是逆时针对算法的影响等等。无论你是刚接触图形学的萌新还是想优化现有代码的老手相信这篇内容都能给你带来直接的帮助。2. 核心数学原理与算法选型要实现凸凹性识别和凸分解我们得先回到高中数学和计算几何的基础。别担心我们不用深究特别复杂的证明但必须理解几个关键概念因为它们是所有后续代码的基石。2.1 如何判断一个多边形的凸凹性判断一个多边形是凸是凹最常用也最有效的方法就是利用向量叉积。假设我们有一个按顺序存储顶点的多边形比如QVectorQPointF。我们依次遍历每条边考虑由连续三个顶点构成的角。具体来说对于顶点P(i-1),P(i),P(i1)我们构造两个向量向量V1 P(i) - P(i-1)向量V2 P(i1) - P(i)然后计算这两个向量的叉积在2D中叉积的结果是一个标量代表有向面积。对于二维向量(x1, y1)和(x2, y2)其叉积cross x1*y2 - y1*x2。这个叉积值的符号至关重要如果所有连续三个顶点计算出的叉积都同号全大于等于0或全小于等于0那么这个多边形就是凸多边形。如果出现异号的叉积那么这个多边形就是凹多边形。注意这里有一个巨大的坑就是多边形的顶点顺序顺时针CW或逆时针CCW。上述判断规则是基于顶点按逆时针顺序排列的。如果顶点是顺时针顺序那么凸多边形的条件就变成了所有叉积都小于等于0。在实现时我们必须先统一顶点顺序或者让算法能自适应。一个常见的做法是先计算多边形的有向面积也是用叉积如果面积为负说明是顺时针那就先反转顶点顺序。不统一顺序你的判断会完全错误。2.2 将凹多边形近似为凸多边形的主流方法识别出凹多边形后接下来就是如何“分解”或“近似”它。这里有两个主要思路适用于不同场景三角剖分将凹多边形完全分割成若干个三角形。三角形天生就是凸的。这是最彻底的方法适用于需要渲染GPU处理三角形最拿手或进行精确但独立的几何计算的场景。经典算法有耳切法。它的思想是寻找多边形的“耳朵”一个顶点与其相邻两顶点构成的三角形完全位于多边形内部且不包含其他顶点切掉这个“耳朵”形成一个三角形然后对剩余多边形递归进行。耳切法实现相对直观但时间复杂度在O(n²)到O(n³)之间对于顶点数多的多边形可能较慢。凸包分解将凹多边形分解成数量尽可能少的凸多边形。这比三角剖分得到的凸块数量少后续处理起来可能更高效比如物理引擎中更少的凸形状意味着更少的碰撞检测对。但算法也更复杂。一个著名的算法是Hertel-Mehlhorn算法。它的基本思路是先对多边形进行三角剖分得到一组对角线然后尝试合并相邻的三角形如果合并后形成的多边形仍然是凸的就合并它们直到无法合并为止。这样能得到一个接近最优的凸分解。为什么我选择耳切法作为本文的实现示例首先耳切法的原理更容易理解代码实现也更能清晰地展示从识别到分解的完整逻辑。其次在很多图形编辑器的交互场景中用户绘制的多边形顶点数不会特别多通常几十个顶点了不起了耳切法的性能是可以接受的。最后掌握了耳切法你对多边形顶点、内角、内部点的判断等基础几何操作会有更深的理解这是学习更复杂算法如Hertel-Mehlhorn的良好基础。当然在文章最后我会简要讨论如何优化以及何时该考虑更高效的算法。3. 开发环境搭建与Qt工程配置工欲善其事必先利其器。我们先来把开发环境搭好。这个项目主要依赖Qt的图形视图框架来展示所以一个基本的Qt Widgets Application就足够了。3.1 工具与库的选择Qt版本我使用的是Qt 5.15.2 LTS。Qt 6也可以但需要注意一些模块的变动比如Qt 6中部分图形类在Qt OpenGL模块中。对于这个2D项目Qt 5.15或Qt 6.2的Qt Widgets都可以。IDEQt Creator是最佳搭档对Qt项目支持完美。当然你用Visual Studio配合Qt VS Tools插件或者VSCode配置Qt开发环境也行看个人习惯。编译器Windows上可以用MSVC或MinGWLinux/macOS上用GCC或Clang。确保你的编译器支持C11或以上标准我们会用到一些现代C的特性让代码更简洁。3.2 创建Qt项目与关键配置在Qt Creator中新建一个“Qt Widgets Application”。在项目文件.pro中我们需要确保链接了必要的模块。通常core,gui,widgets是默认就有的。因为我们主要用QPainter在窗口上绘图这些就够了。如果你的项目后期想加入OpenGL加速渲染可以加上opengl。一个干净的.pro文件配置示例如下QT core gui widgets # 如果未来需要可以取消注释下面这行 # QT opengl CONFIG c11 SOURCES \ main.cpp \ mainwindow.cpp \ polygonprocessor.cpp # 这是我们即将创建的核心算法类 HEADERS \ mainwindow.h \ polygonprocessor.h FORMS \ mainwindow.ui这里我提前规划了一个PolygonProcessor类用来封装所有几何算法保持界面逻辑和业务逻辑分离这是良好的工程实践。3.3 界面设计与交互规划我们的主窗口MainWindow需要提供以下交互一个绘图区域让用户点击添加多边形的顶点。可以用QGraphicsView和QGraphicsScene也可以直接在QWidget的paintEvent里处理。为了简单直观我选择重写一个自定义的QWidget的mousePressEvent和paintEvent。功能按钮比如“清空”、“识别凸凹性”、“三角剖分/凸分解”、“显示/隐藏原始多边形”等。结果显示区域用文本来显示当前多边形是凸是凹或者用不同颜色绘制原始多边形和分解后的凸多边形/三角形。在mainwindow.ui里拖拽几个按钮和一个用于显示的QLabel再添加一个自定义的Widget作为绘图画布。将画布Widget提升为我们即将创建的CanvasWidget类。4. 核心算法类的设计与实现现在进入最核心的部分算法实现。我们将创建一个PolygonProcessor类它不依赖Qt的GUI只进行纯几何计算。这样便于单元测试和算法复用。4.1 基础几何工具函数在实现主要算法前需要一些“轮子”// polygonprocessor.h #ifndef POLYGONPROCESSOR_H #define POLYGONPROCESSOR_H #include QVector #include QPointF #include QPolygonF class PolygonProcessor { public: PolygonProcessor(); // 核心功能接口 bool isConvex(const QVectorQPointF polygon) const; QVectorQVectorQPointF triangulateByEarClipping(QVectorQPointF polygon) const; private: // 内部工具函数 double crossProduct(const QPointF a, const QPointF b, const QPointF c) const; bool isPointInsideTriangle(const QPointF p, const QPointF a, const QPointF b, const QPointF c) const; bool isEar(int i, const QVectorQPointF polygon, const QVectorint indices) const; void ensureCounterClockwise(QVectorQPointF polygon) const; }; #endif // POLYGONPROCESSOR_H// polygonprocessor.cpp #include polygonprocessor.h #include cmath #include algorithm PolygonProcessor::PolygonProcessor() {} // 计算叉积 (b-a) x (c-a) double PolygonProcessor::crossProduct(const QPointF a, const QPointF b, const QPointF c) const { return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()); } // 判断点p是否在三角形abc内部包括边上 bool PolygonProcessor::isPointInsideTriangle(const QPointF p, const QPointF a, const QPointF b, const QPointF c) const { // 使用重心坐标法或同侧法。这里用叉积同侧法更直观。 double d1 crossProduct(a, b, p); double d2 crossProduct(b, c, p); double d3 crossProduct(c, a, p); bool hasNegative (d1 -1e-10) || (d2 -1e-10) || (d3 -1e-10); bool hasPositive (d1 1e-10) || (d2 1e-10) || (d3 1e-10); // 如果叉积既不全为正或零也不全为负或零则点在三角形外 // 使用一个很小的epsilon如1e-10来处理浮点误差 return !(hasNegative hasPositive); } // 确保多边形顶点为逆时针顺序 void PolygonProcessor::ensureCounterClockwise(QVectorQPointF polygon) const { if (polygon.size() 3) return; // 计算有向面积Shoelace formula double area 0.0; int n polygon.size(); for (int i 0; i n; i) { const QPointF p1 polygon[i]; const QPointF p2 polygon[(i 1) % n]; area (p1.x() * p2.y() - p2.x() * p1.y()); } area / 2.0; // 如果面积为负说明是顺时针反转数组 if (area 0) { std::reverse(polygon.begin(), polygon.end()); } }4.2 凸凹性识别的实现有了叉积工具函数和顶点顺序校正凸凹性判断就水到渠成了。bool PolygonProcessor::isConvex(const QVectorQPointF polygon) const { int n polygon.size(); if (n 3) return true; // 少于3个点按定义算凸通常视为退化情况这里返回true // 先拷贝一份统一为逆时针顺序进行计算 QVectorQPointF localPoly polygon; ensureCounterClockwise(localPoly); // 检查所有连续三个顶点的叉积符号是否一致 bool sign false; bool signInitialized false; for (int i 0; i n; i) { const QPointF p0 localPoly[i]; const QPointF p1 localPoly[(i 1) % n]; const QPointF p2 localPoly[(i 2) % n]; double cp crossProduct(p0, p1, p2); // 处理叉积接近零的情况共线点 if (std::fabs(cp) 1e-10) { continue; // 忽略共线点它们不影响凸凹性判断 } bool currentSign cp 0; if (!signInitialized) { sign currentSign; signInitialized true; } else if (currentSign ! sign) { // 发现异号是凹多边形 return false; } } // 所有非零叉积同号是凸多边形 // 如果所有点都共线signInitialized为false这里也返回true但这是一个退化多边形 return true; }实操心得浮点数精度是图形计算永远的痛。上面代码中的1e-10就是一个epsilon用来处理因为浮点运算误差导致的“本应为零却不等于零”的情况。这个值需要根据你的坐标尺度调整。如果坐标值很大比如经纬度可能需要更大的epsilon如果坐标值很小可能需要更小的。没有银弹需要根据实际情况测试。4.3 耳切法三角剖分的实现这是本文最复杂的部分。耳切法的核心是循环查找“耳朵”顶点并切割。// 判断索引为i的顶点是否是“耳朵” bool PolygonProcessor::isEar(int i, const QVectorQPointF polygon, const QVectorint indices) const { int n indices.size(); if (n 3) return false; int prevIdx indices[(i - 1 n) % n]; int currIdx indices[i]; int nextIdx indices[(i 1) % n]; const QPointF prev polygon[prevIdx]; const QPointF curr polygon[currIdx]; const QPointF next polygon[nextIdx]; // 首先这个角必须是凸角对于逆时针多边形叉积应为正 if (crossProduct(prev, curr, next) 1e-10) { return false; } // 其次三角形(prev, curr, next)内部不能包含任何其他顶点 for (int k 0; k n; k) { if (k i || k ((i - 1 n) % n) || k ((i 1) % n)) { continue; } int testIdx indices[k]; const QPointF testPoint polygon[testIdx]; if (isPointInsideTriangle(testPoint, prev, curr, next)) { return false; } } return true; } QVectorQVectorQPointF PolygonProcessor::triangulateByEarClipping(QVectorQPointF polygon) const { QVectorQVectorQPointF triangles; int n polygon.size(); if (n 3) return triangles; // 1. 确保顶点顺序为逆时针 ensureCounterClockwise(polygon); // 2. 创建顶点索引列表 QVectorint indices; indices.reserve(n); for (int i 0; i n; i) indices.append(i); // 3. 循环切割耳朵直到只剩下一个三角形 while (indices.size() 3) { bool earFound false; for (int i 0; i indices.size(); i) { if (isEar(i, polygon, indices)) { // 找到耳朵切割三角形 int prevIdx indices[(i - 1 indices.size()) % indices.size()]; int currIdx indices[i]; int nextIdx indices[(i 1) % indices.size()]; QVectorQPointF triangle; triangle polygon[prevIdx] polygon[currIdx] polygon[nextIdx]; triangles.append(triangle); // 从索引列表中移除当前耳朵顶点 indices.removeAt(i); earFound true; break; // 移除一个顶点后多边形形状变了需要重新判断 } } // 理论上任何简单多边形都至少有两个耳朵。如果没找到可能是算法有bug或输入非法如自相交 if (!earFound) { qWarning() Ear clipping failed: No ear found. Polygon may be self-intersecting or degenerate.; // 一种容错处理直接按扇形剖分从第一个顶点连接到所有其他顶点 triangles.clear(); for (int i 1; i n - 1; i) { triangles.append({polygon[0], polygon[i], polygon[i 1]}); } return triangles; } } // 4. 最后剩下的三个顶点构成最后一个三角形 if (indices.size() 3) { QVectorQPointF lastTriangle; lastTriangle polygon[indices[0]] polygon[indices[1]] polygon[indices[2]]; triangles.append(lastTriangle); } return triangles; }踩坑实录耳切法最怕的就是自相交多边形。用户如果胡乱画线很容易画出像“8”字形一样自己交叉的多边形。这种多边形不是“简单多边形”耳切法以及很多其他几何算法的前提条件就不满足了。上面的代码在找不到耳朵时会发出警告并尝试一种简单的容错剖分。在真实产品中更好的做法是在用户绘制时或处理前就加入多边形自相交的检测并拒绝处理或提示用户。自相交检测可以通过判断非相邻线段是否相交来实现这又是一个计算几何课题。5. Qt界面集成与可视化算法准备好了现在需要把它们和Qt界面连接起来让我们能看到效果。5.1 自定义绘图画布创建一个CanvasWidget类继承自QWidget用于处理鼠标事件和绘制。// canvaswidget.h #ifndef CANVASWIDGET_H #define CANVASWIDGET_H #include QWidget #include QVector #include QPointF class CanvasWidget : public QWidget { Q_OBJECT public: explicit CanvasWidget(QWidget *parent nullptr); void clear(); void detectConvexity(); void triangulate(); signals: void convexityResult(bool isConvex); protected: void paintEvent(QPaintEvent *event) override; void mousePressEvent(QMouseEvent *event) override; private: QVectorQPointF m_polygon; QVectorQVectorQPointF m_triangles; bool m_isConvex; bool m_showTriangles; }; #endif // CANVASWIDGET_H// canvaswidget.cpp #include canvaswidget.h #include polygonprocessor.h #include QPainter #include QMouseEvent CanvasWidget::CanvasWidget(QWidget *parent) : QWidget(parent), m_isConvex(false), m_showTriangles(false) { setMouseTracking(true); } void CanvasWidget::clear() { m_polygon.clear(); m_triangles.clear(); m_showTriangles false; update(); // 触发重绘 } void CanvasWidget::detectConvexity() { if (m_polygon.size() 3) return; PolygonProcessor processor; m_isConvex processor.isConvex(m_polygon); emit convexityResult(m_isConvex); update(); } void CanvasWidget::triangulate() { if (m_polygon.size() 3) return; PolygonProcessor processor; m_triangles processor.triangulateByEarClipping(m_polygon); m_showTriangles true; update(); } void CanvasWidget::paintEvent(QPaintEvent *) { QPainter painter(this); painter.setRenderHint(QPainter::Antialiasing); // 绘制原始多边形顶点和边 if (!m_polygon.isEmpty()) { painter.setPen(QPen(Qt::blue, 2)); painter.setBrush(Qt::NoBrush); QPolygonF qpoly(m_polygon); painter.drawPolygon(qpoly); // 绘制顶点 painter.setBrush(Qt::red); for (const auto p : m_polygon) { painter.drawEllipse(p, 4, 4); } } // 绘制三角剖分结果 if (m_showTriangles !m_triangles.isEmpty()) { painter.setPen(QPen(Qt::darkGreen, 1, Qt::DashLine)); painter.setBrush(QBrush(QColor(0, 255, 0, 50))); // 半透明绿色填充 for (const auto tri : m_triangles) { QPolygonF qtri(tri); painter.drawPolygon(qtri); } } // 显示凸凹性 if (m_polygon.size() 3) { QString text m_isConvex ? 多边形状态凸多边形 : 多边形状态凹多边形; painter.setPen(Qt::black); painter.drawText(10, 20, text); } } void CanvasWidget::mousePressEvent(QMouseEvent *event) { if (event-button() Qt::LeftButton) { m_polygon.append(event-pos()); m_showTriangles false; // 添加新点后隐藏之前的剖分结果 update(); } else if (event-button() Qt::RightButton) { // 右键闭合多边形如果点数大于2 if (m_polygon.size() 2) { // 这里可以添加闭合逻辑或者我们默认绘制闭合多边形。 // 在paintEvent中drawPolygon会自动连接首尾点。 detectConvexity(); // 闭合后自动检测 } } }5.2 主窗口逻辑连接在MainWindow中将按钮的点击信号连接到画布的方法上。// 在MainWindow构造函数中 CanvasWidget *canvas new CanvasWidget(this); setCentralWidget(canvas); // 假设canvas被设置为中心部件 QPushButton *btnClear new QPushButton(清空, this); QPushButton *btnDetect new QPushButton(识别凸凹, this); QPushButton *btnTriangulate new QPushButton(三角剖分, this); connect(btnClear, QPushButton::clicked, canvas, CanvasWidget::clear); connect(btnDetect, QPushButton::clicked, canvas, CanvasWidget::detectConvexity); connect(btnTriangulate, QPushButton::clicked, canvas, CanvasWidget::triangulate); connect(canvas, CanvasWidget::convexityResult, this, [this](bool isConvex){ statusBar()-showMessage(isConvex ? 当前为凸多边形 : 当前为凹多边形, 3000); });现在运行程序你就可以在画布上点击左键添加顶点右键闭合多边形并自动检测凸凹性。点击“三角剖分”按钮凹多边形就会被分解成绿色的三角形。6. 性能优化、边界情况与进阶思考一个基础的Demo完成了但要投入实用我们还得考虑更多。6.1 算法效率与优化我们的耳切法实现是O(n²)的因为isEar函数内部有一个遍历所有顶点的循环来检查点是否在三角形内而外层的while循环在最坏情况下比如星形多边形可能需要切割n-2次。优化思路预处理顶点类型在算法开始前先遍历一次标记每个顶点是凸顶点还是凹顶点反射顶点。只有凸顶点才可能是耳朵。这可以避免对凹顶点进行昂贵的isEar检查。优化点在三角形内的检测isPointInsideTriangle函数是性能热点。可以使用更高效的算法如重心坐标法并利用三角形是凸多边形的特性进行快速排除比如判断点是否在三角形外接矩形外。使用更高效的算法对于顶点数很多成千上万的多边形应考虑O(n log n)的算法如单调多边形剖分结合三角剖分或者直接使用成熟的库如CGALComputational Geometry Algorithms Library。空间换时间维护一个“耳朵列表”每次切割后只更新受影响的局部顶点的耳朵状态而不是重新扫描整个多边形。6.2 处理刁钻的边界情况图形学代码的健壮性很大程度上取决于对边界情况的处理。共线点用户可能添加了三个或更多在同一直线上的点。我们的isConvex函数通过epsilon忽略了它们。但在三角剖分时共线点会导致面积为0的退化三角形。一种策略是在预处理中移除冗余的共线点但要注意不能改变多边形形状。重复点相邻顶点坐标完全相同。这会导致叉积为零、线段长度为零等问题。必须在处理前过滤掉重复点。自相交多边形如前所述这是非法输入。一个健壮的系统应该包含一个isSimplePolygon的检查函数在尝试凸凹判断或剖分前就过滤掉。退化多边形顶点数少于3。我们的代码做了基本检查但可能需要更明确的用户提示。浮点精度始终使用epsilon来比较浮点数相等或大小。epsilon的值需要根据你的数据范围进行校准。6.3 从三角剖分到凸包分解三角剖分得到了三角形但有时我们想要更大的凸块。这就要用到前面提到的Hertel-Mehlhorn算法。其步骤可以简述为首先对多边形进行三角剖分我们已经有了耳切法实现。将三角剖分的结果表示为一个对偶图其中每个三角形是一个节点共享一条边的三角形之间有一条边。遍历这个对偶图尝试合并相邻的三角形。合并的条件是合并后形成的四边形或更多边形仍然是凸的。重复合并过程直到无法合并为止。实现Hertel-Mehlhorn算法需要对多边形、对角线、凸性判断有更深入的理解并且要设计数据结构来高效地表示和操作三角剖分图。这是一个很好的进阶挑战。一个实用的建议是如果你的项目对凸块数量有要求可以考虑集成现有的强大几何库如Boost.Geometry或CGAL它们都提供了成熟的多边形凸分解算法。6.4 在Qt中提升可视化效果目前的绘制比较简陋。可以进一步交互支持拖动顶点修改多边形形状并实时更新凸凹性判断和剖分结果。高亮在识别凸凹性时用不同颜色高亮出导致凹性的“反射顶点”。动画将三角剖分的过程一步步动画展示出来非常适合教学。信息显示在界面上显示面积、周长、重心等几何信息并对比原始多边形和剖分后各部分的信息。7. 常见问题排查与调试技巧在实际编码和调试中你肯定会遇到各种奇怪的现象。这里记录几个我踩过的坑和解决方法。多边形识别结果时对时错检查顶点顺序这是最常见的问题。确保你的ensureCounterClockwise函数正确工作。可以在绘制多边形时用数字标出顶点顺序看看是否是逆时针。检查epsilon值如果坐标值很大比如屏幕坐标1e-10可能太小了导致本应忽略的微小叉积被当作有效值。尝试调整到一个更合理的值比如1e-7。打印调试信息在isConvex循环中打印出每个叉积的值和符号看是在哪个顶点出现了符号翻转。三角剖分时程序崩溃或卡死检查多边形顶点数在triangulateByEarClipping开头添加断言Q_ASSERT(n 3);。检查索引越界在isEar和移除顶点时仔细检查索引的计算特别是取模运算% indices.size()确保在indices大小变化后你的i值仍然是有效的。死循环如果while循环一直找不到耳朵就会死循环。我代码中添加了earFound检查和容错处理。确保你的isEar判断逻辑正确特别是“三角形内无其他顶点”这一条件。剖分结果出现重叠或缺失区域自相交多边形输入了自相交多边形算法行为未定义。务必先进行简单多边形检查。共线点导致退化三角形三个共线点形成的“三角形”在绘制时可能看不见。考虑在剖分前预处理移除相邻的共线点。性能突然变慢顶点数量测试一下顶点数量增加到几百个时的情况。如果变慢明显就是O(n²)算法的问题。需要引入前面提到的优化。isPointInsideTriangle优化这个函数被频繁调用。确保它尽可能高效。一个简单的优化是先判断点是否在三角形的外接矩形之外快速排除。调试利器Qt的qDebug()和qWarning()是你的好朋友。在关键算法步骤输出变量状态。另外可以临时修改绘制代码用不同颜色画出当前正在检查的“耳朵”三角形或者画出判断为在三角形内部的点这能让你直观地看到算法的执行过程。最后图形学算法对细节要求极高。耐心、细致的调试和对几何原理的深刻理解是解决所有问题的关键。从这个小项目出发你可以扩展到更复杂的几何处理领域比如多边形偏移Minkowski和、布尔运算并集、交集、路径规划等底层很多原理都是相通的。希望这篇长文能帮你打下坚实的基础。
