Un problema interessante da risolvere...

[gurghet]

Ho due linee spezzate formate da un numero finito di punti. Come faccio a sapere se si incrociano?
Ho un problema di (geometria topologica?) XD
Cmq a tutti i matematici:
Ho due linee formate da un numero finito di punti, questi punti approssimano una curva e sono distanziati di p centimetri. Voglio un algoritmo molto efficiente per sapere se almeno n punti hanno una distanza minore di r?
Io da informatico ho pensato:
1. calcolo la distanza dei punti di partenza d(A,A')
2. se è maggiore di r allora vado avanti di d(A,A')/p punti sulla seconda linea fino a raggiungere B' e misuro d(A,B')
3. se è minore allora aumento il contatore dei punti che si toccano di uno
e così via...
10 minuti fa - 3 giorni rimanenti per rispondere.
Dettagli aggiuntivi

9 minuti fa
toccano per modo di dire... nel senso che sono molto vicini...
8 minuti fa
ovviamente d(A,A')/p sarà approssimato per difetto... al primo x € Z

[gurghet]

su yahoo answers hanno risolto una prima parte del mio problema alla radice. innanzitutto la funzione matematica classica d(A,B) è troppo ridondante nel mio caso siccome comprende una radice due quadrati due differenze e una somma. Mi hanno fatto notare che per una valutazione con una buona approssimazione un quadrato o una circonferenza non cambiano di molto la situazione. Quindi mi hanno consigliato di riscrivere d(A,B) da un iniziale $sqrt{(x-x_0)^2+(y-y_0)^2}

Cita

Segnala

[gurghet]

sono sicuro che non state rispondendo perché non si capisce niente di quello che ho scritto. Metterò il problema in soldoni. Sto scrivendo un programma per un videogioco che mi valuta se due percorsi fatti da macchinine si sono avvicinati abbastanza, nel qual caso unisce le due macchinine e ne visualizza una sola.

Siccome il gioco deve confrontare migliaia di percorsi al secondo, l'algoritmo che confronta i percorsi dev'essere più che efficiente. I percorsi non sono altro che un elenco lunghissimo di punti, che sono stati calcolati a priori equidistanti e rappresentano con ottima approssimazione il percorso delle macchinine.

Dato un percorso questo dev'essere confrontato con molti altri e deve essere stabilito per ogni confronto quali avvicina di una certa distanza minima. Molti percorsi devono essere esclusi a priori perché semplicemente sono troppo distanti da quello preso in esame per esserci anche una minima possibilità che si incrocino.

Quelli più vicini vanno confrontati con maggiore precisione in modo che si stabilista per quale tratto le macchinine hanno effettuato lo stesso percorso (con un certo margine di errore).

Grazie mille per l'aiuto

[Fioravante Patrone1]

Sei pregato di modificare il titolo del post, secondo quanto prevede il regolamento, che hai sicuramente letto.


Grazie per la comprensione

[Fioravante Patrone1]

Sei pregato di modificare il titolo del post, secondo quanto prevede il regolamento, che hai sicuramente letto.


Grazie per la comprensione