Il punto più vicino all'obiettivo mobile

2

Ho un obiettivo che è in costante movimento e solo la sua posizione corrente è mai conosciuta. Ho anche un centinaio di oggetti che lo circondano, e per ognuno di questi è nota solo la posizione corrente.

Sto cercando di trovare un modo più efficiente per trovare l'oggetto più vicino al mio bersaglio in un dato momento. Ho esaminato una serie di algoritmi, ma nessuno di essi sembra adattarsi a questo (il vicino più prossimo, la coppia più vicina di punti, ecc.).

I miei oggetti sono non ordinati. È necessario che not sia esatto. Il più vicino che ho potuto pensare è l'algoritmo della forza bruta:

Objects objects = MyListOfUnsortedObjects();
Object closestObj = objects[0];
for each (Object obj in objects){
    if(obj is closer than closestObj){
        closestObj = obj;
    }
}
return closestObj;

Ovviamente, questo è terribilmente inefficiente. Sarei stato meglio smistare e poi dividere e conquistare? O vado via base?

Qualche suggerimento?

    
posta Evorlor 25.01.2015 - 02:58
fonte

1 risposta

3

La soluzione è una forma di partizionamento spaziale , che è probabilmente equivalente a "sort e quindi dividi e conquista ", quindi non sei affatto fuori base.

Ci sono molte strutture dati utilizzate per questo, come quadriflessioni, BSP, alberi k-d e così via. Nella mia esperienza personale, le persone raccomandano normalmente il quadrifoglio come buon punto di partenza.

    
risposta data 25.01.2015 - 03:08
fonte

Leggi altre domande sui tag