test

[smilelc3]

#include <iostream>
#include "boost/geometry/geometries/box.hpp"
#include "boost/geometry/geometries/point.hpp"
#include "boost/geometry/geometries/polygon.hpp"
#include "boost/geometry/geometry.hpp"
#include "solution.h"

/*
struct Point {
  int x;
  int y;
  Point(int x, int y) : x(x), y(y) {}
};

struct Polygon {
  vector<Point> points;
  vector<Polygon *> holes;
};
*/

namespace bg = boost::geometry;
constexpr size_t kBoostPointDimensionCount = 2;
using BoostPoint = bg::model::point<double, kBoostPointDimensionCount, bg::cs::cartesian>;
using BoostPolygon = bg::model::polygon<BoostPoint, false>;  // counterClockwise

//示例代码采用boost库，可自定义实现，不强制使用boost
void ToBoostPolygon(Polygon *poly, BoostPolygon &boost_polygon)
{
    // hull_points
    vector<Point> &hull_points = poly->points;
    if (hull_points.empty()) {
        return;
    }
    // counterClockwise
    for (auto it = hull_points.rbegin(); it != hull_points.rend(); it++) {
        bg::append(boost_polygon.outer(), BoostPoint(it->x, it->y));
    }
    bg::append(boost_polygon.outer(), BoostPoint(hull_points.back().x, hull_points.back().y));

    //  hole_points
    int hole_count = poly->holes.size();
    boost_polygon.inners().resize(hole_count);
    auto holes_itr = poly->holes.begin();

    for (int hole_index = 0; holes_itr != poly->holes.end(); ++holes_itr, ++hole_index) {
        vector<Point> &hole_points = (*holes_itr)->points;
        if (hole_points.empty()) {
            continue;
        }
        // ClockWise
        for (auto it = hole_points.rbegin(); it != hole_points.rend(); it++) {
            bg::append(boost_polygon.inners()[hole_index], BoostPoint(it->x, it->y));
        }
        bg::append(boost_polygon.inners()[hole_index], BoostPoint(hole_points.back().x, hole_points.back().y));
    }
}

bool IsAreaMatch(Polygon *polygon1, Polygon *polygon2)
{
    BoostPolygon boost_polygon1, boost_polygon2;

    ToBoostPolygon(polygon1, boost_polygon1);
    ToBoostPolygon(polygon2, boost_polygon2);
    string reason;
    auto matrix = bg::relation(boost_polygon1, boost_polygon2);
    return (matrix[0] == 'T' || matrix[0] == '2');
}

bool IsHoleMatch(Polygon *hole1, Polygon *hole2)
{
    BoostPolygon boost_polygon1, boost_polygon2;
    for (auto it = hole1->points.begin(); it != hole1->points.end(); it++) {
        bg::append(boost_polygon1.outer(), BoostPoint(it->x, it->y));
    }

    bg::append(boost_polygon1.outer(), BoostPoint(hole1->points[0].x, hole1->points[0].y));
    for (auto it = hole2->points.begin(); it != hole2->points.end(); it++) {
        bg::append(boost_polygon2.outer(), BoostPoint(it->x, it->y));
    }
    bg::append(boost_polygon2.outer(), BoostPoint(hole2->points[0].x, hole2->points[0].y));
    string reason;
    auto matrix = bg::relation(boost_polygon1, boost_polygon2);
    return (matrix[0] == 'T' || matrix[0] == '2');
}

/**
 * @brief 获取多边形匹配结果,暴力求解
 * 入参：src_polys 源多边形集
 * 入参：dst_polys 目标多边形集
 * 返回值：匹配结果

unordered_map<Polygon *, unordered_set<Polygon *>> GetMatchPolys(vector<Polygon
*> &src_polys, vector<Polygon *> &dst_polys)
{
    unordered_map<Polygon *, unordered_set<Polygon *>> ans;
    for (auto &src_poly : src_polys) {
        ans[src_poly] = unordered_set<Polygon *>();
        for (auto &dst_poly : dst_polys) {
            if (IsAreaMatch(src_poly, dst_poly)) {
                ans[src_poly].insert(dst_poly);
                for (auto &src_hole : src_poly->holes) {
                    for (auto &dst_hole : dst_poly->holes) {
                        if (IsHoleMatch(src_hole, dst_hole)) {
                            ans[src_hole].insert(dst_hole);
                        }
                    }
                }
            }
        }
    }
    return ans;
}
*/

