对重叠形状进行分组(x，y)

Question

我使用x-y坐标(左下角，右上角)查找重叠矩形(区域)的算法运行良好。但我将重叠的部分分组在一起的算法似乎不起作用。有人能告诉我我哪里做错了吗？

我的程序从.txt文件中读取x-y坐标，如下所示...

0 5 3 6 (0,5 is bottom left corner and 3,6 is top right corner)

2 7 8 9 (2,7 is bottom left corner and 8,9 is top right corner)

然后找出重叠矩形上的所有组，并打印出组。

也就是说，矩形0与2重叠，2与1重叠，1与5重叠。这意味着矩形0、2、1和5都在一组中，所以我可以打印出该组#1。

即矩形4和3重叠，因此这意味着矩形4和3在组#2中。

也就是说，矩形10与11重叠，矩形11与矩形12重叠。这意味着矩形10、11和12都在#3组中，所以我可以整齐地打印出来。

Answer 1

据我所知，您需要做的是实现一个联合查找数据结构来存储连接的组件。它所做的正是您想要的。有关更多解释，请阅读以下问题：Union-find data structure

使用上面提到的代码，您需要做的是：

UF uf( n ); // create and initialize a UF. n is the number of rectangles you have
if ( two rectangles overlap ){ 
     if ( ! connected( rectangleId1, rectangleId2 ) ){ // if they aren't already in the same component
           merge( find(rectangleId1), find(rectangleId2) ); // put them in the same component
     }
}

在此之后，每个具有相同find( rectangleId )值的矩形都属于同一组件。