使用RectPartition求解矩形划分
=====================

矩形划分求解器（Rectangular Partition Solver）用于解决矩形划分问题。其接收若干个彼此不相交的矩形作为输入（主要关注这些矩形共同定义的区域的并集），计算出覆盖相同区域的矩形划分方案，并使输出的矩形数量尽可能少（但不保证最优）。形如下方示意图。

![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/f2/v3/Hy5Qbr4YSAyBRIElljc89A/zh-cn_image_0000002633849234.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=2159951E32ECDF1739F6F37CA4439F469E6AFA6F792DD655FD7C066028C7906A)

其相关定义如下：一个矩形![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/1f/v3/ZqEXIUoYSe2voP624BGACg/zh-cn_image_0000002634009138.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=A9E1D0BC5A5E63042F9A31E9314B5FD958FCCE69AF959049E0609F8FC3438BEA)为二维网格内横纵坐标满足![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/4/v3/EUrtEqKDSmCNO60egVmyfw/zh-cn_image_0000002664208287.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=69CF7A2D6A8F2069B7AD9DE9D345286DD3343F252A2020DA4F4A8C3BC7B1747F)的所有单元矩形构成的集合（坐标系说明：X轴从左到右递增，Y轴从上到下递增）。两个矩形相交，当且仅当它们共享至少一个公共的单元矩形。

在矩形划分问题（Rectangular Partition Problem）中，给定N个彼此不相交的矩形，要求输出M个矩形，使其满足如下几点：

*   输出的M个矩形彼此不相交。
    
*   输出的M个矩形的并集与输入的N个矩形的并集完全相同。
    
*   输出的矩形数量M尽可能少。
    

矩形划分求解器运行的时间复杂度为 ![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/56/v3/u1Gc08duQLmUt1tlSdoouQ/zh-cn_image_0000002664328347.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=8967FAF768723D2EFC190C1415FBA88352224E9930B4EEFAD92EAC4D8D81AF21)，可以高效处理大规模输入数据。在网格数据处理和空间几何计算等优化场景中，可以使用矩形划分求解器提升区域处理效率，减少冗余空间。

#### 接口说明

具体API说明详见[接口文档](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast)。

