Comment identifier la région dans laquelle se trouve un point généré aléatoirement sur une carte ?J'ai déjà posté cette question sur stackoverflow mais a été pointé vers la communauté car elle est plus susceptible d'obtenir une réponse. Il y a aussi une représentation en image de ce que mon problème implique.
Essentiellement, j'ai une "carte" qui se compose de plusieurs régions rectangulaires. J'ai accès aux coordonnées de tous les sommets de chaque région rectangulaire (leurs x_min, x_max, y_min, y_max).
Je génère au hasard un point qui se trouve n'importe où sur cette carte. Je connais les coordonnées de ce point (x et y). Le problème que je veux résoudre est de savoir dans quelle région se situe le point.
ce que j'ai fait, c'est simplement passer par une grande déclaration de condition en vérifiant un par un si les coordonnées x et y du point sont comprises entre x_min et x_max et y_min et y_max de chaque région. Cependant, j'ai l'impression qu'il doit y avoir un moyen plus évolutif, généralisable et efficace de le faire, mais je ne trouve pas de moyen de le faire, du moins pas quelque chose qui ne se trouve pas dans une bibliothèque pour un langage de programmation différent. J'ai pensé à peut-être faire quelque chose où je diviserai la carte en deux, découvrir dans quelle moitié se trouve le point, compter toutes les régions de cette moitié, vérifier s'il reste une région et sinon, diviser à nouveau la carte en deux et recommencer le processus. Je n'ai tout simplement pas une bonne idée de la façon dont cela peut être mis en œuvre et si cela est faisable ou mieux que la méthode actuelle que j'ai.
Scriptles fenêtresRe : Comment identifier la région dans laquelle se trouve un point généré aléatoirement sur une carte ?Si j'inventais un algorithme pour les régions rectangulaires en mosaïque, j'utiliserais la fonction KDTable et chargerais tous les points d'angle dans la table. Quelque chose comme ça:
un à quatre rectangles partagent chaque coin
Le KDTable indiquera efficacement quel coin est le plus proche de tout emplacement xy interrogé. Si vous conservez un autre tableau de tous les rectangles qui partagent ce point, il vous suffit d'en vérifier jusqu'à quatre. Selon la façon dont vous organisez les données, le simple fait de connaître
Le KDTable fait à peu près ce que vous avez décrit, en dimensions K. pour les données xy, K==2.
Re : Comment identifier la région dans laquelle se trouve un point généré aléatoirement sur une carte ?Ou peut-être est-ce plus difficile.
Cela trouvera le mauvais coin.
Re : Comment identifier la région dans laquelle se trouve un point généré aléatoirement sur une carte ?De quelle résolution avez-vous besoin ? Si un bitmap de 10K sur 10K est suffisant et qu'il y a moins de 16E6 polygones, vous pouvez dessiner les rectangles dans le bitmap avec des couleurs uniques (2^24 couleurs correspondent à 16 millions de couleurs) et interroger instantanément un pixel xy arrondi. J'ai fait quelque chose comme ça dans JSL BLOB dans une horloge ESP32 pour les recherches GPS dans une carte de fuseau horaire. Dans mon cas, j'ai pris la résolution que je pouvais obtenir, à savoir un ou deux kilomètres près d'une limite de fuseau horaire ; Je n'avais pas autant besoin de vitesse que de pouvoir coder le bitmap en longueur pour l'adapter à un petit ordinateur.
edit : apparemment j'ai fait un bitmap aussi gros
composition = J( 16000, 30000, 0 );
qui manquait de mémoire ou dépassait une limite de pixels si j'allais plus grand... J'ai utilisé 16000 pour la latitude +/- 90 degrés et 30K (pas 32K) pour la longitude +/- 180 degrés. C'est plus d'un Go non compressé. Vous auriez besoin d'un fichier PNG, PAS d'un JPG. JPG ne conserverait pas les couleurs.
Re : Comment identifier la région dans laquelle se trouve un point généré aléatoirement sur une carte ?Parce que les rectangles ne semblent pas pivoter et ne se chevauchent pas :
Quatre contrôles/boucles et toujours supprimer ceux qui ne correspondent pas :
1. Vérifiez tous les carrés qui ont x_min plus petit que x du point
2. Vérifiez à partir de tous les carrés, qui sont à gauche, qui ont x_max plus grand que x du point
3. Vérifiez à partir de tous les carrés, qui sont à gauche, qui ont y_min plus petit que le point y
4. Vérifiez à partir de tous les carrés, qui sont à gauche, qui ont y_max plus grand que le point y
Et vous pouvez vous arrêter à n'importe quel point de ceux-ci s'il ne reste qu'un seul carré. Dans le cas de JMP, vous pouvez le faire à l'aide de Loc().
Ou alors bouclez sur toutes les valeurs min max et cassez lorsque vous trouvez une correspondance avec quelque chose comme :
:xmin < x < :xmax & :ymin < y < :ymax
Quelques liens qui pourraient être liés et avoir des solutions possibles plus fantaisistes :
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/
