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

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 隐藏。任何绘制顺序都会导致奇怪的渲染。这可以通过多种方式解决，最简单的是只允许凸的、无孔的形状作为可渲染图元。任何凹面都需要分解成 block 。

如果这样做，您就可以将部分订单变成总订单。这是一个例子:

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")

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