Discussion :

[flamme34]

Bonjour,
Je travail sur un logiciel de CAO en c++, et je souhaiterai savoir si il existait un algo ou une librairie d’ailleurs qui permettrait d'extraire quand cela est possible les polygones formés par une liste de segment.

Je m'explique :
Dans mon logiciel les utilisateurs ont la possibilité de dessiner plusieurs segment, qui forme ou pas, visuellement des polygones. Or l'utilisateur peut demander de remplir ce qui pour lui est visuellement un polygone.
Je doit donc extraire les polygones que peuvent former ces segments.

J'ai déjà un algorithme que j'ai développer permettant de faire ça, mais celui ci peut être parfois un peu lent lorsque l'utilisateur discrétise énormément son dessin.

Voici mon code actuel (en c++):

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
    int nbSegment = static_cast<int>(listeDesSegmentDeLaCouche.size());
    if (nbSegment <= 0)
        return;
 
    for ( unsigned int i = 0 ; i < listeDesSegmentDeLaCouche.size(); ++i)
    {
 
        bool find = false;
        for ( unsigned int j = 0; (j < listeDesPolygonesOuvert.size()) && (find == false); ++j)
        {
 
            if ( listeDesPolygonesOuvert[j].TryToAdd(listeDesSegmentDeLaCouche[i]))
            {
 
                find = true;
                if (fabs( (listeDesPolygonesOuvert[j].GetDebut()-listeDesPolygonesOuvert[j].GetFin()).Size() )<1e-6)
                {
                    listeDesPolygones.push_back(listeDesPolygonesOuvert[j]);
                    listeDesPolygonesOuvert.erase(listeDesPolygonesOuvert.begin()+j);
 
                }
 
            }
 
        }
        if ( find == false)
        {
            Polygone2D newPoly;
            if (newPoly.TryToAdd(listeDesSegmentDeLaCouche[i]))
            {
                listeDesPolygonesOuvert.push_back(newPoly);
            }
            else
            {
                qDebug() << "ErreurLors de l'ajout d'un segment dans un polygone vide";
            }
        }
    }
    bool findAgain = false;
    do
    {
        findAgain = false;
        for ( unsigned int i = 0; i <listeDesPolygonesOuvert.size() && findAgain == false; i++)
        {
            for ( unsigned int j = i+1; j <listeDesPolygonesOuvert.size() && findAgain == false; j++)
            {
                if ( i ==j)
                    continue;
                findAgain = listeDesPolygonesOuvert[i].TryToAdd(listeDesPolygonesOuvert[j]);
 
                if ( findAgain)
                {
                    listeDesPolygonesOuvert.erase(listeDesPolygonesOuvert.begin()+j);
                    if (fabs( (listeDesPolygonesOuvert[i].GetDebut()-listeDesPolygonesOuvert[i].GetFin()).Size() )<1e-6)
                    {
                        listeDesPolygones.push_back(listeDesPolygonesOuvert[i]);
                        listeDesPolygonesOuvert.erase(listeDesPolygonesOuvert.begin()+i);
                    }
                }
            }
        }
    }while (findAgain);

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool Polygone2D::TryToAdd(Segment2D segment)
{
    if ( listeDesPoints.size()== 0)
    {
        listeDesPoints.push_back(segment.point1);
        listeDesPoints.push_back(segment.point2);
        return true;
    }
    else
    {
        if ( fabs((segment.point1 - GetDebut()).Size())<1e-6)
        {
            Add(segment.point2, false);
            return true;
        }
        else if ( fabs((segment.point1 - GetFin()).Size())<1e-6)
        {
            Add(segment.point2, true);
            return true;
        }
        if ( fabs((segment.point2 - GetDebut()).Size())<1e-6)
        {
            Add(segment.point1, false);
            return true;
        }
        else if ( fabs((segment.point2 - GetFin()).Size())<1e-6)
        {
            Add(segment.point1, true);
            return true;
        }
 
    }
    return false;
}

Code c++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
bool Polygone2D::TryToAdd(Polygone2D poly)
{
    bool add = false;
    bool sensAjout = false ; //false = croissant true decroissant
    bool ajoutALaFin = true;
 
    if ( listeDesPoints.size()== 0)
    {
        add = true;
        sensAjout = false;
        ajoutALaFin= true;
    }
 
    else if ( fabs( (GetFin()- poly.GetDebut()).Size())<1e-6)
    {
        add = true;
        sensAjout = false;
        ajoutALaFin = true;
    }
   else if ( fabs( (GetFin()- poly.GetFin()).Size())<1e-6)
   {
       add = true;
       sensAjout = true;
       ajoutALaFin = true;
   }
    else if ( fabs( (GetDebut()- poly.GetDebut()).Size())<1e-6)
    {
        add = true;
        sensAjout = false;
        ajoutALaFin = false;
    }
   else if ( fabs( (GetDebut()- poly.GetFin()).Size())<1e-6)
   {
       add = true;
       sensAjout = true;
       ajoutALaFin = false;
   }
 
    if ( add)
    {
        if (sensAjout == false)
        {
            for ( int i = 0; i < poly.GetNbPoint(); ++i)
            {
                Add(poly.GetPoint(i),ajoutALaFin);
            }
        }
        else
        {
            for ( int i = poly.GetNbPoint()-1; i >=0; --i)
            {
                Add(poly.GetPoint(i),ajoutALaFin);
            }
        }
        return true;
    }
    return false;
}

Merci d'avance pour vos suggestions

[Flodelarab]

Bonjour

Manifestement, tu cherches des cycles dans un graphe.

Que penses-tu de tout ce qu'on trouve sur internet ?

[flamme34]

Bonjour,
désolé de ne pas avoir répondu plus tôt, mais avec le pont je n'ai pas pu passer plus tôt.
EN effet je n'avais pas vu ça sous ce point de vue.
Je vais regarder ça.