布置矩形以避免碰撞(算法帮助) [英] Lay out rectangles avoiding collisions (algorithm help)

问题描述

我有一个(大)水平滚动视图，以及一堆我想在其上定位的矩形.每个矩形都有一个所需的水平位置，但是如果需要，它可以从该位置变化最大一定量(常数，K).矩形不得重叠.矩形的垂直位置是任意的(当然，受视图高度限制).

I have a (large) horizontally scrolling view, and a bunch of rectangles I'd like to position on it. Each rectangle has a desired horizontal position, but it can vary from that position by up to a certain amount (a constant, K) if needed. The rectangles must not overlap. The vertical position of the rectangles is arbitrary (constrained to the height of the view, of course).

理想情况下，我希望矩形的大小是可变的……我想如果不可能的话，我只能使尺寸仅在一个维度上变化.

Ideally I'd like to have the size of the rectangles being variable… I guess if that's not possible I can make the size vary in only one dimension.

现在，这种布局将不再可能:由于仅存在一定数量的垂直空间，并且它们只能将K像素从理想水平位置移开，因此可能无法绘制所有矩形.为了解决这个问题，每个矩形都有一个优先级(P)，优先级较低的矩形应首先省略. (您可以假定那是明确的，并且您始终可以知道任何两个矩形中的哪个具有更高的优先级.)

Now, there will be impossibilities in this layout: since there is only a certain amount of vertical space, and they can only move K pixels away from their ideal horizontally, probably not all rectangles will be able to be drawn. To deal with this, each rectangle has a priority (P), and the lower priority ones should be omitted first. (You can assume that that is non-ambiguous, and that you can always tell which of any two rectangles has the higher priority.)

我正在研究概念算法的内容，但是如果您需要特定的算法，它将在iPad上运行，并且将考虑几千个(> 1000个但小于10,000个)矩形.理想情况下，我希望每次用户更改缩放级别时都能快速运行，以便重新运行，但是如果这不容易，则可以缓存位置.这些对象是时间轴上的照片，我想让它们在事件发生时大约在附近—我要进行近似估算，以便在那里获得更多的照片.

I'm after conceptual algorithm stuff, but if you need specifics, this will be run on an iPad, and there will be a few thousand (>1000 but <10,000) rectangles to consider. Ideally I'd like something quick enough to re-run every time the user changes the zoom level, but if that's not easy then I can cache the positions. The objects are photos on a timeline, and I want to get them approximately near when the event happened — I'm going for approximate so as to get more of them on there.

我见过像 this 这样的算法，非相交的技巧，但对于将每个项目最多只能移动一定的数量没有相同的想法.显然，没有后一种约束，您可以显示所有项目，因此我还需要某种方式来知道什么时候不再显示矩形.

I've seen algorithms like this, that do the non-intersecting trick, but don't have the same idea about each item being only allowed to move by up to a certain amount. Obviously without the latter constraint, you can display all items, so I'll also need some way of knowing at what point no more rectangles can be displayed.

如果解决上述问题太困难了，我欢迎提出一个更务实的想法的建议.如果所有其他方法都失败了，我总是可以按优先级顺序进行操作，如果可以的话，将每个项目渲染到所需的位置，如果不能，则尝试垂直移动，如果仍然不行，则将其水平移动到允许的极限，然后再继续下一个.优先级排序将意味着可能会找到次优的解决方案，但是它将优先考虑最重要的项目.

If solving the problem as described is too difficult, I'd welcome a suggestion of a more pragmatic idea. If all else fails, I could always do something where it goes through in priority order, renders each item in its desired place if it can, if not then tries shifting it vertically, if still not then shift it horizontally up to the allowable limit, before moving on to the next one. The priority ordering would mean that probably a sub-optimal solution would be found, but it would be weighted towards the most important items.

推荐答案

这是我认为可以实现的一种方法.

This is one way that I think this could be done.

步骤1是找出可以放置新黄色矩形的所有位置.不失一般性，我们可以将其存储为矩形左上角所有可能的X-Y位置的列表.自然，对于如此庞大的起始区域，列表将包含数百万个条目，因此为了节省空间，让我们以一组矩形区域的形式存储此列表.