struct Box {
    int left{0};
    int right{0};
    int down{0};
    int up{0};
};

//计算一个polygon的边界
Box CalcBoundingBox(Polygon *poly)
{
    Box box;
    box.left = INT_MAX;
    box.right = INT_MIN;
    box.down = INT_MAX;
    box.up = INT_MIN;
    for (auto it = poly->points.begin(); it != poly->points.end(); it++) {
        box.left = std::min(box.left, it->x);
        box.right = std::max(box.right, it->x);
        box.down = std::min(box.down, it->y);
        box.up = std::max(box.up, it->y);
    }
    return box;
}
//计算一组polygon的边界
void CalcBoundingBox(vector<Polygon *> &polys, unordered_map<Polygon *, Box> &box_map)
{
    for (auto &poly : polys) {
        box_map[poly] = CalcBoundingBox(poly);
    }
}

//判断边界box是否重叠，polygon的边界不重叠，则polygon本身不会重叠
bool isBoxOverlap(Box &box1, Box &box2)
{
    if (box1.up < box2.down || box1.down > box2.up) {
        return false;
    }
    if (box1.right < box2.left || box1.left > box2.right) {
        return false;
    }
    return true;
}

//判断hole是否重叠
void MatchHoles(Polygon *src_poly, Polygon *dst_poly, unordered_map<Polygon *, unordered_set<Polygon *>> &ans)
{
    for (auto &src_hole : src_poly->holes) {
        for (auto &dst_hole : dst_poly->holes) {
            if (IsHoleMatch(src_hole, dst_hole)) {
                ans[src_hole].insert(dst_hole);
            }
        }
    }
}

/**
 * @brief 获取多边形匹配结果,排序+滑窗+
 * 入参：src_polys 源多边形集
 * 入参：dst_polys 目标多边形集
 * 返回值：匹配结果
 */
unordered_map<Polygon *, unordered_set<Polygon *>> GetMatchPolys(vector<Polygon *> &src_polys,
                                                                 vector<Polygon *> &dst_polys)
{
    unordered_map<Polygon *, unordered_set<Polygon *>> ans;
    unordered_map<Polygon *, Box> src_box_map;
    unordered_map<Polygon *, Box> dst_box_map;
    CalcBoundingBox(src_polys, src_box_map);
    CalcBoundingBox(dst_polys, dst_box_map);

    // 按边界的x方向排序：先按左侧排序，左侧相等就按右侧排序
    std::sort(src_polys.begin(), src_polys.end(), [&](auto a, auto b) {
        if (src_box_map[a].left == src_box_map[b].left) {
            return src_box_map[a].right < src_box_map[b].right;
        }
        return src_box_map[a].left < src_box_map[b].left;
    });
    std::sort(dst_polys.begin(), dst_polys.end(), [&](auto a, auto b) {
        if (dst_box_map[a].left == dst_box_map[b].left) {
            return dst_box_map[a].right < dst_box_map[b].right;
        }
        return dst_box_map[a].left < dst_box_map[b].left;
    });

    // 排序后，就不用每个polygon都调用boost库计算，记录左窗口
    size_t left_poly_idx = 0;
    for (size_t i = 0; i < src_polys.size(); i++) {
        bool is_step_forword = false;
        auto &src_poly = src_polys[i];
        auto min_x = src_box_map[src_poly].left;
        auto max_x = src_box_map[src_poly].right;
        for (size_t j = left_poly_idx; j < dst_polys.size(); j++) {
            auto &dst_poly = dst_polys[j];
            auto &box = dst_box_map[dst_poly];
            if (min_x > box.right) {
                continue;
            }
            // 记录窗口，src的下一个polygon从当前窗口开始
            if (!is_step_forword) {
                left_poly_idx = j;
                is_step_forword = true;
            }

            // j再往后，box的left只会越来越大，不会有重叠的可能性
            if (max_x < box.left) {
                break;
            }
            if (!isBoxOverlap(src_box_map[src_poly], dst_box_map[dst_poly])) {
                continue;
            }
            if (IsAreaMatch(src_poly, dst_poly)) {
                ans[src_poly].insert(dst_poly);
                MatchHoles(src_poly, dst_poly, ans);
            }
        }
    }
    return ans;
}

[smilelc3]

