Come concatenare i punti in un array

Question

Come concatenare i punti in un array

#1 da (1 voti)

0

Ho una serie di punti con lunghezze e rotazioni come questa:

Hobisognodicrearecateneseparatedapuntilecuilineesisovrappongono,mahodavverodeiproblemiafarloinmodoefficiente.

HounaseriedisemplicioggettiPoint,innessunordineparticolare,epossopassarliinloopetestarliconunasemplicefunzione"intersect". Devo finire con una serie di catene, ognuna con un elenco ordinato di punti. (O un altro modo di rappresentare le catene).

Al momento tutte le vie che esploro sembrano coinvolgere un intricato anello di matrici, gomitate e fudge. Non avendo mai studiato Informatica mi chiedo se esiste una sorta di struttura dati o tecnica che si presterebbe bene a questo genere di cose.

data-structures algorithms

posta Josh 12.08.2014 - 00:54

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms

È una cattiva pratica mantenere gli script DML (database schema scripts) e la manipolazione (DML) in diversi moduli Best practice per gli script temporanei (Python)

score 1 · Answer 1

Un algoritmo ingenuo per questo prende tempo O (n ^ 2), cioè, per ogni linea aggiunta al numero totale di linee, prende (molto approssimativamente) il quadrato di quel numero di linee in termini di tempo. Quindi se il controllo di una riga richiede un secondo, se abbiamo 5 righe ci vorranno 25 secondi.

Per elaborare in modo efficiente le intersezioni, possiamo utilizzare un numero di algoritmi diversi. La maggior parte di questi sono gli algoritmi sweep line . Uno comune è l'algoritmo Bentley-Ottmann . Non è l'algoritmo più veloce per questo tipo di attività, ma è abbastanza facile da implementare. Avrai bisogno di un albero di ricerca binario e di un coda di priorità . Sono entrambi i tipi di alberi . In particolare, avrai bisogno di un albero rosso-nero o di un albero binario autobilanciante simile. È necessario anche un heap binario per creare la coda di priorità.

Questo elaborerà il numero di incroci nel tempo O (n + k) * log (n)). Il tempo logaritmico è inferiore al tempo lineare, quindi questo algoritmo è più efficiente del nostro tentativo ingenuo. Ci sono ovviamente opzioni più veloci ma in genere sono più complesse.