0

我使用 xy 坐标（左下角、右上角）查找重叠矩形（区域）的算法工作正常。但是我将重叠的组合在一起的算法似乎不起作用。有人可以告诉我我做错了什么吗？

我的程序从这样的 .txt 文件中读取 xy 坐标...

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 组中，因此我可以打印出该组 #1。

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

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

4

1 回答 1

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 )属于同一个组件。

于 2015-11-23T00:40:25.870 回答