Eine Liste sortieren, wenn der Vergleich zwischen zwei beliebigen Elementen nicht eindeutig ist?

Question

Ich versuche, eine Sortierung für einen isometrischen Renderer zu optimieren. Was sich als schwierig erweist, ist, dass der Komparator "A> B", "A < B" oder "die Beziehung zwischen A und B ist mehrdeutig" zurückgeben kann. Alle Standard-Sortieralgorithmen erwarten, dass Sie die Werte von zwei beliebigen Objekten vergleichen können, aber das kann ich hier nicht tun. Gibt es bekannte Algorithmen für diese Situation?

Zum Beispiel kann es eine Situation geben, in der die Beziehung zwischen A und C mehrdeutig ist, aber wir kennen A> B und B> C. Die endgültige Liste sollte A, B, C sein.

Beachten Sie auch, dass es mehrere Lösungen geben kann. Wenn A> B, aber C sowohl für A als auch für B zweideutig ist, dann kann die Antwort C, A, B oder A, B, C sein.

Edit: Ich habe gesagt, es war für die Sortierung in einem isometrischen Renderer, aber mehrere Leute fragten nach mehr Informationen, also hier geht. Ich habe ein isometrisches Spiel und versuche die Objekte zu sortieren. Jedes Objekt hat einen rechteckigen, achsversetzten Fußabdruck in der Welt, was bedeutet, dass sie aus der Perspektive der Kamera als eine Art Rautenform erscheinen. Die Höhe der Objekte ist nicht bekannt, daher wird angenommen, dass ein Objekt vor einem anderen Objekt in der Lage ist, das Objekt in der Rückseite zu verschließen, und daher muss es in der Rückseite nach (später in der Liste sortiert) gezeichnet werden.

Ich habe auch eine wichtige Überlegung weggelassen, die darin besteht, dass eine kleine Anzahl von Objekten (die Avatare) sich bewegen.

Edit # 2: Ich habe endlich genug rep, um Bilder zu posten! A und B ... nun, sie sind nicht streng zweideutig, weil sie in jedem Fall eine bestimmte Beziehung zueinander haben. Diese Beziehung kann jedoch nicht durch Betrachten der Variablen von A und B selbst erkannt werden. Nur wenn wir auch auf C schauen, können wir wissen, in welcher Reihenfolge sie gehen.

Ich denke definitiv topographische Art ist der Weg zu gehen, also überlege ich die Frage beantwortet, aber ich bin glücklich, Erklärungen zu machen die Frage für die Nachwelt.

Answer 1

Sie können bei Sorten für Teilaufträge suchen.

https://math.stackexchange.com/questions/55891/algorithm-to-sort-based-on-a-partial-order Links zu den richtigen Arbeiten zu diesem Thema (speziell topologische Sortierung).

Edit:

die Definition der Knoten Gegeben:

Sie müssen sicherstellen, dass Objekte machen nie gegenseitige Okklusion verursachen können. Sehen Sie sich das folgende Raster an, in dem sich die Kamera in der unteren linken Ecke befindet. Jede Zeichnung Ordnung verursacht seltsamen Rendering

______ 
____X_ 
_YYYX_ 
_YXXX_ 
_Y____ 

Wie Sie sehen können, Teile von Y durch X versteckt und Teile von X durch Y versteckt. Dies kann auf viele Arten gelöst werden, wobei das einfachste darin besteht, nur konvexe, lochfreie Formen als darstellbare Primitive zuzulassen. Alles, was konkav ist, muss in Stücke zerbrochen werden.

Wenn Sie dies tun, können Sie Ihre Teilaufgabe in eine Gesamtbestellung umwandeln. Hier ein Beispiel:

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

und verwenden Sie alte Sortier algortithm Sie Ihre Zeichnung zu geben.

Answer 2

Sie sollten zunächst ein gerichtetes Diagramm erstellen, mit dem Sie die Beziehungen durch DFS-ing von jedem Knoten finden können.

Sobald Sie Beziehungen haben, sind einige Paare möglicherweise noch mehrdeutig. Suchen Sie in diesem Fall nach teilweiser Sortierung.