Il modo migliore per ottimizzare il set di dati che contiene stringhe di linea. Alcune linee iniziano e terminano alle stesse coordinate

Question

IL SETUP
Ho una tabella che contiene linestring. I linestring sono composti da più punti geografici. Ogni punto è costituito da una latitudine e una longitudine. Nota: il valore di linestring è memorizzato come TEXT nel database.

Quindi una riga della tabella potrebbe apparire così:
id: un numero intero
linestring: x1, y2, x2, y2, x3, y3, x4, y4

IL PROBLEMA
Google Maps consente di visualizzare solo fino a 1000 elementi alla volta. Nel mio caso, sto visualizzando 850 linestring e dovrò aggiungerne molti altri in futuro.

LA DOMANDA
Molte delle stringhe di linea si collegano con una o più altre stringhe di linea, il che significa che iniziano e / o finiscono con le stesse coordinate. Quello che vorrei fare è trovare il modo migliore per ottimizzare il set di dati in modo che i linestring che si collegano alle estremità vengano uniti nella tabella DB. Ciò ridurrà il conteggio totale degli elementi quando analizzo la tabella DB e creo il file di visualizzazione per google maps.

Esempio
In questo esempio, immagina, i valori alfa (A, B, C) rappresentano i punti geografici. La tabella non ottimizzata potrebbe apparire così:

prima dell'ottimizzazione:
ID linestring
1 A, B, C
2 C, D
3 B, A
4 F, G, H
5 G, I
6 H, J

---

Dopo l'ottimizzazione:
1 A, B, C, D
2 F, G, H, J
3 G, I

---

Qual è il modo migliore per ottimizzare i dati? Esiste un algoritmo particolare che funziona meglio? Ho alcune idee per soluzioni che formulerò e aggiungerò, ma sembrano prolissi e convulsi.

Non sono un CS maggiore, quindi scusa la terminologia sciatta e fammi sapere se è necessario chiarire ovunque. Grazie!

---

Cordiali saluti .. Sto usando un DB MySQL. Non sto usando le estensioni spaziali. Se hai una soluzione imbarazzante e semplice che utilizza le estensioni spaziali, mi piacerebbe comunque sentirne parlare.

Answer 1

Una cosa da capire è che, se esiste più di una stringa lineare che può essere connessa a una data stringa lineare, non importa quale sia stata scelta - il numero finale di linee lineari nel la tabella ottimizzata sarà la stessa.

Quindi, in quel caso, una semplice strategia avida di trovare ripetutamente una coppia di linestring che possono essere uniti e unirli fino a quando non riesci più a trovare una tale coppia ti darà una tabella ottimale. In sostanza lo pseudocodice è:

while (there exists a pair of linestrings x and y that share an endpoint) {
    delete(x)
    delete(y)
    insert(x . y)
}

Questo non può essere fatto in una singola query SQL a causa della possibilità che il risultante linestring x. y verrà utilizzato di nuovo. Dovresti essere in grado di scrivere il ciclo while usando un linguaggio procedurale come T-SQL o un linguaggio di scripting (ad esempio Perl, usando DBI per l'accesso al database) e usando una query SQL SELECT per trovare una coppia o un elenco di coppie e quindi elaborandoli ciascuno usando le istruzioni DELETE e INSERT.

Suggerirei di aggiungere due campi alla tabella, inizio e fine e indicizzarli per accelerare la ricerca.

Answer 2

Penso che il modo più semplice per andare qui sia usare le estensioni spaziali MySQL.

In particolare ho usato solo estensioni spaziali Oracle. In Oracle possiamo usare funzioni come SDO_GEOM.RELATE o SDO_RELATE tra i due oggetti (contiene, tocchi, incroci, ecc.)

Sono sicuro che esiste una funzione spaziale equivalente in MySQL

EDIT:

Ecco un link che mette a disposizione tutti i collegamenti disponibili di MySQL funzioni.

Answer 3

Ci sarà una soluzione unica se ogni endpoint appare al massimo due volte (terminando una stringa lineare e iniziando un'altra), ma è garantito? Per esempio. cosa succede se hai:

1. A, B, C
2. C, D
3. C, E, F

Questo dovrebbe produrre:

1. A, B, C, D
2. C, E, F

o

1. A, B, C, E, F
2. C, D

O non ti interessa?