目录

Using RectPartition to Solve the Rectangular Partition Problem

The rectangular partition solver is used to solve the rectangular partition problem. It takes a set of non-overlapping rectangle as input (focusing on the union of these areas) and computes a rectangular partitioning scheme to generate a minimum number of rectangles that cover the same total area (but not guaranteed to be optimal). The following is an example.

The definition is as follows: A rectangle is a set of all unit rectangles whose horizontal and vertical coordinates in a two-dimensional mesh meet the condition . (The coordinate system is described as follows: The X axis increases from left to right, and the Y axis increases from top to bottom.) Two rectangles intersect if and only if they share at least one common unit rectangle.

In the rectangular partition problem, given N non-overlapping rectangles, the task is to output M rectangles that satisfy the following conditions:

The rectangular partition solver has a time complexity of , enabling it to efficiently process large-scale input data. In optimization scenarios such as grid data processing and spatial geometry computation, the rectangular partition solver can be used to enhance area processing efficiency and reduce spatial redundancy.

API Description

For details about the APIs, please refer to the API Reference.

API Description
FAST_EXPORT FAST_ErrorCode HMS_FAST_RectPartition_CreateConfig (FAST_RectPartitionConfig **config) Creates the opaque configuration of the rectangular partition solver.
FAST_EXPORT void HMS_FAST_RectPartition_DestroyConfig (FAST_RectPartitionConfig *config) Destroys the opaque configuration of the rectangular partition solver.
FAST_EXPORT FAST_ErrorCode HMS_FAST_RectPartition_SetAlgo (FAST_RectPartitionConfig *config, const char *name) Sets the algorithm used by the rectangular partition solver. Currently, only the SweepLineAlgo scanline algorithm is supported. It outputs a set of non-overlapping rectangles with as few rectangles as possible (without guaranteeing optimality). The time complexity is .
FAST_EXPORT FAST_ErrorCode HMS_FAST_RectPartition_Solve (FAST_RectPartitionConfig *config, size_t size, const FAST_Rect *origin, FAST_Rect *result, size_t *resultSize)

Solves the rectangular partition problem under the specified opaque configuration. The function takes a set of non-overlapping rectangles as input and computes a rectangular partitioning scheme to generate a minimum number of rectangles that cover the same total area.

NOTE

1. The input rectangles must be pairwise non-overlapping (that is, for any two rectangles, at least one of the following conditions must be satisfied: , , , or . If the input rectangles do not satisfy these conditions, the function returns the FAST_ERROR_CODE_ILLEGAL_INPUT error code, indicating that the input parameters are invalid.

2. The function can ensure that the number of output rectangles is less than or equal to the number of input rectangles.

Development Procedure

  1. Link the related dynamic library in the CMake script.

    find_library(
    lib_fast_solver
    NAMES fast_solver
)
target_link_libraries(entry PRIVATE ${lib_fast_solver})

  2. Call HMS_FAST_RectPartition_CreateConfig to generate the rectangular partition solver configuration instance (FAST_RectPartitionConfig).

  3. Call HMS_FAST_RectPartition_SetAlgo to set the solving algorithm to SweepLineAlgo.

  4. Call HMS_FAST_RectPartition_Solve to compute the rectangular partitioning scheme.

  5. Call HMS_FAST_RectPartition_DestroyConfig to destroy the rectangular partition solver configuration instance.

#include <cstdio>
#include <cstdlib>
#include "FASTKit/fast_solver_rect_partition.h"

// Define a function to print rectangles.
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() {
    // Define the input rectangles.
    FAST_Rect origin[] = {
        {1, 4, 1, 6},
        {2, 1, 2, 6},
        {3, 1, 3, 3}
    };
    size_t size = sizeof(origin) / sizeof(FAST_Rect);

    // Define the output rectangles.
    FAST_Rect* result = (FAST_Rect*)malloc(size * sizeof(FAST_Rect));
    size_t result_size = 0;

    FAST_RectPartitionConfig* config = nullptr;
    FAST_ErrorCode ret;

    do {
        // Create a configuration instance.
        ret = HMS_FAST_RectPartition_CreateConfig(&config);
        if (ret != FAST_ERROR_CODE_SUCCESS) {
            printf("Failed to create config: %d\n", ret);
            break;
        }

        // Set the algorithm.
        ret = HMS_FAST_RectPartition_SetAlgo(config, "SweepLineAlgo");
        if (ret != FAST_ERROR_CODE_SUCCESS) {
            printf("Failed to set algorithm: %d\n", ret);
            break;
        }

        // Compute the rectangular partitioning scheme.
        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;
        }

        // Print the result.
        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);


    // Destroy the configuration.
    HMS_FAST_RectPartition_DestroyConfig(config);

    // Release the array.
    free(result);

    return ret;
}