Step 1 is to figure out all of the locations where the new yellow rectangle can be placed. Without loss of generality, we can store this as a list of all the possible X-Y positions of the upper left corner of the rectangle. Naturally, for such a huge starting area that list will contain millions of entries, so to save space let's store this list in the form of a set of rectangular areas.

例如，如果我们的屏幕上的像素从X = 0到X = 2999(包括两端)，从Y = 0到Y = 999(包括两端)，并且我们的新矩形的宽度为300像素，高度为150像素，我们的新矩形可以出现在从(X，Y)=(0，0)到(2699，849)(包括两端)的任何位置.让我们将其存储为四元组[0，0，2699，849].

For example, if our screen has pixels from X=0 to X=2999 inclusive, and from Y=0 to Y=999 inclusive, and our new rectangle has width 300 pixels and height 150 pixels, the upper left corner of our new rectangle can appear at any position from (X,Y) = (0, 0) to (2699, 849) inclusive. Let's store that as a quadruplet, [0, 0, 2699, 849].

现在，当我们将每个现有的(红色)矩形放到屏幕上时，其中某些可能性就被排除在外，因为它们会导致新的(黄色)矩形与它们重叠.例如，如果有一个红色矩形[1100，200，1199，299]，则我们的黄色矩形在(X，Y)=(801，51)到(1199，299)的任何位置都不能具有其左上角包容性的.

Now when we put each existing (red) rectangle onto the screen, some of these possibilities become ruled out, since they would result in the new (yellow) rectangle overlapping them. For example, if there is a red rectangle [1100, 200, 1199, 299], then our yellow rectangle cannot have its upper left corner at any position from (X,Y) = (801, 51) to (1199, 299) inclusive.

因此，用四个覆盖相同区域但留有间隙的矩形区域替换[0，0，2699，849].有很多方法可以执行此操作，但是这里有一个:[0，0，1199，50]，[1200，0，299，2699]，[0，51，800，849]，[801，300，2699，849 ].

So, replace [0, 0, 2699, 849] with four rectangular zones which cover the same area but leave the gap. There are many ways to do this but here is one: [0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849].

继续在屏幕上添加更多红色矩形.每次添加一个，从列表中减去更多的可能性(通常将导致列表包含更多，更小的安全区域"). (对于全屏显示1000个以上的矩形，这可能会非常耗时；相反，如果仅从您提到的[XK，0，X + K，H]空间开始，那么在1000个矩形中相对较少+将使其重叠，并且计算将更快.)应谨慎编写此代码，并进行大量单元测试，因为围栏错误会比比皆是.

Keep adding more red rectangles to the screen. Each time one is added, subtract more possibilities from the list (this will usually result in the list containing more, smaller "safe zones"). (This could be very time-consuming for your full screen with 1000+ rectangles on it; if, instead, you start with just the [X-K, 0, X+K, H] space that you mentioned, then relatively few of the 1000+ will overlap this and the calculation will go much faster.) This code should be written with great care and a pile of unit tests, because fencepost errors will abound.

最终结果是屏幕上可以放置新黄色矩形左上角的可能位置的完整列表，以矩形区域列表的形式表示.

The end result is a complete list of possible locations on the screen where the upper left corner of your new yellow rectangle could be placed, expressed in the form of a list of rectangular zones.

第2步:浏览此列表，然后选择最理想的位置.实际上与理想垂直线相交的任何矩形区域都将被优先处理.但是有可能没有.在这种情况下，您可以从理想线左侧的区域和右侧的区域中选择最可取的选项.提示:在每种情况下，仅需考虑每个区域的一个角(右侧区域的左上角在右侧，左侧区域的右上角).

Step 2: look through this list and select the most desirable location. Any rectangular zone which actually intersects your ideal vertical line will take priority. But it's possible that there will be none. In this case it is up to you to pick the most preferable option from the zones falling on the left and the zones falling on the right of the ideal line. As a hint: only one corner of each zone needs to be considered in each case (the top left corner of the zones on the right, the top right corner of the zones on the left).

这篇关于布置矩形以避免碰撞(算法帮助)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！