Naming questo algoritmo: confronto e interpolando i punti?

Question

la mia domanda potrebbe essere un po 'strano. Ho "sviluppato" un algoritmo e non so se c'è un algoritmo simile già là fuori.

La situazione: Ho un tracciato definito da punti (2D). I punti rappresentano giri per esempio. Tra i punti ci sono solo linee rette. Ora sto Dato un insieme di coordinate in questo spazio 2D. A calcolare la distanza dal primo punto traccia per le nuove coordinate e la distanza per l'intervallo per i primi due punti. Se la distanza alle coordinate misurate è inferiore alla distanza dal primo al secondo punto traccia, sto supponendo che questo punto si trova tra questo intervallo. Ho poi fare un interpolazione lineare su questo. Se è più grande, io controllerò con il successivo intervallo.

Quindi è fondamentalmente prendendo distanze intervallo e cercando di farli stare in là. Sto cercando di seguire un oggetto in movimento approssimativamente lungo questa pista.

Se questo suona familiare a qualcuno? qualcuno può venire con un suggerimento per un algoritmo esistente simile?

Modifica Da quello che ho affermato finora, tengo a precisare che una posizione non è moltiplicare associato per tracciare punti. Si consideri il bene ASCII disegno Jonathan ha fatto:

La posizione X è risultato essere all'interno Segmento 1 e 2 (S12). Ora la posizione successiva è Y, che non è da considerarsi abbastanza vicino per essere su S12. Mi sposterò a S23, e verificare se è in.

Se si trova, non sarò controllando S12 per qualsiasi altro valore, perché ho trovato uno nel segmento successivo già. L'algoritmo di "non guardare indietro".

Ma se non trova il segmento proprio da lì, perché happenend essere quello lontano dal primo segmento, ma ancora più lontano da qualsiasi altro segmento in ogni caso, farò cadere il valore e la posizione successiva sarà essere cercata nel S12, ancora una volta.

Il ciclo rimane ancora un problema. Considerate Ottengo Y per S23 e poi saltare due o tre posizioni (in quanto sono troppo lontani), potrei essere perdendo il conto. Ho potuto determinare una posizione in S34 in cui sarebbe già in S56.

Forse posso venire con una certa velocità media di Våge dire in che segmento che dovrebbe essere.

Sembra che il più grande i segmenti sono, maggiore è la possibilità di fare una decisione giusta.

Answer 1

Ciò che mi preoccupa sull'algoritmo che hai descritto è che è 'avidi' e potrebbe scegliere il segmento di traccia 'sbagliato' (o, almeno, un segmento di pista che non è il più vicino al punto).

È ora di spingere l'arte ASCII ai limiti. Si consideri il seguente percorso (numeri rappresentano la sequenza nella lista dei punti), e la coordinata X (e, successivamente, Y).

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

Come dovremmo interpretare descrizione?

  

[C] alculate la distanza dal primo punto traccia per le nuove coordinate e la distanza per l'intervallo per i primi due punti. Se la distanza alle coordinate misurate è inferiore alla distanza dal primo al secondo punto traccia, [supporre] che questo punto si trova tra questo intervallo; [...] [s] è più grande, [...] verificare con il successivo intervallo.

Credo che la prima frase significa:

• Calcolare la distanza da TP1 (punto traccia 1) per TP2 - chiamarlo D12
.
• Calcolare la distanza da TP1 a X (chiamarlo D1X) e da TP2 a X (chiamarlo D2X).

La parte difficile è l'interpretazione della frase condizionale.

La mia impressione è che se uno D1X o D2X è inferiore D12, allora X sarà considerata on (o più vicino troppo) il TP1 segmento di pista per TP2 (chiamarlo segmento S12).

Guardando la posizione del X nel diagramma, è moderatamente chiaro che sia D1X e D2X sono più piccoli di D12, quindi la mia interpretazione del vostro algoritmo interpreterebbe X come associati con S12, ma X è chiaramente più vicino a S23 o S56 che è di S12 (ma quelli vengono scartati senza nemmeno essere considerato).

ho frainteso qualcosa sul vostro algoritmo?

A pensarci un po ': quello che ho interpretato l'algoritmo a dire è che se il punto X si trova all'interno o il cerchio di raggio D12 centrata TP1 o il cerchio di raggio D12 centrata a TP2, allora si associano con X S12. Tuttavia, se consideriamo anche punto di Y, l'algoritmo suggerisco che si sta utilizzando sarebbe anche associarlo con S12.

Se l'algoritmo viene raffinato per dire MAX(D1Y, D2Y) < D12, allora non considera Y come collegati alla S12. Tuttavia, X è probabilmente ancora considerato essere correlato alla S12, piuttosto che S23 o S56.

Answer 2

La prima parte di questo algoritmo mi ricorda di muoversi attraverso uno spazio discretizzata. Un esempio di rappresentare uno spazio così è il ordine Z di riempimento dello spazio curva. Ho usato questa tecnica per rappresentare un quadtree , la struttura di dati per un adattiva maglia codice raffinatezza una volta ho lavorato su, e ho usato un algoritmo molto simile a quello che si descrive per attraversare la rete e determinare le distanze tra le particelle.

La somiglianza può non essere immediatamente evidente. Dal momento che sono solo preoccupato per posizioni di intervallo, si sta trattando in modo efficace tutti i punti all'intervallo come equivalente in questo passaggio. Questa è la stessa come la scelta di uno spazio che ha solo punti discretizzata -. Si è effettivamente 'scattare' i tuoi punti per una griglia