Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Si on se contente d'intervertir les destinations des arcs "haut" et "bas" on risque très fortement de se retrouver avec des zones de "proches" très très allongées, et donc de ne plus réussir à se déplacer efficacement autour du point.
(Coucou Flady ; ) Ou mieux encore, utiliser les exceptions php pour gérer les erreurs mysql, traiter séparement les erreurs de doublons d'entrées, etc. : p )
Oui, evidemment, si on depasse plusieurs points, il faut se deplacer le long de la direction en question jusqu'au point le plus proche de la position finale... et lier l'arc de la direction opposé a ce point.Envoyé par Blustuff
En fait on arrive (presque) a un algo de path finding avec une liste de points de passage
Je parle du maintien du graphe, pas de la recherche.
moi aussi : un maintien du graphe lors d'un déplacement pourrait se faire via un algo *ressemblant* a un algo de path finding
Je ne vois absolument pas comment.
Par exemple, considérons la situation suivante :
Le rectangle rouge contenant strictement le point 1 représente la situation initiale : dans notre graphe, le point 1 est lié par quatre arcs au points respectifs 2, 6, 8 et 7. On dépalce le point 2, qui prends la place notée 3. Si on suit ta proposition, il me semble qu'on agrandit le rectangle rouge vers le haut pour se coller aux contours vert, délimité par les points 4, 6, 8 et 7. Mais il aurait peut être été plus habile de réduire la largeur du rectangle initial en un nouveau rectangle délimité en bleu par les points 4, 5, 8 et 7.
Ce deuxième rectangle a des propriétés fortes il me semble que n'a pas la première construction. On aurait pu le construire par un algorithme :
Centrer un petit carré sur le point 1.
Faire grandir tous ses cotés simultanément jusqu'à se cogner à un point.
Lorsque l'on bloque contre un point, on fixe le position de l'arrête : elle ne pourra que grandir, plus se déplacer.
On recommence à faire grandir les cotés, jusqu'à ce qu'ils soient tous immobilisés par un point.
(Un carré de baudruche que l'on gonfle en se posant contre les pions)
L'avantage de cette construction c'est qu'elle permet d'avoir un meilleur carré, en tentant d'avoir une largeur la plus proche possible de sa longueur.
J'imaginais que cette propriété était importante pour avoir une bonne recherche, sans se perdre à trois kilomètres du point de départ. Peut être en fait que ce n'est pas du tout nécessaire, et que le fait d'avoir des rectangles dans lesquels il n'y a pas d'autres points est suffisant, et alors, on peut prendre n'importe quelle construction de rectangle possible pourvu qu'elle donne bien un découpage du plan. Je vais y réfléchir un peu tout seul encore.
C'est la qu'intervient l'algo de path finding ;o)
Car il ne sert a rien de faire une recherche des points autour de 1 puisque 1 est deja lié a des points qui connaissent d'autres points qui connaissent les points cherchés.
Donc si on déplace 2 en 3, les impacts pour 1 sont :
* L'arc haut doit etre lié a l'arc haut de 2 : a savoir 4 (car 2 depasse 4, sinon l'arc haut serait resté 2)
* L'arc gauche (lié a 6) peut en effet etre reconsidéré, il suffit pour cela de partir de 4 (qui est le résultat d'un arc ayant changé) et de partir a gauche : on trouve 5. 5 étant plus proche que 6, il est choisi.
* De la meme maniere, on peut regarder le point a droite de 4 pour verifier si il n'y pas plus pret que 7
Il suffit donc de se deplacer sur le graphe jusqu'au premier point situé a une distance superieure au point de l'arc deja en place.
En résumé, utiliser le graphe déjà construit pour trouver les points proches, oui, mais c'est la pire des solutions qu'on pouvait imaginer. On ne sait même pas encore qu'une telle représentation permet réellement de trouver tous les points, et de le faire rapidement. On sait déjà qu'il existe des algorithmes pour le faire, ce qui m'intéresse, c'est de le faire rapidement. Autrment dit choisir des réctangles qui ont des propriétés suffisantes pour une rercherche efficace, et que ces mêmes propriétés sont maintenables tout aussi efficacement.
Est-ce qu'il faut également optimiser l'insertion/suppresion de point dans ton quadrillage ? Peut-être peux-tu faire des calculs préléminaires, à l'insertion/suppression de points..
J'imagine ton problème, comme une sorte de bombe qui viendrait s'appliquer sur ton quadrillage, en un point précis, et qui supprimerait tous les points impactés par la déflagration ( d )
Visuellement, je vois donc ça plutot comme un cercle, et pas comme un rectangle, je me trompe ?
K
Je ne vois pas la bombe en fait. Le rectangle a une raison d'être, assurer que l'on puisse bien se déplacer dans le plan. Avec un cercle, on risque de n'avoir qu'un seul point y appartenant. Je ne vois pas bien ce que vous voulez faire avec un cercle.
L'insertion / supression doit pouvoir être rapide effectivement, c'est ce qui pose actuellement problème. Déplacer un pion revient à le supprimer, et à le replacer à sa destination. Si on sait insérer supprimer rapidement, on sait déplacer un pion facilement. La réciproque n'est pas vraiment vraie : /
Dans ma tête, j'imagine donc un cercle, au point d'impact, de rayon d.le problème est de trouver le plus rapidement possible la liste des pions situés à une distance (euclidienne) inférieure ou égale à d de la case donnée.
Tu peux donc extraire une "sous-matrice" et pour chaque point de cette sous-matrice, calculer la distance avec le point centrale de l'impact.. C'est un peu lourd comme calcul, je réfléchis à une optimisation...
K
Comme nous tous, comme nous tous...
Si tu as la place de stockage, tu peux imaginer une sorte de tableau à 3 entrées :
1) en x,y les coordonnées comme tu les as déjà
2) en z, la liste des "distances possibles" ( une 20ène de cases par exemple ? )
Et dans chaque case de z, pour chaque point de ta matrice originale, tu aurais la liste des points se trouvant à cette distance... C'est lourd, méga lourd, lors de l'insertion.. mais... si tu as des distances "constantes" plutot qu'aléatoire, ça pourrait être jouable ?
Donc, par exemple, imaginons qu'en z, tu aies décidé de mettre 20 profondeur ( correspondant à une distance maximale de 20 cases )
Si tu ajoutes un point sur la grille; prendre les points situés à 1d de ce nouveau point; ajouter à la position 1 du z de chacune de ces cases, la référence vers le pion.
Continuer comme ça 20 fois...
Désolé si je suis à coté de la plaque
K
Je ne suis pas d'accord du tout. ici, le déplacement est facilité par la présence du graphe, et le pion a déplacer comporte des informations qu'un nouveau pion ne comporte pas (a savoir ses 4 arcs liés). Il ne faut pas s'en priver lors du déplacement, pour savoir quels autres pions mettre a jour, et pour trouver les 4 autres arcs auquels il sera lié
Je pense que dans la majorité des cas (> 80%) la recherche du plus proche voisin par parcours du graphe tel que je l'ai décrit sera rapide (1, 2 iterations max), et rien ne t'empeche de brider le calcul pour eviter l'explosion
J'ai bien précisé que la réciproque n'était pas vraie. Je ne crois pas du tout en le "Une ou deux" itération tant que je n'ai pas de preuve. Je peux donner un contre exemple dans lequel on a construit des rectangles de telle manière que le graphe construit ne soit pas connexe et donc que la recherche de chemin risque de ne pas aboutir. (Ce qui est assez gênant) Oh, bien sûr, la construction des rectangles ne correspond pas à la seconde construction, mais on est jamais à l'abris. Là, où ça coince, c'est que le point de destination n'est pas encore dans le graphe, et qu'il faut l'insérer. Ce qui rend plus difficile la construction du rectangle autour du point 4. (Elle ne peut pas suivre l'algorithme présenté) Il faudra bien entendu reconstruire le graphe sur tous les sommets entourant 4, ce qui peut bien représenter 8 rectangles, peut être plus, peut être moins. Enfin, je pense pouvoir montrer un exemple dans lequel l'algorithme ne construit pas de rectangle ayant la "propriété supposée intéressante", mais je ne suis pas sûr que ce soit indispensable.
KiLVaiDeN, j'aimerais si possible une méthode qui n'admet pas d'erreur. (Pas de limite arbitraire) On devrait effectivement pouvoir calculer la liste des pions de distance inférieure à une certaine constante. Malheureusement, le calcul de cette "liste" est aussi difficile que le problème lui même : en fait, tu cherches juste à stocker les solutions du problème une fois qu'on les a il me semble.
bon, une autre idée alors ;o)
transformer ton plan en calotte de sphere et changer le systeme de coordonnée :
chaque point étant alors représenté par les 2 angles alpha et beta :
* alpha l'angle entre la droite D (passant par le centre du plan et le centre de la sphere sur laquelle repose la calotte) et le point sur la calotte (ie : un point au milieu du plan aura un angle alpha = 0°)
(alpha défini donc un cercle sur le plan d'origine le centre du plan)
* beta l'angle entre une direction arbitraire sur le plan et le point (beta défini donc 1 demi droite partant du centre du plan)
Le point étant l'intersection du cercle de la demi droite.
La question a 100 balles étant : n'est-ce pas plus simple de calculer la distance entre 2 points a partir des 2 angles qu'a partir des coordonnées x,y ?
Je laisse les matheux s'amuser avec les formules, c'est pas trop mon truc ;o)
Et si c'est trop capillo-tracté, oubliez, c'est pas grave ;o)
J'vois pas tellement c'que tu veux gagner en fait. Calculer les distances dans le plan, c'est facile. Tu cherches un moyen de rendre plus rapide le calcul de distance ?
oué, il me semblais me souvenir, de mes vagues reminiscences estudiantines que les calculs de distances a l'aide d'angles étaient plus simples
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager