特定算法的名称

我看到了你问题的两种解释:“给定一组坐标x1,y1,x2,y2,:…

1)这些矩形的结合是否形成一个独特的形状,即一个“岛”,而不是“独立的岛”,
2)所有这些矩形是否与给定形状相交(甚至包括在内)。

我不知道它是哪一个,但这听起来与 Set Cover problem (通过对偶关系到RSP提到的包装问题),并且可能是 Hitting Set .

听起来好像你描述了 packing problem 求解算法。

编辑 : 2d packing algorithms 在另一节中链接到。

我终于从一个朋友那里发现了扫描线算法可以用来做这个。事后看来很简单。这里有一个链接。 Sweep Line Algo