2
J'applique l'algorithme de recherche de chemin A * dans un moteur basé sur une grille, mais je souhaite créer des nœuds dans des zones polygonales plutôt que d'utiliser simplement les points de la grille.Algorithme de division d'une grande surface en polygones convexes
Il y aura des obstacles dans la zone, qui ne devraient pas être déplacés. Je me demande s'il existe un algorithme qui peut diviser une plus grande zone avec des obstacles en un graphique avec le plus petit nombre possible de polygones convexes connectés?
Chaque polygone sera un sommet dans un graphique connecté, que je vais utiliser pour naviguer. Je pensais que le plus petit nombre de vertex possibles serait le meilleur pour l'optimisation; le simple fait de diviser la zone en triangles ne me donnera pas le plus petit nombre de nœuds. La coque convexe des points ne fonctionnera pas, car il peut y avoir des obstacles au milieu qui doivent être pris en compte. –
Je ne pense pas que le plus petit nombre de connexions de nœuds soit utile. Mais, dans la plupart des situations, vous pourriez les trouver tous, puis les ranger selon certains critères comme des choses sur le chemin ou quelque chose * quelque chose. – Tatarize