Sally (./41190) :
Sinon pour la capture je ne vois pas vraiment comment tu peux faire autrement que garder dans un coin la liste des intersections qui constituent le groupe, mais peut-être que tu peux faire ça comme une bête liste de coordonnées, et en cas de capture tu reconstruis la structure ? il y a en général moins d'une dizaine de captures dans une partie non ?

peut-être qu'il y a peu de captures effectives dans une vraie partie (parce que si y a capture c'est plus ou moins qu'un joueur a mal joué) mais que si on joue au hasard comme avec monte-carlo ça arrive bien plus souvent ?

Pollux > mais même s'il savait quels groupes sont en contact ça ne résoudrait pas vraiment le problème, il faut qu'il connaisse la forme du groupe qui est capturé pour pouvoir reconstruire son graphe... ah ou alors tu veux dire que ça lui permettrait de savoir quelle partie du graphe est affectée et d'éviter de tout reconstruire ?

Ah oui je n'ai pas dit que c'était suffisant, j'ai juste montré du doigt le problème... Pour le résoudre la solution la plus naturelle ça me paraît être de rajouter un nouveau type d'arête étiquetée partant d'une chaîne n et aboutissant à une chaîne ou une intersection x : par exemple si n -(i)> x alors l'intersection i doit être ajoutée à la liste des voisins de x si n est détruit. Du coup la destruction d'un groupe est juste en O(périmètre) et non en O(aire)...