c++ - 对重叠形状 (x,y) 进行分组

Question

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

我的程序从 .txt 文件中读取 x-y 坐标...

0 5 3 6(0,5 是左下角，3,6 是右上角)

2 7 8 9(2,7 是左下角，8,9 是右上角)

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

即矩形 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 查找数据结构来存储连接的组件。它完全符合您的意图。如需更多解释，您应该阅读以下问题: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 ) 具有相同值的每个矩形都属于同一个组件。