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

Question

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

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

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

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

这是我要找的：

这是一个对象示例：x=0，y=0，宽度=2，高度=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))，那么先画哪个矩形并不重要；
else if ((A.x_max <= B.x_min) OR (A.y_max <= B.y_min)),则B应该在A之前绘制;
else if ((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。

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

How can I order objects on an isometric projection, based on coordinates and size?

sorting

algorithm

isometric