Bref, quel est le problème ? Imaginez un plan 2D avec des points qu'on appelera "nœuds" dessus. Le problème est de trouver les nœuds voisins (notion que j'invente pour le problème, pas forcément une notion mathématique existante) de chaque nœud.
Et qu'est-ce qu'un nœud voisin ? La définition "mathématique" que j'ai trouvée est la suivante :
Deux nœuds X et Y sont voisins s'il existe un chemin entre X et Y tel que pour tout point p sur ce chemin, le nœud le plus proche de p est soit X soit Y.
Et des exemples :
Vous avez trois nœuds ici, alignés, avec des chemins dessinés entre les deux. Vous constatez qu'il existe bien un chemin entre 1 et 2 qui valide la propriété précédente, idem pour 2 et 3 (même si un chemin droit marchait aussi, celui-ci fonctionne tout autant), mais pas entre 1 et 3 puisque vous aurez toujours un point sur le chemin qui vous rendra plus proche de 2 que de 1 et 3.
Et dans le cas d'un "triangle" en revanche, ça fonctionne, tous les nœuds sont voisins deux à deux (aucun chemin n'a été dessiné entre 1 et 2 ni entre 2 et 3 mais vous pouvez les trouver sans moi...).
Et du coup la question... Comment je code ça ?
Alors notez que je ne demande pas directement un code C/C++ fonctionnel, mais si vous trouvez des définitions équivalentes à celle-là mais avec une traduction algorithmique plus évidente, ça m'aiderait déjà beaucoup. Parce que tester tous les chemins possibles entre deux nœuds sur un plan (un ensemble plutôt grand déjà...) puis tous les points dessus (même remarque...), ça ne risque pas d'être très rapide.
