Discussion :

[begude]

Bonsoir,
je suis à la recherche de pistes et d'idées pour répondre au problème que l'on me soumet et que je dois traiter dans un programme C++ :

J'ai un ensemble de droite (entre 100 et 150) définies par leurs équations.
Elles sont tracées en bleu sur le graphe ci-dessous.
Il faut que j'arrive à trouver l'ensemble des points qui définissent "l'enveloppe intérieure" (je ne sais pas si c'est le terme approprié) de ces droites.
Elle est tracée en rouge.



J'ai cherché du coté des enveloppes convexes, j'ai trouvé un code en c++ qui fonctionne mais c'est pour une enveloppe extérieure...
Je n'ai pas forcément les bons mots clés pour la recherche ?

Merci d'avance pour votre aide.

[ToTo13]

Je traiterai cela comme si c'était une image :
- 1 - je trace toutes les droites
- 2 - je pars du centre

Méthode 1 :
- 3 - je vais dans une direction (n'importe laquelle) jusqu'à rencontrer une droite (pixel coloré car image)
- 4 - j'effectue un simple parcours dans le sens que je souhaite jusqu'à revenir au pixel de départ.

Méthode 2 :
- 3 - je lâche un germe (comme pour la numérotation des composantes connexes) qui se propage et qui est limité par la présence des droites.

[tbc92]

Bonsoir,
Je pense que ça peut se faire de façon 'Exacte' assez rapidement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
nbre_droites est le nombre de droites ( 100 à 150 dans l'exemple)
Pour i = 1 a nbre_droites
  Pour j = I+1 a nbre_droites
       x0,Y0 = intersection des droites i et J
       pour k = 1 a nbre_droites 
           si k <> i  et k<> j alors
              La droite Dk divise le plan en 2 demi-plans, est-ce que ce point (x0,y0) est dans le même demi-plan que (0,0), si oui, on continue, sinon on jette ce point (x0,y0) ; pas la peine de regarder les autres Droites Dk  pour ce couple i,j.
              Autrement dit, Quel est le signe de ak* x0 + bk*y0 + ck  ? Si ce nombre n'est pas du même signe que ck, alors ce point x0,y0 est inutile
           fin
      Next k 
      Si (x0,y0) est utile, on incrémente un tableau, avec : les coordonnées x0,Y0, et les n° des 2 droites i et j
   Next j
Next i

C'est fini ...
On a tous les points utiles, et on a ce qu'il faut pour les ordonner.
Reste une petite galère si 3 droites se croisent en un même point.

[begude]

Bonsoir,
je voulais vous remercier tous les deux pour votre aide.
J'ai pris un peu de temps pour vous répondre car j'ai testé la solution détaillée proposée par tbc92.
J'ai fait un exemple avec une demi-douzaine de courbes formant un polygone autour de l'origine.
Après quelques mises au points (dans mon code), ça marche.
Dans mon cas réel d’application, la physique du truc fait que les chances d'avoir 3 droites se croisant en un même point sont inexistantes. Merci d'avoir attiré mon attention sur ce cas particulier.

Il me reste à tester cela au boulot avec des données réelles.

Bravo encore pour la solution ainsi que sur la clarté et la propreté de l'algo.

[tbc92]

Merci pour le feedback.
En terme de temps de traitement, cet algorithme est en gros en n*n*racine(n) .
Pour n entre 100 et 150, ça fait un nombre de calculs 'raisonnable'.

J'ai en tête un aménagement de cet algorithme. Pour 100 droites, je pense que le rapport bénéfice / inconvénients est équilibré.

Mais si tu as besoin d'un temps de traitement optimisé, ou si tu es amené à traiter 500 ou 1000 droites, n'hésite pas à faire signe.

[souviron34]

En terme de temps de traitement, cet algorithme est en gros en n*n*racine(n) .
...
Mais si tu as besoin d'un temps de traitement optimisé, ou si tu es amené à traiter 500 ou 1000 droites, n'hésite pas à faire signe.

Tiens je suis tombé sur cet article, qui devrait résoudre le problème :

http://arxiv.org/pdf/1412.6619.pdf