Ricerca di posizioni appropriate per le coordinate aggiunte a un elenco di coordinate

Sto cercando il modo più efficiente per trovare la posizione appropriata di una coordinata geografica in un elenco di altre coordinate (geografiche) che formano un percorso.

Potrebbe sembrare un po 'criptico, ma considera questo:

Condizioni
Ho i seguenti dati su cui lavorare:

• Un elenco di coordinate (cartesiane) che descrivono un percorso geografico (la coordinata-lista )
• Un elenco di coordinate (cartesiane) per i punti di interesse (POI) distribuiti lungo il percorso (la lista dei PDI )

Quello che sto cercando di fare è unire le coordinate dalla lista POI alla coordinata-lista nelle loro posizioni appropriate, in modo che la coordinata- lista è ordinata nello stesso ordine in cui raggiungerei tutte le coordinate, compresi i POI, se dovessi percorrere il percorso.

So in quale ordine i POI dovrebbero essere "aggiunti".
Cioè il secondo POI dovrebbe avere un indice più alto di quello del primo POI e così via.

Approccio attuale
Quello che sto facendo sta iterando l'intera coordinata-lista una volta per coordinata nella lista POI , e per ogni coordinata calcolando la distanza tra il POI e la linea formata dalla coordinata e dalla coordinata successiva nella lista di coordinate .

Considera il seguente codice:

shortestDistance = /* distance between the first two coordinates */;
index = 0;

for(POI poi : poiList) {
    for(i = 0; i < coordinateList.size(); i++) {
        Line line = new Line(coordinateList.get(i), coordinateList.get(i + 1));
        int distance = distanceBetween(line, poi);

        if(distance < shortestDistance) {
            shortestDistance = distance
            index = i
        }
    }

    /* "index" now represents the index of the "coordinateList" at which the POI-coordinate should be added */
}

Ai miei occhi questa soluzione è estremamente inefficace e deve esserci un modo più veloce per farlo ...

Il requisito
Simile alla soluzione attuale, la nuova soluzione deve essere in grado di gestire tutte le situazioni che può causare una rotta automobilistica generata automaticamente, ad esempio situazioni in cui il percorso fa un'inversione a U e torna nella direzione opposta vicino a sé. / p>

La soluzione dovrebbe essere il più veloce possibile.
Il multithreading è consentito!