Segments de ligne sans intersection tout en minimisant la longueur cumulée

Je voudrais trouver un meilleur algorithme pour résoudre le problème suivant:

Il y a N points de départ (violet) et N points cibles (vert) en 2D. Je veux un algorithme qui relie les points de départ aux points cibles par un segment de ligne (marron) sans qu’aucun de ces segments ne se recoupe (rouge) tout en minimisant la longueur cumulée de tous les segments.

Mon premier effort en C ++ consistait à permuter tous les états possibles, à trouver des états sans intersection et, parmi ceux-ci, l’état avec une longueur de segment totale minimale O (n!) . Mais je pense qu’il doit y avoir un meilleur moyen.

entrer la description de l'image ici

Une idée? Ou de bons mots-clés pour la recherche?

C’est la correspondance euclidienne minimale en 2D . Le lien contient une bibliographie de ce qui est connu sur ce problème. Étant donné que vous voulez minimiser la longueur totale, la contrainte de non-intersection est redondante, car la longueur de toute paire de segments croisés peut être réduite en les décroisant.

Vous pouvez sélectionner une connexion aléatoire, puis chaque fois que vous supprimez une croix (en fait, modifiez la connexion de leurs extrémités), cet algorithme fonctionne et se termine en étapes finies. Vous dites peut-être que changer de croix entraîne une nouvelle croix, peu importe, chaque fois que vous changez de croix, vous minimisez la longueur totale de votre réponse et cette manière ne peut être infinie (parce que la longueur totale des lignes est finie). Fonctionne en fait dans O (F * n ^ 2) où F= sum of all line segments * power of 10 (pour le rendre entier). Cet O est très optimiste, je pense que si vous essayez cet algorithme simple, il fonctionnera très bien. Bien sûr, c’est bien mieux que la force brute en général.

On dirait que vous pourriez utiliser un algorithme de type BSP .

Utilisez cet algorithme avec l’ordre O (n 3 ) :

L’algorithme hongrois est un algorithme d’optimisation combinatoire qui résout le problème d’affectation en temps polynomial.

Comment ça peut aider? Eh bien, il trouvera juste la longueur cumulative minimale. Mais…

LORSQUE LA LONGUEUR TOTALE EST MINIMALE, IL N’Y A PAS D’INTERSECTION.

Donc, comme @ qq3 dit que la contrainte d’intersection est redondante et après avoir supprimé cette contrainte, elle peut réduire l’ordre de O (n!) À O (n 3 ) .