Estremi segmento dati N punti

[gorghino]

Ciao a tutti.
Ho un problema che credo sia geometrico, però coinvolge coordinate e informatica.
Sto lavorando con dei punti coordinate di GoogleMaps (latitudine, longitudine) e il problema di fondo è:
Dati N punti in una via, determinare quali sono gli estremi del segmento che li attraversa.
Però non mi interessa trovare l'interpolante precisa, ma io stavo più percorrendo questa strada:
-Dati i punti ne prendo due a caso A,B
-Per ogni altro punto C verifico se questo sta fuori al segmento A-B o dentro A-B
--Se sta dentro A-B allora lo ignoro (non mi dà nessuna informazione in più)
--Se sta fuori A-B allora C è il candidato per diventare il nuovo estremo del segmento. Quindi calcolo se è più vicino ad A o a B e aggiorno.
Il problema che devo risolvere è dato C, verificare che sia tra A,B o no.
All'inizio avevo immaginato bastasse calcolare la sua distanza con A e con B e se la somma risultava < AB allora stava dentro; ma funziona solo se i punti sono esattamente allineati. Ok che le strade sono abbastanza allineate, ma con la precisione offerta da GMaps il controllo spesso sbaglia
Come mi consigliate di procedere?
Grazie mille!

[giuscri]

Mmm. Provo a dare il mio (terribile) contributo.
Se tu avessi la possibilita' di calcolarti l'equazione del sostegno della curva che passa per gli \( N \) punti, ti basterebbe calcolarti l'integrale curvilineo per ogni possibile coppia: quella che ha il valore piu' alto e' la coppia
\[ ( \text{estremo_1}, \text{estremo_2} ) \]
In questo modo ti salvi anche dal caso in cui la strada sia `molto larga' e ti vengano dati globalmente vicini, ma localmente lontani (mmm, non so come spiegarlo meglio).
[ot]Di che progetto si tratta, in quale linguaggio stai scrivendo la procedura?[/ot]

[gorghino]

Hmmm forse non ho capito bene io, ma se devo fare comunque un calcolo per ogni possibile coppia, a questo punto potrei calcolarmi la distanza A-B e ritornarmi i vertici con distanza maggiore, no?

Non voglio che il sistema sia perfetto su ogni possibile strada (vedi tornanti o incroci strani)..un margine di errore mi va anche bene. Alla fine quei N punti sono notifiche di traffico, e io devo rappresentare con una riga rossa dove sta la coda.
Il progetto lato client è in JavaScript e trovi il prototipo qui: http://ltw1306.web.cs.unibo.it

[giuscri]

"gorghino":Hmmm forse non ho capito bene io, ma se devo fare comunque un calcolo per ogni possibile coppia, a questo punto potrei calcolarmi la distanza A-B e ritornarmi i vertici con distanza maggiore, no?

Intendi dire la procedura che proponi nel primo post? Si ...ma quello mi pare sia l'ultimo dei problemi. La vera questione --a mio parere-- e' calcolare la distanza fra due punti della traiettoria (con traiettoria sconosciuta).

"gorghino":Alla fine quei \( N \) punti sono notifiche di traffico, e io devo rappresentare con una riga rossa dove sta la coda.

Mhn. Quindi: hai un set che campiona una coda di macchine e vuoi trovare i due punti piu' lontani per fornire una stima del traffico lungo una strada, corretto?

Non so che dire --ma sicuramente fra un po' (spostato nella sezione giusta)-- arrivera' una carrelata di gente molto piu' competente di me.

Ad ogni modo una mano te la do volentieri, fin dove riesco e se serve.

Non so se puo' servire, ma potresti cominciare a postare un set di \( N \) punti gia' acquisito? (Se ne hai uno).

[gorghino]

"giuscri":
Intendi dire la procedura che proponi nel primo post? Si ...ma quello mi pare sia l'ultimo dei problemi. La vera questione --a mio parere-- e' calcolare la distanza fra due punti della traiettoria (con traiettoria sconosciuta).

Hmm per quello Google fornisce una computeDistanceBetween(p1, p2) che mi permette di calcolare la distanza in linea d'aria.

"giuscri":
Mhn. Quindi: hai un set che campiona una coda di macchine e vuoi trovare i due punti piu' lontani per fornire una stima del traffico lungo una strada, corretto?
Non so se puo' servire, ma potresti cominciare a postare un set di \( N \) punti gia' acquisito? (Se ne hai uno).

Sì esatto. Un set possibile che non mi visualizza correttamente è (ad esempio):

lat: 44.4968114,
lng: 11.3278055,

lat: 44.495587,
lng: 11.3281918,

lat: 44.4945998,
lng: 11.3285458,

lat: 44.4964441,
lng: 11.327945;

lat: 44.498319,
lng: 11.3273442

[giuscri]

"gorghino":Per quello Google fornisce una computeDistanceBetween(p1, p2) che mi permette di calcolare la distanza in linea d'aria.

La cosa cambia un pochetto, forse. Scusa, ma se la pianta della mappa e' a scacchiera dovrebbe bastare quella funzione? Se \( \mathcal{P} \) e' l'insieme dei punti, implementa in qualche modo
\[ \mathcal{P} \times \mathcal{P} := \{ ( \mathbf{p}_t, \mathbf{p}_s ) \}_{ 1 \le t, \, s \le \operatorname{len}(\mathcal{P}) } \]
e trova il massimo valore che assume computeDistanceBetween() per le coppie di \( \mathcal{P} \) --leva i doppioni chiaramente.
Se l'idea fa schifo (e mi rendo conto di quanto poco sia raffinata), al momento non mi viene in mente nulla di serio.