Instradamento geospaziale

Sono un programmatore di logistica e mi è stato chiesto di capire se un punto GPS è "fuori rotta" in cui il percorso è costituito da un certo numero di punti geospaziali (latitudine, longitudine).Instradamento geospaziale

Qual è l'algoritmo migliore per determinare se un punto si trova vicino al percorso? Userò C# e SQL Server, ma in realtà non importa molto se so quale algoritmo usare.

Ho considerato

Trovare i due punti più vicini e determinare se l'area del triangolo è al di sopra di un limite specifico.
Utilizzo di vettori per tutte le coppie di punti e quindi controllo per vedere se qualcuno di essi è "simile" al vettore definito dal punto GPS e il punto che determina essere "successivo" nel percorso.

Non ho una laurea in matematica, ma posso probabilmente gestire qualsiasi cosa abbia i termini corretti e un motore di ricerca.

Dovrò effettuare almeno 4000 calcoli all'ora, quindi utilizzare una soluzione di mappatura probabilmente non è accettabile a causa del volume.

fonte

2012-01-18 Doug Heeren

quello che hai chiesto è una domanda interessante. Quella soluzione superficie-triangolo non funzionerebbe perché due punti molto distanti genererebbero un triangolo con un'ampia superficie anche quando il punto è leggermente fuori rotta. Non sono sicuro di avere una soluzione migliore. Grazie per avermi dato qualcosa a cui pensare. –

Quale versione di SQL Server stai usando? Hai degli attributi sulla posizione degli autobus diversi da lat/long?Che ne dici di ID bus, ID percorso, ecc. Che possono essere ricollegati alla strada/percorso corretta che dovrebbe essere attiva? – RyanDalton

@RyanDalton 2005 sfortunatamente. A quanto ho capito, il 2012 ha alcune caratteristiche piuttosto carine per quanto riguarda i dati spaziali. Non sono sopra usando mongo o qualche altro database, ma questo finirà per essere un po 'più di lavoro per impostare e mantenere un altro database con informazioni in tempo reale. –

Google per "Along-track distance" e dovresti trovare le formule comunemente usate nel settore dell'aviazione. In alternativa, lo cross-track distance potrebbe anche essere quello che desideri.

fonte

2012-01-18 21:57:17

Grazie, questa sembra essere la risposta che stavo cercando. –

Si può prendere il percorso esistente come una sequenza di segmenti di linea in 2-D, quindi prendere il punto di ricerca e trovare il punto più vicino e il segmento di linea più vicino? La distanza dal punto/segmento di linea più vicino sarebbe la distanza che ti interessa.

Se ti stai attenendo a latitudini relativamente basse (sotto i 60 gradi) potresti essere in grado di trattare la latitudine e la longitudine come se fossero semplicemente piatte, come su una proiezione di Mercatore.

In caso contrario, è possibile trasformare il sistema di coordinate in modo relativo a un grande cerchio che attraversa alcuni dei punti del percorso.

A meno che non abbiate a che fare con milioni di punti di instradamento, non dovreste avere problemi con il tempo della CPU.

fonte

2012-01-18 22:08:43

Questa è una delle formule che ho preso in considerazione, ma ho trovato casi in cui semplicemente non funziona a seconda della forma del percorso. La maggior parte di loro non si trova in alcun luogo vicino a una linea retta e alcuni di essi si raddoppiano su di loro stessi. Diventa ancora più complicato quando il tempo è coinvolto, ma l'ho salvato per un'altra domanda. –

Come qui di seguito ...

scorrere tutti i segmenti di linea

lineSegSlope = Calcolare pendenza per ogni segmento di linea

tracciare una linea di finzione dal punto in questione, che interseca la linea corrente segmento. questo viene fatto invertendo il lineSegSlope e moltiplicando per -1 per ottenere la nuova pendenza, quindi sostituisci il tuo punto di arrivo X, Y e la nuova pendenza in y-y1 = b * (x-x1). La tua X va in x1, la Y in Y1 e la tua nuova Slope in B.

fare un'equazione per il segmento di linea.

se si disegnano le due linee una sopra l'altra, devono creare una X dove ogni angolo è di 90 gradi.

calcolare l'intersezione delle due linee

calcolare la distanza tra il punto di intersezione e il vostro nuovo punto.Se è maggiore di un valore tollerabile, il nuovo punto è troppo lontano.

questo sembra un disastro, ma si spera che dovrebbe funzionare.

fonte

2012-01-18 22:26:17

L'angolo dei punti sulla rotta rispetto al punto in questione è ciò che lo spegne quando ho ragionato. Se il segmento di linea è lontano dal punto, ma l'angolo dei due punti del percorso è tale che la linea è molto vicina al punto in cui è estesa produrrà una risposta errata. Sto faticando a capire un po 'anche se così potrei avere una risposta sbagliata con questo. –

Vedo quello che stai dicendo, buona cattura. Penso che in questo caso, però, le estremità effettive dei segmenti di linea sarebbero i punti più vicini. È quindi possibile calcolare la distanza dal punto di destinazione alle estremità del segmento di linea. Divertente piccolo problema che hai qui. –

Un approccio ingenuo sarebbe quello di inserire il nuovo punto GPS in vari punti lungo il percorso. Inizia inserendolo prima del tuo primo punto P0, quindi tra il tuo primo e il secondo punto P0 e P1, e così via fino a quando non provi ad inserirlo come ultimo punto. Ogni volta che provi ad inserirlo in una posizione, calcola la distanza totale per il circuito e salva la distanza totale più breve. Questo può essere accelerato anticipando le distanze delle gambe e memorizzando quella somma. Controlla la distanza sottraendo la distanza della gamba per la gamba in cui stai inserendo il nuovo punto e aggiungendo la nuova distanza dal punto P (n) al punto GPS a P (n + 1). Se la distanza totale più breve è compresa nel tuo livello di tolleranza, puoi accettarla.

Questo probabilmente non è l'algoritmo "migliore" (a seconda della definizione del migliore) ma è O (n) sul numero di punti nel percorso per la complessità di tempo e spazio. Quindi, a meno che tu non abbia un numero enorme di punti nel tuo percorso, ogni controllo dovrebbe essere un po 'meno di un secondo, quindi questo dovrebbe essere entro i tuoi requisiti di tempo.

Inoltre, assicurarsi di utilizzare haversine distance equations quando si calcola la distanza tra i punti consecutivi sul percorso.

fonte

2012-01-18 22:27:20 andand

La cosa migliore per me è veloce e precisa in una gran parte delle circostanze. Il livello di tolleranza in questa situazione dovrà crescere quando la distanza tra i punti nella rotta è maggiore, vero? –

dovrò fare almeno 4000 calcoli un'ora in modo da utilizzare una soluzione mappatura non è probabilmente accettabile a causa del volume.

In realtà, questo è un esempio PERFETTO in cui una soluzione di mappatura sarebbe utile. Non il tuo tradizionale "guarda una mappa e determina la distanza", ma piuttosto "lascia che il database determini qual è la via più vicina al tuo punto GPS.

Dato che dici di non essere contrario all'utilizzo di un database diverso, potresti considerare :

SQL Server 2008, che ha Spatial Database Engine funzioni o
PostgreSQL con l'estensione open-source PostGIS (spaziale), che ha significativamente più funzioni di analisi spaziale che MS SQL 2008.

Dai un'occhiata alla funzione PostGIS ST_Distance o MS SQL Server 2008 STDistance. Questo è un buon blog entry che descrive i vantaggi di SQL2005 rispetto a SQL2008.

Si potrebbe anche prendere in considerazione la lettura (o la richiesta di una mappatura più dettagliata) post su gis.stackexchange. L'intero gruppo è dedicato all'analisi spaziale. Alcune buone discussioni per voi di prendere uno sguardo al sarebbe

fonte

2012-01-19 22:26:12 RyanDalton

Grazie. Ho invitato un amico a consigliare gis.stackexchange anche a me. La velocità è la mia preoccupazione per l'utilizzo di una soluzione di mappatura. Devo almeno un minimo di 4000 di questi un'ora. Ma hai ragione è probabilmente la soluzione più accurata. –

risposta

Problemi correlati