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,
 
 
 

http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm
 
Pas exactement ton problème, mais l'idée est là.

C'est quoi la finalité de ce problème ?

Routage?  (Tu completes par un graphe donnant les noeuds accessibles l'un a l'autre et tu as des chemins evitant les obstacles).

En effet, après ça permet de trouver un chemin entre les obstacles.
Merci à 0x90 pour sa réponse, je vais essayer d'adapter l'algorithme de Bentley Ottmann à mon problème. Ca n'a pas l'air évident quand même...

ça ressemble à un calcul de visibilité, mais en plus simple parce que tes points peuvent regarder que dans une seule direction. http://en.wikipedia.org/wiki/Visibility_graph