当任何两个元素之间的比较可能不明确时对列表进行排序？

Question

我正在尝试优化等距渲染器的排序.令人难以置信的是,比较者可以返回"A> B","A <B"或"A和B之间的关系是模棱两可的".所有标准排序算法都希望您可以比较任何两个对象的值,但我不能在这里做.是否有针对这种情况的已知算法？

例如,可能存在A和C之间的关系不明确的情况,但我们知道A> B,B> C.最终列表应该是A,B,C.

另请注意,可能存在多种解决方案.如果A> B,但C对A和B都不明确,则答案可以是C,A,B或A,B,C.

编辑:我确实说它是用于在等距渲染器中进行排序,但有几个人要求更多信息,所以这里有.我有一个等距游戏,我正在尝试对物体进行排序.每个物体在世界上都有一个矩形的,轴对齐的足迹,这意味着它们从相机的角度看起来像一种钻石形状.对象的高度是未知的,因此假定另一个对象前面的对象能够遮挡后面的对象,因此必须在后面的对象之后绘制(在列表中稍后排序).

我也留下了一个重要的考虑因素,即少数物体(化身)四处移动.

编辑#2:我终于有足够的代表发布图片了!A和B ......好吧,它们并不严格含糊不清,因为在每种情况下它们之间都有一定的关系.但是,通过查看A和B本身的变量,无法知道这种关系.只有当我们看到C时,我们才能知道它们的顺序.

我绝对认为地形排序是要走的路,所以我正在考虑回答的问题,但我很乐意澄清后代的问题.

Answer 1

您可能想查看部分订单的排序。

https://math.stackexchange.com/questions/55891/algorithm-to-sort-based-on-a-partial-order链接到有关此主题（特别是拓扑排序）的正确论文。

编辑：

给定节点的定义：

您需要确保对象永远不会导致相互遮挡。看一下下面的网格，相机位于左下角。

______
____X_
_YYYX_
_YXXX_
_Y____

正如你所看到的，Y的一部分被X隐藏，X的一部分被Y隐藏。任何绘制顺序都会导致奇怪的渲染。这个问题可以通过多种方式解决，最简单的是只允许凸面、无孔形状作为可渲染图元。任何凹面都需要分成块。

如果您这样做，您就可以将部分订单转换为全订单。这是一个例子：

def compare(a,b):
    if a.max_x < b.min_x:
        return -1
    elif a.max_y < b.min_y:
        return -1
    elif b.max_x < a.min_x:
        return 1
    elif b.max_y < a.min_y:
        return 1
    else:
        # The bounding boxes intersect
        # If the objects are both rectangular,
        # this should be impossible
        # If you allow non-rectangular convex shapes,
        # like circles, you may need to do something fancier here.
        raise NotImplementedException("I only handle non-intersecting bounding boxes")

并使用任何旧的排序算法来为您提供绘图顺序。