#include <iostream>
#include "boost/geometry/geometries/box.hpp"
#include "boost/geometry/geometries/point.hpp"
#include "boost/geometry/geometries/polygon.hpp"
#include "boost/geometry/geometry.hpp"
#include "solution.h"

namespace bg = boost::geometry;
constexpr size_t BoostPointDimensionCount = 2;
using BoostPoint = bg::model::point<int, BoostPointDimensionCount, bg::cs::cartesian>;
using BoostPolygon = bg::model::polygon<BoostPoint, true, true>;  //  点类型 顺时针 闭合多边形
using BoostRing = bg::model::ring<BoostPoint, true, true>;
const static boost::geometry::de9im::mask solMask("T********"); // 仅内部存在交集
unordered_map<Polygon *, BoostPolygon> trans_polygon_map;

// ToBoostPolygon 函数将自定义的 Polygon 转换为 Boost.Geometry 的 BoostPolygon 类型，用于后续的计算。
void ToBoostPolygon(const Polygon &poly, BoostPolygon &boost_polygon) {
    // hull_points
    const vector<Point> &hull_points = poly.points;
    if (hull_points.empty()) {
        return;
    }
    // hull_points
    boost_polygon.outer().reserve(hull_points.size() + 1);
    for (auto hull_point: hull_points) {
        boost_polygon.outer().emplace_back(hull_point.x, hull_point.y);
    }
    boost_polygon.outer().emplace_back(boost_polygon.outer().front()); // 首尾相连

    //  hole_points
    boost_polygon.inners().reserve(poly.holes.size());
    for (auto &hole: poly.holes) {
        if (hole->points.empty()) {
            continue;
        }
        BoostRing boost_hole;
        boost_hole.reserve(hole->points.size() + 1);
        for (auto &point: hole->points) {
            boost_hole.emplace_back(point.x, point.y);
        }
        boost_hole.emplace_back(boost_hole.front()); // 首尾相连
        boost_polygon.inners().emplace_back(std::move(boost_hole));
    }
}

// 函数用于判断两个多边形是否具有相交或包含关系。
bool IsAreaMatch(Polygon &polygon1, Polygon &polygon2) {
    auto find_1 = trans_polygon_map.find(&polygon1);
    if (find_1 == trans_polygon_map.end()) {
        BoostPolygon boost_polygon1;
        ToBoostPolygon(polygon1, boost_polygon1);
        trans_polygon_map[&polygon1] = std::move(boost_polygon1);
    }
    auto find_2 = trans_polygon_map.find(&polygon2);
    if (find_2 == trans_polygon_map.end()) {
        BoostPolygon boost_polygon2;
        ToBoostPolygon(polygon2, boost_polygon2);
        trans_polygon_map[&polygon2] = std::move(boost_polygon2);
    }

    bool check = boost::geometry::relate(trans_polygon_map[&polygon1], trans_polygon_map[&polygon2], solMask);
    return check;
}

// 函数用于判断两个孔（Hole）是否具有相交或包含关系。
bool IsHoleMatch(Polygon *hole1, Polygon *hole2) {
    BoostPolygon boost_polygon1, boost_polygon2;

    boost_polygon1.outer().reserve(hole1->points.size() + 1);
    for (auto &point: hole1->points) {
        boost_polygon1.outer().emplace_back(point.x, point.y);
    }
    boost_polygon1.outer().emplace_back(boost_polygon1.outer().front());

    boost_polygon2.outer().reserve(hole2->points.size() + 1);
    for (auto &point: hole2->points) {
        boost_polygon2.outer().emplace_back(point.x, point.y);
    }
    boost_polygon2.outer().emplace_back(boost_polygon2.outer().front());
    bool check = boost::geometry::relate(boost_polygon1, boost_polygon2, solMask);
    return check;
}

struct Box {
    int left{std::numeric_limits<int>::max()};
    int right{std::numeric_limits<int>::min()};
    int down{std::numeric_limits<int>::max()};
    int up{std::numeric_limits<int>::min()};
};

//计算一个polygon的边界
// 函数用于计算多边形的边界框。
Box CalcBoundingBox(Polygon *poly) {
    Box box;
    for (const auto &point: poly->points) {
        box.left = std::min(box.left, point.x);
        box.right = std::max(box.right, point.x);
        box.down = std::min(box.down, point.y);
        box.up = std::max(box.up, point.y);
    }
    return box;
}

