C++如何计算两个多边形的重叠部分面积-C++-PHP中文网

最可靠方法是使用cgal计算多边形交集面积，需采用exact_predicates_exact_constructions_kernel、顶点逆时针排序，并从intersection()返回的cgal::object中提取polygon_with_holes_2调用area()。

c++如何计算两个多边形的重叠部分面积

用 CGAL 计算两个多边形重叠面积最可靠

标准 C++ 库不提供多边形布尔运算，硬写交集算法极易出错（比如退化边、浮点精度、自相交处理）。生产环境建议直接用 CGAL —— 它的 intersection() 能正确处理任意简单/带洞/非凸多边形，且默认使用精确几何谓词。

实操要点：

需启用 Exact_predicates_exact_constructions_kernel（EPICK 不够，必须用 EK），否则交点坐标可能丢失精度，导致面积为 0 或 NaN
输入多边形顶点必须是逆时针序（外环）+ 顺时针序（内环/孔），顺序错会导致交集为空
CGAL::intersection() 返回的是一个 vector，元素可能是 Point_2、Segment_2 或 Polygon_with_holes_2，只取其中的 Polygon_with_holes_2 并调用 area()

// 示例：计算两个简单多边形交集面积
#include <cgal>
#include <cgal>
#include <cgal>
#include <cgal>

using K = CGAL::Exact_predicates_exact_constructions_kernel;
using Polygon_2 = CGAL::Polygon_2<k>
using Polygon_with_holes = CGAL::Polygon_with_holes_2<k>

double overlap_area(const Polygon_2& p1, const Polygon_2& p2) {
    std::vector<:object> output;
    CGAL::intersection(p1, p2, std::back_inserter(output));
    double area = 0.0;
    for (const auto& obj : output) {
        Polygon_with_holes poly;
        if (CGAL::assign(poly, obj)) {
            area += poly.outer_boundary().area(); // 忽略孔洞面积（交集本身不含孔）
            // 若需严格处理孔，得遍历 inner boundaries 并减去
        }
    }
    return std::abs(area); // area() 可能为负（取决于朝向）
}</:object></k></k></cgal></cgal></cgal></cgal>

不用第三方库时，只能处理凸多边形 + Sutherland-Hodgman 剪裁

如果明确知道两个多边形都是凸的，且不能引入 CGAL，可用 Sutherland-Hodgman 算法：用一个多边形的每条边当裁剪线，逐步裁剪另一个多边形。它实现简单，但对凹多边形会得到错误结果（比如把本该保留的区域切掉）。

关键细节：

C函数速查手册（CHM版）

下载

裁剪方向必须一致：所有边按同一顺序（如逆时针）处理，且点在边“左侧”视为内点
浮点比较必须用 epsilon（如 1e-9），否则共线顶点易被误判为内外侧
输出顶点数可能为 0（无重叠）、2（退化为线段，面积为 0）或 ≥3；需检查顶点数 ≥3 才调用鞋带公式

用 Boost.Geometry 的折中方案

Boost.Geometry 提供 intersection()，接口比 CGAL 简单，但默认使用 double 坐标，对病态几何（如几乎共线、极细长多边形）容易失败，报错信息是 "Operation not supported for this geometry type" 或静默返回空集合。

规避方法：

预处理：用 boost::geometry::correct() 修复输入多边形（自动调整环方向、移除重复点）
强制转为高精度：定义 typedef boost::geometry::model::d2::point_xy<long double> point;</long>，但部分算法仍回退到 double
务必检查返回容器是否为空，且每个元素调用 boost::geometry::is_valid()，无效则跳过