| 名称 | 描述 |
| :-- | :-- |
| FAST\_EXPORT [FAST\_ErrorCode](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_errorcode-1) [HMS\_FAST\_RectPartition\_CreateConfig](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#hms_fast_rectpartition_createconfig) ([FAST\_RectPartitionConfig](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_rectpartitionconfig) \*\*config) | 创建矩形划分求解器的不透明配置。 |
| FAST\_EXPORT void [HMS\_FAST\_RectPartition\_DestroyConfig](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#hms_fast_rectpartition_destroyconfig) ([FAST\_RectPartitionConfig](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_rectpartitionconfig) \*config) | 销毁矩形划分求解器的不透明配置。 |
| FAST\_EXPORT [FAST\_ErrorCode](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_errorcode-1) [HMS\_FAST\_RectPartition\_SetAlgo](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#hms_fast_rectpartition_setalgo) ([FAST\_RectPartitionConfig](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_rectpartitionconfig) \*config, const char \*name) | 设置矩形划分求解器使用的算法。目前仅支持扫描线算法“SweepLineAlgo”，输出数量尽可能少（不保证最优性）的不相交矩形集合，复杂度为![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/d7/v3/oP1AGzyOTHiXvsFZ5r957g/zh-cn_image_0000002633849236.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=EDB24861FF81683C5AEFDA971FC8C7D0A337D21FA3741E593F1479EBD39E2C2B)。 |
| FAST\_EXPORT [FAST\_ErrorCode](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_errorcode-1) [HMS\_FAST\_RectPartition\_Solve](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#hms_fast_rectpartition_solve) ([FAST\_RectPartitionConfig](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit-fast#fast_rectpartitionconfig) \*config, size\_t size, const [FAST\_Rect](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit--fast-rect) \*origin, [FAST\_Rect](https://developer.huawei.com/consumer/cn/doc/harmonyos-references/fast-kit--fast-rect) \*result, size\_t \*resultSize) | 
在指定不透明配置下解决矩形划分问题。函数接收若干个彼此不相交的矩形作为输入，计算出覆盖相同区域的矩形划分方案，并使输出的矩形数量尽可能少。

**说明**：

1\. 输入须保证矩形两两不相交（即任意两个矩形满足：![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/34/v3/co0xFfZQT0KNB1TZOvrgXQ/zh-cn_image_0000002634009140.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=5DFD1E52848DC40DE98F72282E0CEC2AC1D94DDB048CA2A0C0C4D4B77F7245BF) 或 ![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/b8/v3/pZxPOBkvT8a24qFI-Yu2gA/zh-cn_image_0000002664208289.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=A2C40CD0D2EFCB9DADD1A37C45D56257620F0EE60A43EB45514773AEFFE7995C)或![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/c2/v3/069W3OASQZmYcVzokD06Cw/zh-cn_image_0000002664328349.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=723440086F60104AC33B0339A50F4668951E3FCE7793BDD4F806AA79C0882CEB)或 ![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/86/v3/zbqya9LOR3GeOYA_D1FtNg/zh-cn_image_0000002633849238.png?HW-CC-KV=V1&HW-CC-Date=20260709T132446Z&HW-CC-Expire=86400&HW-CC-Sign=26117F878F5853A5335C3BCD38A62FC44E3CCA0D13C22D1F87D695E7BD2812FB)），否则函数返回FAST\_ERROR\_CODE\_ILLEGAL\_INPUT。

2\. 函数能保证输出矩形的数量小于等于输入矩形的数量。

 |

#### 开发步骤

1.  在CMake脚本中链接相关动态库。
    
    find\_library(
        lib\_fast\_solver
        NAMES fast\_solver
    )
    target\_link\_libraries(entry PRIVATE ${lib\_fast\_solver})
    
2.  调用HMS\_FAST\_RectPartition\_CreateConfig生成矩形划分求解器配置实例（FAST\_RectPartitionConfig）。
    
3.  调用HMS\_FAST\_RectPartition\_SetAlgo设置求解算法为“SweepLineAlgo”（扫描线算法）。
    
4.  调用HMS\_FAST\_RectPartition\_Solve计算矩形划分方案。
    
5.  调用HMS\_FAST\_RectPartition\_DestroyConfig销毁矩形划分求解器配置实例。
    

#include <cstdio>
#include <cstdlib>
#include "FASTKit/fast\_solver\_rect\_partition.h"

// 定义一个函数来打印矩形
void print\_rect(const FAST\_Rect\* rect) {
    printf("Rect: left=%d, top=%d, right=%d, bottom=%d\\n",
           rect->left, rect->top, rect->right, rect->bottom);
}

FAST\_ErrorCode rect\_partition\_demo() {
    // 定义输入矩形
    FAST\_Rect origin\[\] = {
        {1, 4, 1, 6},
        {2, 1, 2, 6},
        {3, 1, 3, 3}
    };
    size\_t size = sizeof(origin) / sizeof(FAST\_Rect);

    // 定义输出矩形
    FAST\_Rect\* result = (FAST\_Rect\*)malloc(size \* sizeof(FAST\_Rect));
    size\_t result\_size = 0;

    FAST\_RectPartitionConfig\* config = nullptr;
    FAST\_ErrorCode ret;

    do {
        // 创建配置
        ret = HMS\_FAST\_RectPartition\_CreateConfig(&config);
        if (ret != FAST\_ERROR\_CODE\_SUCCESS) {
            printf("Failed to create config: %d\\n", ret);
            break;
        }

        // 设置算法
        ret = HMS\_FAST\_RectPartition\_SetAlgo(config, "SweepLineAlgo");
        if (ret != FAST\_ERROR\_CODE\_SUCCESS) {
            printf("Failed to set algorithm: %d\\n", ret);
            break;
        }

        // 计算矩形划分方案
        ret = HMS\_FAST\_RectPartition\_Solve(config, size, origin, result, &result\_size);
        if (ret != FAST\_ERROR\_CODE\_SUCCESS) {
            printf("Failed to solve: %d\\n", ret);
            break;
        }

        // 打印结果
        printf("Resulting rectangles(result\_size=%ld):\\n", result\_size);
        for (size\_t i = 0; i < result\_size; ++i) {
            print\_rect(&result\[i\]);
        }
        /\*
            Resulting rectangles(result\_size=2):
            Rect: left=1, top=4, right=2, bottom=6
            Rect: left=2, top=1, right=3, bottom=3
         \*/

    } while (0);


    // 销毁配置
    HMS\_FAST\_RectPartition\_DestroyConfig(config);

    // 释放数组
    free(result);

    return ret;
}