Come posso identificare in quale regione cade un punto generato casualmente su una mappa?Ho già postato questa domanda su StackOverflow ma è stato indicato alla community poiché è più probabile che ottenga una risposta. C'è anche una rappresentazione grafica di ciò che il mio problema comporta.
In sostanza, ho una "mappa" composta da diverse regioni rettangolari. Ho accesso alle coordinate di tutti i vertici di ogni regione rettangolare (i loro x_min, x_max, y_min, y_max).
Genero casualmente un punto che si trova ovunque su quella mappa. Conosco le coordinate di quel punto (x e y). Il problema che voglio risolvere è scoprire in quale regione si trova il punto.
quello che ho fatto, è semplicemente passare attraverso una grande dichiarazione di condizione controllando una per una se la coordinata x e y del punto è compresa tra x_min e x_max e y_min e y_max di ogni regione. Tuttavia, sento che ci deve essere un modo più scalabile, generalizzabile ed efficiente per farlo, ma non riesco a trovare un modo per farlo, almeno non qualcosa che non sia in una libreria per un linguaggio di programmazione diverso. Ho pensato di fare qualcosa in cui dividere la mappa a metà, scoprire in quale metà si trova il punto, contare tutte le regioni in quella metà, controllare se è rimasta una regione e, in caso contrario, dividere di nuovo la mappa a metà e ripetere il processo. Semplicemente non ho una buona idea di come possa essere implementato e se sia fattibile o migliore del metodo attuale che ho.
ScriptingfinestreRe: Come identificare in quale regione cade un punto generato casualmente su una mappa?Se stessi inventando un algoritmo per le regioni rettangolari affiancate, userei la funzione KDTable e caricherei tutti i punti d'angolo nella tabella. Qualcosa come questo:
one to four rectangles share each cornerda uno a quattro rettangoli condividono ogni angolo
Il KDTable dirà in modo efficiente quale angolo è più vicino a qualsiasi posizione xy interrogata. Se mantieni un'altra tabella di tutti i rettangoli che condividono quel punto, devi solo controllarne fino a quattro. A seconda di come ordini i dati, solo sapere
Il KDTable sta praticamente facendo quello che hai descritto, in K dimensioni. per i dati xy, K==2.
Re: Come identificare in quale regione cade un punto generato casualmente su una mappa?O forse è più difficile.
This will find the wrong corner.Questo troverà l'angolo sbagliato.
Re: Come identificare in quale regione cade un punto generato casualmente su una mappa?Quanta risoluzione ti serve? Se una bitmap da 10K per 10K sarebbe abbastanza buona e ci sono meno di 16E6 poligoni, puoi disegnare i rettangoli nella bitmap con colori univoci (2^24 colori sono 16 milioni di colori) e interrogare istantaneamente un pixel xy arrotondato. Ho fatto qualcosa del genere in JSL BLOB in un orologio ESP32 per le ricerche GPS in una mappa del fuso orario. Nel mio caso, ho preso la risoluzione che potevo ottenere che era un miglio o due vicino al confine del fuso orario; Non avevo bisogno della velocità tanto quanto essere in grado di codificare la bitmap in lunghezza per adattarla a un piccolo computer.
edit: a quanto pare ho creato una bitmap così grande
composition = J( 16000, 30000, 0 );
che ha esaurito la memoria o ha superato un limite di pixel se sono andato più grande ... Ho usato 16000 per la latitudine di +/- 90 gradi e 30K (non 32K) per la longitudine di +/- 180 gradi. Questo è più di un GB non compresso. Avresti bisogno di un file PNG, NON di un JPG. JPG non conserverebbe i colori.
