布置矩形避免碰撞(算法帮助)
我有一个(大)水平滚动视图,还有一堆我想在其上定位的矩形.每个矩形具有所需的水平位置,但如果需要,它可以从该位置变化一定量(常数,K).矩形不得重叠.矩形的垂直位置是任意的(当然,约束于视图的高度).
理想情况下,我希望矩形的大小是可变的...我想如果这是不可能的,我可以使尺寸只在一个维度上变化.
现在,这种布局将不可能:由于只有一定数量的垂直空间,并且它们只能将K像素远离其理想水平方向移动,因此可能并非所有矩形都能够被绘制.为了解决这个问题,每个矩形都有一个优先级(P),优先级较低的矩形应该先省略.(您可以假设这是非模糊的,并且您可以始终分辨哪两个矩形具有更高的优先级.)
我是在概念算法的东西,但如果你需要细节,这将在iPad上运行,并将有几千(> 1000但<10,000)矩形需要考虑.理想情况下,每当用户更改缩放级别时,我都希望能够快速重新运行,但如果这不容易,那么我可以缓存这些位置.对象是时间轴上的照片,我希望在事件发生时大致接近它们 - 我要去近似,以便在那里获得更多.
我已经看过像这样的算法,它做了非交叉的技巧,但是对于每个只允许移动一定数量的项目没有相同的想法.显然没有后一种约束,你可以显示所有项目,所以我还需要一些方法知道在什么点上不能再显示矩形.
如果解决上述问题太困难,我欢迎提出一个更务实的想法.如果所有其他方法都失败了,我可以随时按优先顺序执行某些操作,如果可以,则将每个项目呈现在所需的位置,如果不是,则尝试垂直移动,如果仍然没有,则将其水平移动到允许的限制,然后继续下一个.优先级排序意味着可能会找到次优解决方案,但它会对最重要的项目进行加权.
这是我认为可以做到的一种方式.
第1步是找出可以放置新黄色矩形的所有位置.在不失一般性的情况下,我们可以将其存储为矩形左上角所有可能的XY位置的列表.当然,对于这样一个巨大的起始区域,该列表将包含数百万个条目,因此为了节省空间,我们将这个列表以一组矩形区域的形式存储.
例如,如果我们的屏幕具有从X = 0到X = 2999(含)的像素,并且从Y = 0到Y = 999(含),我们的新矩形的宽度为300像素,高度为150像素,我们的新矩形的左上角可以出现在(X,Y)=(0,0)到(2699,849)的任何位置.让我们将它存储为四元组,[0,0,2699,849].
现在,当我们将每个现有(红色)矩形放在屏幕上时,其中一些可能性将被排除,因为它们会导致新的(黄色)矩形与它们重叠.例如,如果有一个红色矩形[1100,200,1199,299],那么我们的黄色矩形的左上角不能位于(X,Y)=(801,51)到(1199,299)的任何位置包括的.
因此,将[0,0,2699,849]替换为覆盖相同区域但留有间隙的四个矩形区域.有很多方法可以做到这一点,但这里有一个:[0,0,1199,50],[1200,0,299,2699],[0,51,800,849],[801,300,2699,849] ].
继续在屏幕上添加更多红色矩形.每次添加一个,从列表中减去更多的可能性(这通常会导致列表包含更多,更小的"安全区域").(对于你的全屏有1000个以上的矩形,这可能非常耗时;如果你只是从你提到的[XK,0,X + K,H]空间开始,那么相对较少的1000个+将与此重叠并且计算速度会快得多.)这段代码应该非常谨慎地编写并进行一堆单元测试,因为fencepost错误会比比皆是.
最终结果是屏幕上可能位置的完整列表,其中可以放置新黄色矩形的左上角,以矩形区域列表的形式表示.
第2步:浏览此列表并选择最理想的位置.实际上与理想垂直线相交的任何矩形区域都将优先考虑.但是可能没有.在这种情况下,您可以从落在左侧的区域和落在理想线右侧的区域中选择最优选的选项.作为提示:在每种情况下,只需要考虑每个区域的一个角(右侧区域的左上角,左侧区域的右上角).