Bonjour à tous,
Sur l'image ci-dessus, on trace une droite verticale à partir de chaque sommet jusqu'à ce que celle-ci rencontre soit un obstacle, soit le bord de l'espace de travail.
Les noeuds se trouvent au milieu de chaque segment tracé.
Sachant que l'on dispose de n sommets et n arrêtes, je cherche un algorithme en O(n log n) (en pseudo code) me renvoyant la position des noeuds. Je ne vois pas trop comment faire :s
Si vous avez une solution, ça serait très gentil de m'aider
Merci d'avance,