algorithm - 如何根据坐标和大小在等距投影上排序对象？

Question

我试图自己弄明白，但我尝试过的任何东西都无法完全奏效。我不确定这是否是数学问题(因为它与语言无关)，但我会先在这里问。

我有一组矩形:x、y、宽度、高度。我希望能够对这些对象进行排序，以便它们在等距投影时“彼此落后”。

编辑:x 和 y 坐标表示每个矩形的“左下角”。

这是一个失败尝试的例子:

这是我要找的:

这是一个对象的例子:x=0, y=0, width=2, height=1

对象可以是任意大小的矩形(不仅仅是我示例中显示的那些)。角度也不是很重要，我们就说 45°。

我曾尝试研究 Cavalier Projection 和类似的主题 - 但关于如何实际对这些对象进行排序的信息让我望而却步。

我可以使用什么样的排序算法来对这些对象进行排序并得到正确的顺序？

编辑 1: 使用 @Stef 的建议(并将“<”更改为“<=”适用于大多数情况，但一旦添加更多对象，就会开始发生这种情况:

// Stef's suggestion, slightly modified
compareRectangles(r1, r2):
return ((r1.x + r1.width <= r2.x) OR (r1.y+r1.height <= r2.y))

我以前在自己的尝试中遇到过这个问题。添加或删除其他框，可以更改结果。我不确定这是否是 sort() 的问题，或者它是否与对象彼此太“遥远”有关(因此当“长”对象相互切割时，排序突然不再起作用)。

一般来说，物体越“方”，出现的故障就越少。但我正在努力寻找一种即使是长矩形也能正常工作的解决方案。

编辑 2:这是上述失败示例的坐标。可悲的是，这个星座有点脆弱……添加更多的盒子只会导致故障出现在不同的随机位置。 整个星座似乎会影响结果，而不是每个单独的比较。

x, y, width, height
===================
0, 4, 4, 4
0, 8, 8, 1
4, 4, 4, 2
8, 4, 1, 7
6, 6, 1, 1
5, 6, 1, 1
4, 6, 1, 1
8, 11, 1, 1
0, 2, 9, 1
0, 1, 9, 1
0, 0, 9, 1
11, 7, 1, 1
11, 8, 1, 1
11, 9, 1, 1
11, 10, 1, 1
11, 11, 1, 1
0, 10, 1, 1
0, 11, 1, 1
1, 10, 1, 1
1, 11, 1, 1
2, 10, 1, 1
2, 11, 1, 1

0, 3, 11, 1 // long box above failing box

9, 1, 1, 1 // failing box

Answer 1

对于两个矩形A和B，可能存在三种情况:

• A必须先于B；
• B必须在A之前绘制；
• 先画哪个并不重要。

第三种情况很重要；如果您尝试通过默认为比较函数中的前两种情况之一来混合它，那么比较将不是传递关系。换句话说，您最终可能会得到相互冲突的三元组 A、B、C，其中 A 必须在 B 之前绘制，B 在 C 之前绘制，C 在 A 之前绘制。

经典排序算法假设关系是传递的(没有冲突的三元组)和总的(对于每一对 A，B，你可以说必须首先绘制哪一个)。

不需要完全关系的排序算法称为拓扑排序，通常被描述为有向图的一种顶点排序。这里的顶点是矩形，如果必须在 A 之前绘制 A，则存在从 A 到 B 的边。

因此，构建您的图形，并在此图形上调用拓扑排序函数。

我认为边缘的条件如下。对于两个矩形 A 和 B:

• 如果((A.x_max <= B.x_min) AND (B.y_max <= A.y_min)) OR ((B.x_max <= A.x_min) AND (A.y_max <= B.y_min)) , 那么先画哪个矩形就无所谓了;
• 否则如果((A.x_max <= B.x_min) OR (A.y_max <= B.y_min)) , 那么 B 应该在 A 之前绘制;
• 否则如果((B.x_max <= A.x_min) OR (B.y_max <= A.y_min)) , 那么 A 应该在 B 之前绘制。

请注意，与您的符号相比，我使用了 x_min = x, x_max = x+width, y_min = y, y_max = y + height .