矩形并集求解：合并多边形转矩形的技术实现问询

我正在开发一个小型项目，需要计算两个或多个给定矩形的并集（Union）。关键要求是：将矩形合并为多边形后，最终结果必须以矩形形式返回（参考效果：多个矩形的覆盖区域被拆解为一组不重叠的规整矩形）。

矩形约束条件 #

• 必须与y轴相交（即左上角x坐标<0，右下角x坐标>0）
• 右下角严格位于左上角的右下方（保证是合法的非空矩形）

现有思路与问题 #

我原本的解题思路如下：

1. 将矩形列表从中间拆分
2. 找到相交的矩形以创建多边形
3. 递归处理所有矩形，将其转换为多边形
4. 将所有多边形合并为一个大的多边形
5. 尝试将该多边形拆分为矩形以完成实现

但之前尝试生成矩形中所有可能的点集，导致内存消耗过高，不适用于当前应用。

已实现代码 #

Point类 #

from typing import Tuple, List

class Point:
    x: int
    y: int
    def __init__(self, x: int, y: int) -> None:
        self.x = x
        self.y = y

    def get_coordinates(self) -> Tuple[int, int]:
        return (self.x, self.y)
    
    def __eq__(self, other) -> bool:
        if isinstance(other, Point):
            return self.x == other.x and self.y == other.y
        return False
    
    def __hash__(self):
        return hash((self.x, self.y))

Rectangle类 #

class Rectangle:
    top_left: Point
    bottom_right: Point

    def __init__(self, top_left: Point, bottom_right: Point) -> None:
        if top_left.x < 0 and bottom_right.x > 0:
            self.top_left = top_left
            self.bottom_right = bottom_right
        else:
            raise ValueError("Rectangle must intersect Y-axis")
    
    def contains(self, point: Point) -> bool:
        if self.top_left.x <= point.x <= self.bottom_right.x and self.bottom_right.y <= point.y <= self.top_left.y:
            return True
        else:
            return False
    
    def get_points(self) -> Tuple[Point, Point]:
        return (self.top_left, self.bottom_right)

Union类（待实现） #

class Union:
    rectangles: List[Rectangle]
    def __init__(self, rectangles: List[Rectangle]) -> None:
          self.rectangles = rectangles
    
    def get_union(self) -> List[Rectangle]:
        """
        Returns a list of Rectangles representing the union area.
        Rectangles should be returned in a sorted order from top to bottom.
        :return: The Rectangles from top to bottom that make up the union.
        """
        # 待实现
        pass

需求 #

寻求合适的实现方案，尤其是完成Union.get_union方法的编写，解决内存占用过高的问题。返回的矩形列表需按从上到下的顺序排序。

内容的提问来源于stack exchange，提问作者code-wolf-byte