背景：
我有 GDSII 布局，其中许多矩形都位于同一层上。对于那些不熟悉的人来说，GDSII 是一种用于存储集成电路布局（电子/光子学/等）的文件格式。基本上，此文件格式存储多边形（以及有关这些多边形是什么的元数据，但请忽略这一点）。从数学上讲，我有一个 2D 平面上的矩形列表。
问题：
我想合并所有彼此靠近的多边形。我将接近定义为彼此相差 0.1 单位以内的两个多边形（单位是微米，但这与问题无关）。两个多边形之间的距离不是从中心到中心测量的；相反，它是两个多边形的最近边缘之间的距离。您还可以假设所有多边形都是矩形，并且可以使用曼哈顿距离。
我正在使用 python 来处理这个布局。可以使用浮点来表示距离。
我的解决方案：
我有一个非常慢的解决方案（基本上我使用的是幼稚的方法）。我循环遍历列表中的所有矩形两次（嵌套 for 循环），测量每个矩形组合之间的距离，如果它们足够近则合并。这是可行的，但是非常慢，时间复杂度为 O(n^2)，最好的情况也是 n^2（这不是一个聪明的算法）。
问题：
如果 O(n^2) 是最好的，请告诉我。我希望有一个解决方案可以在最好的情况下提供更好的时间复杂度，或者可能是一个更智能的 n^2 解决方案（已知具有较小常数的解决方案）？
我使用的是python GDSTK包，但是如果解决方案不使用这个包也没关系。
这个问题在数学上是关于在笛卡尔平面上合并矩形的。矩形存储为顶点 (xmin,ymin),(xmax,ymax)。可以通过在它们上面绘制一个大矩形或在它们之间绘制一个矩形来合并矩形（这样两个矩形基本上就连接起来了）。
简单算法：
当然，这是手写版本。简写版本是，对隐式扩展的矩形进行扫描和修剪，并记下那些具有 0-0.1 重叠的矩形，然后合并它们。