Bonjour,
Dans le cadre du développement de mon city builder je suis confronté à la problématique de ne pas construire de route au dessus de routes existantes (sans parler d'intersection).
Soient A l'union de splines existantes (les routes qui ont déja été créées) et B la spline en cours de prévisualisation (un premier clic définit le premier point, un second clic le point tangente et des mouvement de souris déplacent le dernier point permettant de visualiser la spline avant validation, cliquer une derniere fois valide le dernier point et donc la spline)
subdiviser chaque spline de A et la spline de B en segments n'étaient pas couteux algorithmiquement grâce à l'algo de de Casteljau (à condition d'avoir un nombre d'itérations raisonnables), mais là où ça devient très couteux cest quand il s'agit de vérifier si B peut être validé, donc si B n'est pas en intersection avec A. Puisque :
40 fois par secondes( B est en prévisualisation, donc chaque mouvement de souris, modifient l'apparence de la spline), il ya 3 boucles emboitées :
Pour tous segments s2 de B -> pour toutes splines de A -> pour tous segments s1 de A (sachant qu'une spline peut contenir une trentaine de segments, donc imaginez si A contient 500 splines...), si s1 est en intersection avec s2 on sort de la fonction en renvoyant false, et B ne peut être validé.
Je me penche alors vers la solution qui consiste à faire une intersection de chaque spline validée avec une grille 2D (par exemple 5000 x 5000).
toutes les splines de A ont été snappée précédemment avec un certain pas, sur la grille. Au moment de prévisualiser B je récupère les indices i et j de chaque points xi ([xi xi+1] mesure un certain pas) de la spline qui correspondent à un snap sur la grille, et si Grid[i][j]->IsOccupied = true, je ne valide pas B.
Cet algo semble bien moins couteux que le précédent, mais y a-t'il mieux svp ?
Partager