如何基于坐标和尺寸在等轴投影上对对象进行排序？

Question

如何基于坐标和尺寸在等轴投影上对对象进行排序？

algorithmsortingisometric

3

我试图自己解决这个问题，但是我尝试的所有方法都没有完全奏效。我不确定这是否是一个数学问题（因为它与语言无关），但我首先会在这里问。

我有一组矩形形状：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

- Katai

你能在图纸上标出x和y吗？ - Stef

@Stef 确定，稍等一下，我会编辑这些图片 - 是的...我尝试过几种不同的解决方案，但每一种都有它自己的问题 :) - Katai

我的关于x和y的评论实际上是在问两个问题：（1）哪个轴是x轴，哪个轴是y轴；（2）矩形的哪个点对应于该矩形的“坐标”？（可以是中心，右下角或另一个角落） - Stef

@Stef 我忘了那个，你是对的。我会编辑它。x和y是“左下角”坐标;我现在调整了图片，希望更清晰。我会在文本中添加有关角落的部分。 - Katai

@Stef 我可以给你坐标，但问题是它们似乎并不重要。整体星座是导致这个问题的原因，而不是单个比较 - 所以是“整体顺序”导致了这种效果。我可以随机添加新元素，突然它就能工作了，而另一部分则失败了。不过，我会添加所有箱子的坐标，并标记失败的对 - 但请记住，比较两个元素是正常的；它在“更大的范围”上失败了。 - Katai

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stef · Accepted Answer

对于两个矩形A和B，有三种可能的情况：

A必须在B之前绘制；
B必须在A之前绘制；
不管先画哪一个都没关系。

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

经典排序算法的假设是关系既是可传递的（没有冲突的三元组），也是完全的（对于每一对A、B，您可以说哪一个必须先绘制）。

不需要关系是完全的排序算法称为拓扑排序，并通常被描述为有向图顶点的排序。这里的顶点是矩形，如果A必须在B之前绘制，则从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;
否则，如果((B.x_max <= A.x_min) OR (B.y_max <= A.y_min))，则应该先画A。

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