Discussion :

[Invité]

Bonjour,

J''ai des données correspondant à des points d'une surface d'eau et je cherche à les trianguler. J'ai donc obtenu ces fonctions de mon prof :

Code :

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
 
typedef struct
{
    float	x, y;
} Point2D;
 
typedef struct
{
    Point2D p1, p2, p3;
} Triangle2D;
 
Triangle2D* Terrain::Process( int nb_points, Point2D *points, int& nb_triangles )
{
    /* allocate and initialize list of Vertices in polygon */
    Triangle2D *triangles = new Triangle2D[nb_points-2];
    nb_triangles = 0;
 
    int n = nb_points;
    if ( n < 3 ) return false;
 
    int *V = new int[n];
 
    /* we want a counter-clockwise polygon in V */
 
    if ( 0.0f < Area(nb_points, points) )
        for (int v=0; v<n; v++) V[v] = v;
    else
        for(int v=0; v<n; v++) V[v] = (n-1)-v;
 
    int nv = n;
 
    /*  remove nv-2 Vertices, creating 1 triangle every time */
    int count = 2*nv;   /* error detection */
 
    for(int m=0, v=nv-1; nv>2; )
    {
 
        /* if we loop, it is probably a non-simple polygon */
        if (0 >= (count--))
        {
            //** Triangulate: ERROR - probable bad polygon!
            //	delete[] triangles;
            printf( "Degenerate polygon\n" );
            return triangles;
        }
 
        /* three consecutive vertices in current polygon, <u,v,w> */
        int u = v  ; if (nv <= u) u = 0;     /* previous */
        v = u+1; if (nv <= v) v = 0;     /* new v    */
        int w = v+1; if (nv <= w) w = 0;     /* next     */
 
        if ( Snip(nb_points, points,u,v,w,nv,V) )
        {
            int a,b,c,s,t;
 
            /* true names of the vertices */
            a = V[u]; b = V[v]; c = V[w];
 
            /* output Triangle */
            /*   result.push_back( points[a] );
      result.push_back( points[b] );
      result.push_back( points[c] );*/
 
            triangles[nb_triangles].p1 = points[a];
            triangles[nb_triangles].p2 = points[b];
            triangles[nb_triangles].p3 = points[c];
            nb_triangles++;
 
            m++;
 
            /* remove v from remaining polygon */
            for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--;
 
            /* resest error detection counter */
            count = 2*nv;
        }
    }
 
    delete V;
 
    return triangles;
}
 
float Terrain::Area( int nb_points, Point2D *points )
{
 
    int n = nb_points;
 
    float A=0.0f;
 
    for(int p=n-1,q=0; q<n; p=q++)
    {
        A+= points[p].x*points[q].y - points[q].x*points[p].y;
    }
    return A*0.5f;
}
 
 
bool Terrain::Snip( int nb_points, Point2D *points,int u,int v,int w,int n,int *V )
{
    int p;
    float Ax, Ay, Bx, By, Cx, Cy, Px, Py;
 
    Ax = points[V[u]].x;
    Ay = points[V[u]].y;
 
    Bx = points[V[v]].x;
    By = points[V[v]].y;
 
    Cx = points[V[w]].x;
    Cy = points[V[w]].y;
 
    if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false;
 
    for (p=0;p<n;p++)
    {
        if( (p == u) || (p == v) || (p == w) ) continue;
        Px = points[V[p]].x;
        Py = points[V[p]].y;
        if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
    }
 
    return true;
}
 
bool Terrain::InsideTriangle(float Ax, float Ay,
                             float Bx, float By,
                             float Cx, float Cy,
                             float Px, float Py)
 
{
    float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
    float cCROSSap, bCROSScp, aCROSSbp;
 
    ax = Cx - Bx;  ay = Cy - By;
    bx = Ax - Cx;  by = Ay - Cy;
    cx = Bx - Ax;  cy = By - Ay;
    apx= Px - Ax;  apy= Py - Ay;
    bpx= Px - Bx;  bpy= Py - By;
    cpx= Px - Cx;  cpy= Py - Cy;
 
    aCROSSbp = ax*bpy - ay*bpx;
    cCROSSap = cx*apy - cy*apx;
    bCROSScp = bx*cpy - by*cpx;
 
    return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}

Cela marche sauf que cela se passe de cette façon : Le fichier contenant les points a plus d'un million de points, et je ne cherche à traçer que certains triangles se situant dans une zone spécifique. Jusqu'à la nickel, sauf que il se peut qu'il y ait des triangles dénégérés , c'est à dire qu'on ne dispose pas à tout les coups de tout les points d'un triangle.
Du coup, ce qu'il se passe, c'est que après la triangulation des triangles spécifiques, je m'aperçois que cela dessine non pas la zone désiré mais ce qu'il y a autour.

Du coup, je me suis dis que j'allais changer d'algol de triangulation mais je ne trouve pas ( ou bien je n'ai pas assez cherché ) d'algo facilement implémentables ( qui ne s'éloigne pas des masses de mes structures )

Auriez-vous des conseils, des choses à me proposer ?

PS : Voici en photo mon problème pour que cela soit plus clair :

[LittleWhite]

Bonjour,

Je dois dire que j'ai du mal à saisir. Vous souhaitez seulement trianguler une sous partie de votre surface d'eau ?
J'arrive pas à comprendre ce que l'on doit voir dans l'image ? Il y a une surface en fil de fer, et l'autre en bleu ? La partie bleue est la partie triangulée ?

[Astraya]

Bonjour,

Triangulation de delaunay!