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:
da 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.
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.
Re: Come identificare in quale regione cade un punto generato casualmente su una mappa?Perché i rettangoli non sembrano essere ruotati e non si sovrappongono:
Quattro controlli/loop e rimuovi sempre quelli che non corrispondono:
1. Controlla tutti i quadrati che hanno x_min più piccolo del punto x
2. Controlla da tutti i quadrati, che sono rimasti, che hanno x_max maggiore del punto x
3. Controlla da tutti i quadrati, che sono rimasti, che hanno y_min più piccolo del punto y
4. Controlla da tutti i quadrati, che sono rimasti, che hanno y_max maggiore del punto y
E puoi fermarti in qualsiasi punto di questi se rimane solo un quadrato. Nel caso di JMP puoi farlo con l'aiuto di Loc().
Oppure esegui il loop su tutti i valori minimi massimi dei quadrati e interrompi quando trovi una corrispondenza con qualcosa del tipo:
:xmin < x < :xmax & :ymin < y < :ymax
Un paio di link che potrebbero essere correlati e avere possibili soluzioni più fantasiose:
https://stackoverflow.com/questions/1897779/test-if-point-is-in-some-rectangle
https://www.reddit.com/r/programming/comments/80dlc/i_have_a_set_of_rectangles_and_need_to_determine/
