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

Question

I'm trying to optimize a sort for an isometric renderer. What is proving tricky is that the comparitor can return "A > B", "A < B", or "the relationship between A and B is ambiguous." All of the standard sorting algorithms expect that you can compare the values of any two objects, but I cannot do that here. Are there known algorithms that are made for this situation?

For example, there can be a situation where the relationship between A and C is ambiguous, but we know A > B, and B > C. The final list should be A,B,C.

Note also that there may be multiple solutions. If A > B, but C is ambiguous to both A and B, then the answer may be C,A,B or A,B,C.

Edit: I did say it was for sorting in an isometric renderer, but several people asked for more info so here goes. I've got an isometric game and I'm trying to sort the objects. Each object has a rectangular, axis-aligned footprint in the world, which means that they appears as a sort of diamond shapes from the perspective of the camera. Height of the objects is not known, so an object in front of another object is assumed to be capable of occluding the one in the back, and therefore must be drawn after (sorted later in the list than) the one in the back.

I also left off an important consideration, which is that a small number of objects (the avatars) move around.

Edit #2: I finally have enough rep to post pictures! A and B...well, they aren't strictly ambiguous because in each case they have a definite relationship compared to each other. However, that relationship cannot be known by looking at the variables of A and B themselves. Only when we look at C as well can we know what order they go in.

I definitely think topographical sort is the way to go, so I'm considering the question answered, but I'm happy to make clarifications to the question for posterity.

Answer 1

You may want to look at sorts for partial orders.

https://math.stackexchange.com/questions/55891/algorithm-to-sort-based-on-a-partial-order links to the right papers on this topic (specifically topological sorting).

Edit:

Given the definition of the nodes:

You need to make sure objects never can cause mutual occlusion. Take a look at the following grid, where the camera is in the bottom left corner.

______
____X_
_YYYX_
_YXXX_
_Y____

As you can see, parts of Y are hidden by X and parts of X are hidden by Y. Any drawing order will cause weird rendering. This can be solved in many ways, the simplest being to only allow convex, hole-free shapes as renderable primitives. Anything concave needs to be broken into chunks.

If you do this, you can then turn your partial order into a total order. Here's an example:

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

And use any old sorting algortithm to give you your drawing order.