Ordinare una lista quando il confronto tra due elementi può essere ambiguo?

Question

Sto cercando di ottimizzare un ordinamento per un renderer isometrico. Ciò che si sta rivelando difficile è che il comparatore può restituire "A> B", "A < B" o "la relazione tra A e B è ambigua". Tutti gli algoritmi di ordinamento standard prevedono che è possibile confrontare i valori di qualsiasi due oggetti, ma non posso farlo qui. Esistono algoritmi noti per questa situazione?

Ad esempio, può esserci una situazione in cui la relazione tra A e C è ambigua, ma sappiamo A> B e B> C. L'elenco finale dovrebbe essere A, B, C.

Si noti inoltre che potrebbero esserci più soluzioni. Se A> B, ma C è ambiguo sia per A che per B, allora la risposta potrebbe essere C, A, B o A, B, C.

Modifica: Ho detto che era per l'ordinamento in un renderer isometrico, ma diverse persone hanno chiesto maggiori informazioni, ecco qui. Ho un gioco isometrico e sto cercando di ordinare gli oggetti. Ogni oggetto ha un ingombro rettangolare allineato sull'asse nel mondo, il che significa che appaiono come una sorta di rombi dalla prospettiva della telecamera. L'altezza degli oggetti non è nota, quindi si presume che un oggetto di fronte a un altro oggetto sia in grado di occludere quello nella parte posteriore e, pertanto, deve essere disegnato dopo (ordinato più tardi nell'elenco) di quello nella parte posteriore.

Ho anche lasciato una considerazione importante, ovvero che un piccolo numero di oggetti (gli avatar) si muovono.

Edit # 2: Ho finalmente un rappresentante sufficiente per pubblicare le foto! A e B ... beh, non sono strettamente ambigui perché in ogni caso hanno una relazione definita l'una rispetto all'altra. Tuttavia, tale relazione non può essere conosciuta guardando le variabili di A e B stesse. Solo quando guardiamo anche a C possiamo sapere in che ordine vanno.

Credo assolutamente che la topografia sia la strada da percorrere, quindi sto considerando la domanda risposta, ma sono felice di fare dei chiarimenti a la domanda per i posteri.

Answer 1

Si consiglia di guardare i tipi di ordini parziali.

https://math.stackexchange.com/questions/55891/algorithm-to-sort-based-on-a-partial-order collegamenti ai documenti giusti su questo argomento (in particolare l'ordinamento topologico).

Edit:

Data la definizione dei nodi:

È necessario rendere gli oggetti sicuri mai può provocare l'occlusione reciproca. Dai un'occhiata alla seguente griglia, dove la fotocamera si trova nell'angolo in basso a sinistra.

______ 
____X_ 
_YYYX_ 
_YXXX_ 
_Y____ 

Come si può vedere, le parti del Y sono nascoste da X e parti di X sono nascoste da Y. Ogni ordine di disegno causerà il rendering strano. Questo può essere risolto in molti modi, il più semplice consiste nel consentire solo forme convesse e prive di fori come primitive renderizzabili. Qualunque cosa concava deve essere spezzata in pezzi.

Se si esegue questa operazione, è possibile trasformare l'ordine parziale in un ordine totale. Ecco un esempio:

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

E utilizzare qualsiasi vecchio algoritmo di ordinamento per darti il ​​tuo ordine di disegno.

Answer 2

Si dovrebbe prima costruire un grafico diretto, utilizzando tale grafico sarà possibile trovare le relazioni, mediante DFS -ing da ciascun nodo.

Una volta che ci sono delle relazioni, alcune coppie potrebbero ancora essere ambigue. In tal caso, cerca l'ordinamento parziale.