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

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

![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/80/v3/ZlJxNicIT9aYR1lXShZZ5w/zh-cn_image_0000002594828626.png?HW-CC-KV=V1&HW-CC-Date=20260612T073441Z&HW-CC-Expire=86400&HW-CC-Sign=6C6B319A62B27B9EC04943D679F14D88ACD2FD6DFA215F86C38139220B4C2414)

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

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

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

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

#### 接口说明

具体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/b6/v3/iaG67_wTRHmnt8ikCM7a8Q/zh-cn_image_0000002594828628.png?HW-CC-KV=V1&HW-CC-Date=20260612T073441Z&HW-CC-Expire=86400&HW-CC-Sign=FDCD87130815FED4517FA3CBEAC6E133E60BDBCF6E5A625F44824181AEF2F45A)。 |
| 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/84/v3/I5Ul57asSMi21yrbJMWA2w/zh-cn_image_0000002625188075.png?HW-CC-KV=V1&HW-CC-Date=20260612T073441Z&HW-CC-Expire=86400&HW-CC-Sign=14D7EF9A665A11A754C2E0CD0543A67CF533973383BA97949756B7F58072D57D) 或 ![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/74/v3/DEmSMoj-Qv6g2PZ92ztLbw/zh-cn_image_0000002625108219.png?HW-CC-KV=V1&HW-CC-Date=20260612T073441Z&HW-CC-Expire=86400&HW-CC-Sign=2C2F1B6FAA02F281B7E87B35F6C18777F976482165BC9D1D3575E3ADD12E3F67)或![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/65/v3/AEncu0-BRaisFVbDmHFYdg/zh-cn_image_0000002594668702.png?HW-CC-KV=V1&HW-CC-Date=20260612T073441Z&HW-CC-Expire=86400&HW-CC-Sign=808214D2BB17F983C91ABBBCAC3BEA5D96E0C096596F28B3709E116B5F29E5E8)或 ![](https://contentcenter-vali-drcn.dbankcdn.cn/pvt_2/DeveloperAlliance_scene_100_1/5c/v3/7eWhZAKNRL69N3jPna_9CA/zh-cn_image_0000002594828630.png?HW-CC-KV=V1&HW-CC-Date=20260612T073441Z&HW-CC-Expire=86400&HW-CC-Sign=CD8F210D73DF4E2D0CE1C93E1FC22360C538B41EB6F2C5443411FB2202414AAB)），否则函数返回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;
}