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

Question

我正在尝试优化等距渲染器的排序。棘手的是，比较器可以 return "A > B"、"A < B" 或 "the relationship between A and B is ambiguous." 所有标准排序算法都希望您可以比较任意两个对象的值，但我不能在这里这样做。是否有针对这种情况的已知算法？

比如可能出现A和C关系不明确的情况，但是我们知道A>B，B>C，最终的列表应该是A,B,C。

另请注意，可能有多种解决方案。如果A > B，但C对A和B都是模糊的，那么答案可能是C,A,B或A,B,C。

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

我还遗漏了一个重要的考虑因素，即少量对象（化身）四处移动。

编辑 #2：我终于有足够的代表 post 图片了！ A 和 B...嗯，它们并不是严格意义上的模棱两可，因为在每种情况下，它们彼此之间都有明确的关系。但是，无法通过查看 A 和 B 本身的变量来了解这种关系。只有当我们也看C的时候，我们才能知道它们的顺序。

我绝对认为地形排序是可行的方法，所以我正在考虑回答的问题，但我很乐意为 posterity 澄清问题。

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

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

Answer 2

您应该首先构建一个有向图，使用该图您将能够通过每个节点的 DFS 找到关系。

一旦有了关系，有些对可能仍然是模棱两可的。在那种情况下寻找部分排序。

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

Sorting a list when the comparison between any two elements may be ambiguous?

sorting

algorithm

comparison

ambiguity