1 // Created on: 1995-03-06
2 // Created by: Laurent PAINNOT
3 // Copyright (c) 1995-1999 Matra Datavision
4 // Copyright (c) 1999-2012 OPEN CASCADE SAS
6 // The content of this file is subject to the Open CASCADE Technology Public
7 // License Version 6.5 (the "License"). You may not use the content of this file
8 // except in compliance with the License. Please obtain a copy of the License
9 // at http://www.opencascade.org and read it completely before using this file.
11 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
12 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
14 // The Original Code and all software distributed under the License is
15 // distributed on an "AS IS" basis, without warranty of any kind, and the
16 // Initial Developer hereby disclaims all such warranties, including without
17 // limitation, any warranties of merchantability, fitness for a particular
18 // purpose or non-infringement. Please see the License for the specific terms
19 // and conditions governing the rights and limitations under the License.
23 #include <Poly_Connect.ixx>
24 #include <Poly_Triangle.hxx>
26 #include <Standard.hxx>
29 //=======================================================================
30 //function : Poly_Connect
32 //=======================================================================
33 // this structure records one of the edges starting from a node
35 //typedef struct polyedge {
37 polyedge* next; // the next edge in the list
38 Standard_Integer nd; // the second node of the edge
39 Standard_Integer nt[2]; // the two adjacent triangles
40 Standard_Integer nn[2]; // the two adjacent nodes
44 Poly_Connect::Poly_Connect(const Handle(Poly_Triangulation)& T) :
46 myTriangles(1,T->NbNodes()),
47 myAdjacents(1,6*T->NbTriangles())
51 Standard_Integer nbNodes = myTriangulation->NbNodes();
52 Standard_Integer nbTriangles = myTriangulation->NbTriangles();
54 // We first build an array of the list of edges connected to the nodes
58 // create an array to store the edges starting from the vertices
61 // the last node is not used because edges are stored at the lower node index
62 polyedge** edges = new polyedge*[nbNodes];
63 for (i = 0; i < nbNodes; i++) edges[i] = 0;
66 // loop on the triangles
67 Standard_Integer j,k,n[3],n1,n2;
68 const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
70 for (i = 1; i <= nbTriangles; i++) {
73 triangles(i).Get(n[0],n[1],n[2]);
75 // Update the myTriangles array
76 myTriangles(n[0]) = i;
77 myTriangles(n[1]) = i;
78 myTriangles(n[2]) = i;
80 // update the edge lists
81 for (j = 0; j < 3; j++) {
82 k = (j+1) % 3; // the following node of the edge
92 // edge from n1 to n2 with n1 < n2
93 // insert in the list of n1
95 polyedge* ced = edges[n1];
97 // the edge already exists
105 // create the edge if not found
107 ced->next = edges[n1];
111 ced->nn[0] = n[3-j-k]; // the third node
116 // just mark the adjacency if found
118 ced->nn[1] = n[3-j-k]; // the third node
124 // now complete the myAdjacents array
126 Standard_Integer index = 1;
127 for (i = 1; i <= nbTriangles; i++) {
130 triangles(i).Get(n[0],n[1],n[2]);
133 for (j = 0; j < 3; j++) {
134 k = (j+1) % 3; // the following node of the edge
144 // edge from n1 to n2 with n1 < n2
145 // find in the list of n1
147 polyedge* ced = edges[n1];
148 while (ced->nd != n2)
151 // Find the adjacent triangle
152 Standard_Integer l = 0;
153 if (ced->nt[0] == i) l = 1;
155 myAdjacents(index) = ced->nt[l];
156 myAdjacents(index+3) = ced->nn[l];
162 // destroy the edges array
163 for (i = 0; i < nbNodes; i++) {
164 polyedge* ced = edges[i];
166 polyedge* tmp = ced->next;
174 //=======================================================================
175 //function : Triangles
177 //=======================================================================
179 void Poly_Connect::Triangles(const Standard_Integer T,
180 Standard_Integer& t1,
181 Standard_Integer& t2,
182 Standard_Integer& t3) const
184 Standard_Integer index = 6*(T-1);
185 t1 = myAdjacents(index+1);
186 t2 = myAdjacents(index+2);
187 t3 = myAdjacents(index+3);
190 //=======================================================================
193 //=======================================================================
195 void Poly_Connect::Nodes(const Standard_Integer T,
196 Standard_Integer& n1,
197 Standard_Integer& n2,
198 Standard_Integer& n3) const
200 Standard_Integer index = 6*(T-1);
201 n1 = myAdjacents(index+4);
202 n2 = myAdjacents(index+5);
203 n3 = myAdjacents(index+6);
207 //=======================================================================
208 //function : Initialize
210 //=======================================================================
212 void Poly_Connect::Initialize(const Standard_Integer N)
215 myfirst = Triangle(N);
217 mysense = Standard_True;
218 mymore = (myfirst != 0);
221 Standard_Integer i, no[3];
222 const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
223 triangles(myfirst).Get(no[0], no[1], no[2]);
224 for (i = 0; i < 3; i++)
225 if (no[i] == mynode) break;
226 myothernode = no[(i+2)%3];
230 //=======================================================================
233 //=======================================================================
235 void Poly_Connect::Next()
237 Standard_Integer i, j;
238 Standard_Integer n[3];
239 Standard_Integer t[3];
240 const Poly_Array1OfTriangle& triangles = myTriangulation->Triangles();
241 Triangles(mytr, t[0], t[1], t[2]);
243 for (i = 0; i < 3; i++) {
245 triangles(t[i]).Get(n[0], n[1], n[2]);
246 for (j = 0; j < 3; j++) {
247 if ((n[j] == mynode) && (n[(j+1)%3] == myothernode)) {
249 myothernode = n[(j+2)%3];
250 mymore = (mytr != myfirst);
256 // sinon, depart vers la gauche.
257 triangles(myfirst).Get(n[0], n[1], n[2]);
258 for (i = 0; i < 3; i++)
259 if (n[i] == mynode) break;
260 myothernode = n[(i+1)%3];
261 mysense = Standard_False;
263 Triangles(mytr, t[0], t[1], t[2]);
266 for (i = 0; i < 3; i++) {
268 triangles(t[i]).Get(n[0], n[1], n[2]);
269 for (j = 0; j < 3; j++) {
270 if ((n[j] == mynode) && (n[(j+2)%3] == myothernode)) {
272 myothernode = n[(j+1)%3];
273 mymore = Standard_True;
280 mymore = Standard_False;
284 //=======================================================================
287 //=======================================================================
289 Standard_Integer Poly_Connect::Value() const