0022815: Missing delete operator for placement new
[occt.git] / src / Poly / Poly_Connect.cxx
1 // File:        Poly_Connect.cxx
2 // Created:     Mon Mar  6 16:30:09 1995
3 // Author:      Laurent PAINNOT
4 //              <lpa@metrox>
5
6
7 #include <Poly_Connect.ixx>
8 #include <Poly_Triangle.hxx>
9
10 #include <Standard.hxx>
11
12
13 //=======================================================================
14 //function : Poly_Connect
15 //purpose  : 
16 //=======================================================================
17 // this structure records one of the edges starting from a node
18
19 //typedef struct polyedge {
20 struct polyedge {
21     polyedge* next;             // the next edge in the list
22     Standard_Integer nd;    // the second node of the edge
23     Standard_Integer nt[2]; // the two adjacent triangles
24     Standard_Integer nn[2]; // the two adjacent nodes
25     DEFINE_STANDARD_ALLOC
26   };
27
28 Poly_Connect::Poly_Connect(const Handle(Poly_Triangulation)& T) :
29     myTriangulation(T),
30     myTriangles(1,T->NbNodes()),
31     myAdjacents(1,6*T->NbTriangles())
32 {
33   myTriangles.Init(0);
34   myAdjacents.Init(0);
35   Standard_Integer nbNodes     = myTriangulation->NbNodes();
36   Standard_Integer nbTriangles = myTriangulation->NbTriangles();
37
38   // We first build an array of the list of edges connected to the nodes
39  
40
41   
42   // create an array to store the edges starting from the vertices
43
44   Standard_Integer i;
45   // the last node is not used because edges are stored at the lower node index
46   polyedge** edges = new polyedge*[nbNodes];
47   for (i = 0; i < nbNodes; i++) edges[i] = 0;
48
49
50   // loop on the triangles
51   Standard_Integer j,k,n[3],n1,n2;
52   const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
53
54   for (i = 1; i <= nbTriangles; i++) {
55
56     // get the nodes
57     triangles(i).Get(n[0],n[1],n[2]);
58
59     // Update the myTriangles array
60     myTriangles(n[0]) = i;
61     myTriangles(n[1]) = i;
62     myTriangles(n[2]) = i;
63
64     // update the edge lists
65     for (j = 0; j < 3; j++) {
66       k = (j+1) % 3;  // the following node of the edge
67       if (n[j] <= n[k]) {
68         n1 = n[j];
69         n2 = n[k];
70       }
71       else {
72         n1 = n[k];
73         n2 = n[j];
74       }
75
76       // edge from n1 to n2 with n1 < n2
77       // insert in the list of n1
78
79       polyedge* ced = edges[n1];
80       while (ced != 0) {
81         // the edge already exists
82         if (ced->nd == n2)
83           break;
84         else
85           ced = ced->next;
86       }
87
88       if (ced == 0) {
89         // create the edge if not found
90         ced = new polyedge;
91         ced->next = edges[n1];
92         edges[n1] = ced;
93         ced->nd = n2;
94         ced->nt[0] = i;
95         ced->nn[0] = n[3-j-k];  // the third node
96         ced->nt[1] = 0;
97         ced->nn[1] = 0;
98       }
99       else {
100         // just mark the adjacency if found
101         ced->nt[1] = i;
102         ced->nn[1] = n[3-j-k];  // the third node
103       }
104     }
105   }
106
107
108   // now complete the myAdjacents array
109   
110   Standard_Integer index = 1;
111   for (i = 1; i <= nbTriangles; i++) {
112     
113     // get the nodes
114     triangles(i).Get(n[0],n[1],n[2]);
115
116     // fore each edge
117     for (j = 0; j < 3; j++) {
118       k = (j+1) % 3;  // the following node of the edge
119       if (n[j] <= n[k]) {
120         n1 = n[j];
121         n2 = n[k];
122       }
123       else {
124         n1 = n[k];
125         n2 = n[j];
126       }
127
128       // edge from n1 to n2 with n1 < n2
129       // find in the list of n1
130
131       polyedge* ced = edges[n1];
132       while (ced->nd != n2)
133         ced = ced->next;
134
135       // Find the adjacent triangle
136       Standard_Integer l = 0;
137       if (ced->nt[0] == i) l = 1;
138       
139       myAdjacents(index)   = ced->nt[l];
140       myAdjacents(index+3) = ced->nn[l];
141       index++;
142     }
143     index += 3;
144   }
145
146   // destroy the edges array
147   for (i = 0; i < nbNodes; i++) {
148     polyedge* ced = edges[i];
149     while (ced != 0) {
150       polyedge* tmp = ced->next;
151       delete ced;
152       ced = tmp;
153     }
154   }
155   delete [] edges;
156 }
157
158 //=======================================================================
159 //function : Triangles
160 //purpose  : 
161 //=======================================================================
162
163 void Poly_Connect::Triangles(const Standard_Integer T, 
164                              Standard_Integer& t1, 
165                              Standard_Integer& t2, 
166                              Standard_Integer& t3) const 
167 {
168   Standard_Integer index = 6*(T-1);
169   t1 = myAdjacents(index+1);
170   t2 = myAdjacents(index+2);
171   t3 = myAdjacents(index+3);
172 }
173
174 //=======================================================================
175 //function : Nodes
176 //purpose  : 
177 //=======================================================================
178
179 void Poly_Connect::Nodes(const Standard_Integer T, 
180                          Standard_Integer& n1, 
181                          Standard_Integer& n2, 
182                          Standard_Integer& n3) const 
183 {
184   Standard_Integer index = 6*(T-1);
185   n1 = myAdjacents(index+4);
186   n2 = myAdjacents(index+5);
187   n3 = myAdjacents(index+6);
188 }
189
190
191 //=======================================================================
192 //function : Initialize
193 //purpose  : 
194 //=======================================================================
195
196 void Poly_Connect::Initialize(const Standard_Integer N)
197 {
198   mynode = N;
199   myfirst = Triangle(N);
200   mytr = myfirst;
201   mysense = Standard_True;
202   mymore = (myfirst != 0);
203   if (mymore)
204   {
205     Standard_Integer i, no[3];
206     const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
207     triangles(myfirst).Get(no[0], no[1], no[2]);
208     for (i = 0; i < 3; i++)
209       if (no[i] == mynode) break;
210     myothernode = no[(i+2)%3];
211   }
212 }
213
214 //=======================================================================
215 //function : Next
216 //purpose  : 
217 //=======================================================================
218
219 void Poly_Connect::Next()
220 {
221   Standard_Integer i, j;
222   Standard_Integer n[3];
223   Standard_Integer t[3];
224   const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
225   Triangles(mytr, t[0], t[1], t[2]);
226   if (mysense) {
227     for (i = 0; i < 3; i++) {
228       if (t[i] != 0) {
229         triangles(t[i]).Get(n[0], n[1], n[2]);
230         for (j = 0; j < 3; j++) {
231           if ((n[j] == mynode) && (n[(j+1)%3] == myothernode)) {
232             mytr = t[i];
233             myothernode = n[(j+2)%3];
234             mymore = (mytr != myfirst);
235             return;
236           }
237         }
238       }
239     }
240     // sinon, depart vers la gauche.
241     triangles(myfirst).Get(n[0], n[1], n[2]);
242     for (i = 0; i < 3; i++)
243       if (n[i] == mynode) break;
244     myothernode = n[(i+1)%3];
245     mysense = Standard_False;
246     mytr = myfirst;
247     Triangles(mytr, t[0], t[1], t[2]);
248   }
249   if (!mysense) {
250     for (i = 0; i < 3; i++) {
251       if (t[i] != 0) {
252         triangles(t[i]).Get(n[0], n[1], n[2]);
253         for (j = 0; j < 3; j++) {
254           if ((n[j] == mynode) && (n[(j+2)%3] == myothernode)) {
255             mytr = t[i];
256             myothernode = n[(j+1)%3];
257             mymore = Standard_True;
258             return;
259           }
260         }
261       }
262     }
263   }
264   mymore = Standard_False;
265 }
266
267
268 //=======================================================================
269 //function : Value
270 //purpose  : 
271 //=======================================================================
272
273 Standard_Integer Poly_Connect::Value() const
274 {
275   return mytr;
276 }