Discussion :

[AJMont]

Bonjour à tous,
J'ai précédemment ouvert un billet sur ce problème en commençant une possibilité de résolution qui c'est avéré bien trop longue à calculer.

Voici le problème:
Je voudrais réalisé un programme qui détermine le nombre maximal de triangle non-secants pouvant être réalisé avec n points.

Exemple simple, avec quatre point:

on peut compter 4 triangles

mais avec quinze points nous pouvons obtenir ceci:



Combien y a t'il de triangle dans ce cas là?

Dans ces deux cas les point sont dans une position optimale, mais le problème devient plus difficile visuellement si les point sont placés aléatoirement.

J'ai tenté avec sympy de générer tous les triangles possible avec les point d'une liste pour ensuite nettoyer celle-ci des triangles sécants. C'est vraiment pas optimal...


Quelqu'un a t'il une idée à me proposer?