Ordinamento coordina problema

Question

sono state scatching la mia testa su questo! - e mi sa è semplice, ma la mia geometria / algebra è piuttosto spazzatura, e non riesco a ricordare come fare questa roba dai miei giorni di scuola

A CURA: Ho una lista di coordinate con le persone apparire vicino a loro - ho bisogno di un algoritmo per ordinare gente da sinistra in alto a destra in basso in un elenco (array), e il secondo criteri di richieste che coordinate che sono più vicini verso la parte superiore origine sinistra prendere prescendance over tutti gli altri - come si dovrebbe fare questo?

Il codice dovrebbe mostrare l'ordine come:

1. Tom
2. Harry
3. Bob
4. Dave

Vedere lo schema qui di seguito:

Answer 1

Da vostra ordinazione, sembra che si sta mettendo posizione y con una priorità più alta rispetto alla posizione x, quindi qualcosa di simile potrebbe funzionare quando si confrontano due persone:

if (a.y > b.y)
// a is before b
else if (a.x < b.x)
// a is before b
else
// b is before a

modifica per l'aggiornamento Questo confronto funziona ancora con i nuovi criteri. posizione Y è ancora ha la precedenza sulla posizione X. Se i valori Y sono uguali, il punto più vicino all'angolo superiore sinistro sarebbe quello con il valore X più piccolo. Se si desidera rendere il vostro oggetto un comparatore, applicazione del presente come la vostra funzione di confronto permetterebbe di fare ArrayList.sort (), dove negativo significa che la prima persona è prima del secondo:

public int compareTo(person a, person b) {
    if (a.y == b.y)
       return a.x-b.x
    else
       return b.y-a.y
}

//compareTo(Tom, Harry) == -50 (tom is before harry)
//compareTo(Tom, Bob) == -25 (tom is before bob)
//compareTo(Dave, Bob) == 30 (dave is after bob)

Answer 2

Ordine in base alla loro distanza dall'angolo in alto a sinistra del vostro 2D-Space, in questo caso (0, 100).

EDIT:

Ovviamente questo significa che si avrà casi in cui 2 persone sono equidistanti dall'angolo in alto a sinistra, eppure sono in nessun posto vicino l'un l'altro.

In questo caso, è necessario specificare come si desidera queste persone di essere ordinati. Se si vuole scegliere le persone che sono più in alto, è possibile ordinare di y-coord prima. Allo stesso modo si può scegliere qualche altro criterio.

Tutti gli altri algoritmi di ordinamento avranno lo stesso problema, di cosa fare quando 2 oggetti hanno la stessa chiave di ordinamento. Per definizione allora, sono considerati identici fino a quando si arriva con un criterio di ordinamento secondario.

Answer 3

direi:

orderValue = x+(100-y)

Poi ordinamento basato sul orderValue più piccole sono le più "vicino" (secondo la distanza proiettata sulla linea y = 100-x) all'inizio-sinistra.

Answer 4

Se si conosce ordine di grandezza massima di X, sort by (per il dato esempio) 100 * (100 - Y). + X

Answer 5

Il comparatore assomiglia a questo:

int d = o2.y - o1.y;
if (d == 0)
    d = o1.x - o2.x;
return d;

Questo sarà ordina per Y, poi da X (per tutti gli oggetti che hanno la stessa Y).

[EDIT] Fixed ordinamento Y.

Answer 6

Può essere che si poteva guardare nella formula Haversine che viene utilizzato in navigazione per il calcolo di prossimità da due punti. Tuttavia, questo vale soprattutto per i punti su una sfera. http://en.wikipedia.org/wiki/Haversine_formula