在我的应用程序中,关键的一段代码涉及枚举二维表面上的所有矩形.矩形不相交,我必须能够枚举给定矩形边界内的所有矩形.

我已经有一个函数可以返回给定坐标的矩形(如果存在)

GetRectangle( int row, int col )

这就是我将如何调用生成的代码.

foreach( var rect in GetRectangles( row, col, rowCount, colCount ) ) {
   //..  my processing code here
}

显然,我可以为曲面中的每个点调用函数GetRectangle().我也可以跳过上一次调用返回的矩形的宽度,因为我知道它们不相交.但是,这仍然不够有效.

您知道这种算法吗？

更新：表面不一定被矩形覆盖,但在某些特殊情况下可能会覆盖矩形.因此,函数GetRectangle(int row,int col)可能返回null.

可以将表面视为填充有随机矩形(不相交)的位图.任务是返回该表面上落入(即相交)给定框架的所有矩形.希望这可以澄清问题.

谢谢

解决方法:

为了获得最佳结果,请将矩形的集合组织为spatial lookup structure.在这种情况下,听起来好像R-tree是一个不错的选择.但是,如果您不能做到这一点,而GetRectangle就是您所拥有的,那么这就是我要做的：

计划是维护一个0≤j< j的整数xj的列表. rowCount,其中xj是第j行的最左边的点,对此我尚未找到覆盖它的矩形.
>首先为所有j初始化xj：= 0.
>如果所有j的xj = colCount,我们就完成了.停止.
>令J = min(j | xj = min(xi)).然后xJ是我尚未找到覆盖它的矩形的最左端.
>调用GetRectangle(xJ,J).如果这没有返回矩形,则该点将被覆盖.设置xJ：= xJ 1并转到步骤2.
>否则,我们有一个矩形,其左上角为(xJ,J).称其宽度w和高度h.当J≤j< J h,设置xj：= xj w.转到步骤2.
这是此算法的示例运行. xj的列表由左侧的数字显示,最顶部的最左端以粗体突出显示.橙色矩形是在该算法步骤中发现的矩形.

为了在步骤3高效发现最小值,您可能希望将xj列表保留在heap中.