Euristico per ordinare in modo coerente i punti in un piano

Question

Euristico per ordinare in modo coerente i punti in un piano

#1 da (5 voti)
#2 da (0 voti)

1

Ho regioni rettangolari in un piano. Voglio ordinarli in modo coerente in modo umano per cui un tipo y-x tipico non funziona. Fondamentalmente voglio (0,0), (1,0) e (0,1) per ordinare lo stesso di (0,0), (1, -0,1) e (-0,1, 1).

idee?

Dai commenti:

Le ovvie risposte, y-x e x-y sort, danno come risultato ordini diversi per il breve esempio che ho postato. Le cose che mi vengono in mente, ora, sono gli approcci di cluster in cui raggruppo i valori y, ordinati per cluster y, quindi per x.

Question: What are you sorting your rectangles for? Searching? Displaying?

Numerando le regioni, e voglio due insiemi di regioni che un umano direbbe sono quasi identici per essere identificati in modo identico.

Question: Is the orientation of the rectangles really important (what is the difference between (0,1) and (-1,0) in the problem domain)? Would primarily sorting by area or diagonal be ok?

Non posso dire l'orientamento di essi al di là del ritratto o del paesaggio e la dimensione non funziona perché molto potrebbe essere praticamente uguale.

sorting

posta David Ehrmann 01.10.2013 - 18:52

fonte

2 risposte

Leggi altre domande sui tag sorting

Qual è il significato dell'output dell'analisi del Function Point Come potrebbe rilasciare Clang sotto licenza BSD?

score 5 · Answer 1

In linea di principio, una curva di Hilbert può farlo. È un frattale che riempie uno spazio bidimensionale.

Questo documento definisce una generalizzazione della curva di Hilbert e usa una relazione con codice binario grigio riflesso per definire conversioni efficienti, con l'applicazione principale come indici di database multidimensionali.

Il punto chiave è che un frattale può essere valutato a qualsiasi livello di dettaglio. Quindi, in linea di principio, se due punti diversi colpiscono lo stesso punto su una curva di Hilbert ad una risoluzione, puoi semplicemente valutare la curva di Hilbert a risoluzioni sempre più alte finché non trovi quella in cui i punti della curva di Hilbert sono diversi, ordinando i due punti basato su questo. Poiché stai solo valutando la stessa curva a un livello superiore di dettaglio, l'ordinamento relativo ad altri punti (valutato con una risoluzione inferiore) è invariato.

Detto questo, questa è solo un'idea di base: non so se è stata eseguita (probabilmente lo ha, ma non ho un riferimento) o il dettaglio su come implementarlo bene.

score 0 · Answer 2

Ho capito che esiste un modo migliore per affrontare il problema. Quello che cercavo di fare veramente era la corrispondenza (0,0), (1,0) e (0,1) a (0,0), (1, -0,1), e ( -0.1, 1), rispettivamente. Ordinarli, quindi abbinare sequenze come itertools.zip() di Python sembrava una soluzione elegante.

Ma ciò che è più facile è trattarlo come un problema di clustering. Esecuzione di K-means nella lista concatenata di punti in cui K = n / 2 (3 nel caso del mio esempio sopra) sarebbe l'abbinamento che mi serviva.