//计算一组polygon的边界
void CalcBoundingBox(vector<Polygon *> &polys, unordered_map<Polygon *, Box> &box_map) {
    for (const auto &poly: polys) {
        box_map[poly] = CalcBoundingBox(poly);
    }
}

//判断边界box是否重叠，polygon的边界不重叠，则polygon本身不会重叠
// 函数用于判断两个边界框是否重叠。
bool isBoxOverlap(Box &box1, Box &box2) {
    if (box1.up < box2.down or box1.down > box2.up or
        box1.right < box2.left or box1.left > box2.right) {
        return false;
    }
    return true;
}

//判断hole是否重叠
// MatchHoles 函数用于匹配两个多边形的孔。
void MatchHoles(Polygon *src_poly, Polygon *dst_poly, unordered_map<Polygon *, unordered_set<Polygon *>> &ans) {
    for (auto &src_hole: src_poly->holes) {
        for (auto &dst_hole: dst_poly->holes) {
            if (IsHoleMatch(src_hole, dst_hole)) {
                ans[src_hole].insert(dst_hole);
            }
        }
    }
}

/**
 * @brief 获取多边形匹配结果,排序+滑窗+
 * 入参：src_polys 源多边形集
 * 入参：dst_polys 目标多边形集
 * 返回值：匹配结果
 * 函数是一个获取多边形匹配结果的函数。它接受源多边形集合和目标多边形集合作为输入，并返回匹配结果的映射。
 * 函数通过排序和滑动窗口的方式进行匹配。它首先计算并排序源多边形和目标多边形的边界框，然后根据边界框的顺序遍历多边形进行匹配判断。在遍历过程中，根据边界框的位置关系和重叠情况，利用 IsAreaMatch 函数判断多边形是否匹配，并调用 MatchHoles 函数匹配孔。
 */
unordered_map<Polygon *, unordered_set<Polygon *>> GetMatchPolys(vector<Polygon *> &src_polys,
                                                                 vector<Polygon *> &dst_polys) {
    trans_polygon_map.clear();
    trans_polygon_map.reserve(src_polys.size() + dst_polys.size());
    unordered_map<Polygon *, unordered_set<Polygon *>> ans;
    unordered_map<Polygon *, Box> src_box_map;
    src_box_map.reserve(src_polys.size());
    unordered_map<Polygon *, Box> dst_box_map;
    dst_box_map.reserve(dst_polys.size());
    CalcBoundingBox(src_polys, src_box_map);
    CalcBoundingBox(dst_polys, dst_box_map);

// 按边界的x方向排序：先按左侧排序，左侧相等就按右侧排序
    std::sort(src_polys.begin(), src_polys.end(), [&](auto a, auto b) {
        if (src_box_map[a].left == src_box_map[b].left) {
            return src_box_map[a].right < src_box_map[b].right;
        }
        return src_box_map[a].left < src_box_map[b].left;
    });
    std::sort(dst_polys.begin(), dst_polys.end(), [&](auto a, auto b) {
        if (dst_box_map[a].left == dst_box_map[b].left) {
            return dst_box_map[a].right < dst_box_map[b].right;
        }
        return dst_box_map[a].left < dst_box_map[b].left;
    });

    // 排序后，就不用每个polygon都调用boost库计算，记录左窗口
    size_t left_poly_idx = 0;
    for (auto & src_poly : src_polys) {
        bool is_step_forward = false;
        auto min_x = src_box_map[src_poly].left;
        auto max_x = src_box_map[src_poly].right;
        for (size_t j = left_poly_idx; j < dst_polys.size(); j++) {
            auto &dst_poly = dst_polys[j];
            auto &box = dst_box_map[dst_poly];
            if (min_x > box.right) {
                continue;
            }
            // 记录窗口，src的下一个polygon从当前窗口开始
            if (not is_step_forward) {
                left_poly_idx = j;
                is_step_forward = true;
            }

            // j再往后，box的left只会越来越大，不会有重叠的可能性
            if (max_x < box.left) {
                break;
            }
            if (not isBoxOverlap(src_box_map[src_poly], dst_box_map[dst_poly])) {
                continue;
            }
            if (IsAreaMatch(*src_poly, *dst_poly)) {
                ans[src_poly].insert(dst_poly);
                MatchHoles(src_poly, dst_poly, ans);
            }
        }
    }
    return ans;
}