projects / occt.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
0022048: Visualization, AIS_InteractiveContext - single object selection should alway...
[occt.git] / src / MAT / MAT_Graph.cxx
CommitLineData
b311480e 1// Created on: 1993-05-06
2// Created by: Yves FRICAUD
3// Copyright (c) 1993-1999 Matra Datavision
973c2be1 4// Copyright (c) 1999-2014 OPEN CASCADE SAS
b311480e 5//
973c2be1 6// This file is part of Open CASCADE Technology software library.
b311480e 7//
d5f74e42 8// This library is free software; you can redistribute it and/or modify it under
9// the terms of the GNU Lesser General Public License version 2.1 as published
973c2be1 10// by the Free Software Foundation, with special exception defined in the file
11// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12// distribution for complete text of the license and disclaimer of any warranty.
b311480e 13//
973c2be1 14// Alternatively, this file may be used under the terms of Open CASCADE
15// commercial license or contractual agreement.
7fd59977 16
42cf5bc1 17
18#include <MAT_Arc.hxx>
19#include <MAT_BasicElt.hxx>
20#include <MAT_Bisector.hxx>
21#include <MAT_DataMapIteratorOfDataMapOfIntegerBasicElt.hxx>
22#include <MAT_DataMapOfIntegerArc.hxx>
23#include <MAT_DataMapOfIntegerBasicElt.hxx>
24#include <MAT_Edge.hxx>
25#include <MAT_Graph.hxx>
26#include <MAT_ListOfBisector.hxx>
27#include <MAT_Node.hxx>
28#include <MAT_SequenceOfArc.hxx>
29#include <MAT_Zone.hxx>
30#include <Precision.hxx>
31#include <Standard_Type.hxx>
7fd59977 32
25e59720 33IMPLEMENT_STANDARD_RTTIEXT(MAT_Graph,Standard_Transient)
92efcf78 34
7fd59977 35//------------------
36// functions static.
37//-------------------
38 static Handle(MAT_Arc) MakeArc(const Handle(MAT_Bisector)& aBisector,
39 MAT_DataMapOfIntegerBasicElt& TheBasicElts,
40 MAT_DataMapOfIntegerArc& TheArcs,
41 Standard_Integer& IndTabArcs);
42
43// =====================================================================
44// Constructeur vide.
45// =====================================================================
46MAT_Graph::MAT_Graph() {}
47
48// =====================================================================
49// function : Perform
50// purpose : Creation du graphe contenant le resultat.
51// =====================================================================
52void MAT_Graph::Perform(const Standard_Boolean SemiInfinite,
53 const Handle(MAT_ListOfBisector)& TheRoots,
54 const Standard_Integer NbBasicElts,
55 const Standard_Integer NbArcs)
56{
57 Standard_Integer NbRoots;
58 Handle(MAT_Arc) FirstArc;
59 Handle(MAT_Arc) CurrentArc;
60 Handle(MAT_Node) Extremite;
61 Standard_Integer IndTabArcs = 1;
62 Standard_Integer IndTabNodes;
63 Standard_Integer i;
64 Standard_Real DistExt;
65 Standard_Integer IndExt;
66 Handle(MAT_Arc) PreviousArc = CurrentArc;
67
68 //------------------------
69 // Construction du graphe.
70 //------------------------
71
72 if (SemiInfinite) {
73 NbRoots = TheRoots->Number();
74 numberOfInfiniteNodes = NbRoots;
75 }
76 else {
77 NbRoots = 1;
78 numberOfInfiniteNodes = 0;
79 }
80
81 numberOfArcs = NbArcs;
82 numberOfBasicElts = NbBasicElts;
83 numberOfNodes = NbRoots + NbArcs;
84 IndTabNodes = numberOfNodes;
85
86 //---------------------------
87 //... Creation des BasicElts.
88 //---------------------------
89 for (i = 1; i <= NbBasicElts; i++) {
90 theBasicElts.Bind(i,new MAT_BasicElt(i));
91 theBasicElts(i)->SetGeomIndex(i);
92 }
93
94 //--------------------------------------------------------------------
95 // ... Creation des ARCS et des NODES.
96 // Construction des arbres d arcs a partir des <Bisector> racines.
97 //--------------------------------------------------------------------
98
99 if (SemiInfinite) {
100
101 // Plusieurs points d entree a l infini.
102 //--------------------------------------
103 TheRoots->First();
104
105 while (TheRoots->More()) {
106 CurrentArc = MakeArc(TheRoots->Current(),
107 theBasicElts,
108 theArcs,
109 IndTabArcs);
110 Extremite = new MAT_Node (0,CurrentArc,Precision::Infinite());
111 Extremite ->SetIndex (IndTabNodes);
112 CurrentArc->SetSecondNode(Extremite);
113 theNodes.Bind(IndTabNodes,Extremite);
114 TheRoots->Next();
115 IndTabNodes--;
116 }
117 }
118 else {
119 // -----------------------------------------------
120 // Un seul point d entree .
121 // Creation d un premier ARC et du NODE racine.
122 // -----------------------------------------------
123 NbRoots = 1;
124 TheRoots->First();
125 CurrentArc = MakeArc(TheRoots->Current(),
126 theBasicElts,
127 theArcs,
128 IndTabArcs);
129 DistExt = TheRoots->Current()->FirstEdge()->Distance();
130 IndExt = TheRoots->Current()->EndPoint();
131
132 Extremite = new MAT_Node(IndExt,CurrentArc,DistExt);
133 Extremite ->SetIndex (IndTabNodes);
134 CurrentArc->SetSecondNode(Extremite);
135 theNodes.Bind(IndTabNodes,Extremite);
136 IndTabNodes--;
137
138 // -----------------------------------------------------------
139 // ...Creation des ARCs issues de la racine.
140 // Codage des voisinages sur ces arcs et mise a jour de la
141 // sequence des arcs issue du Node racine.
142 // -----------------------------------------------------------
143 FirstArc = CurrentArc;
144 PreviousArc = FirstArc;
145 TheRoots->Next();
146
147 while (TheRoots->More()) {
148 CurrentArc = MakeArc(TheRoots->Current(),
149 theBasicElts,
150 theArcs,
151 IndTabArcs);
152 CurrentArc ->SetSecondNode(Extremite);
153 CurrentArc ->SetNeighbour (MAT_Left,Extremite ,PreviousArc);
154 PreviousArc->SetNeighbour (MAT_Right,Extremite,CurrentArc);
155
156 PreviousArc = CurrentArc;
157 TheRoots->Next();
158 }
159 FirstArc ->SetNeighbour (MAT_Left ,Extremite,CurrentArc);
160 CurrentArc->SetNeighbour (MAT_Right,Extremite,FirstArc);
161 }
162
163 // ----------------------------------------------------
164 // Les sequence des Arcs des Nodes racines sont a jour.
165 // Mise a jour des sequences des autres Nodes.
166 // ----------------------------------------------------
167 UpDateNodes(IndTabNodes);
168}
169
170//=============================================================================
171//function : Arc
172//Purpose :
173//=============================================================================
174Handle(MAT_Arc) MAT_Graph::Arc(const Standard_Integer Index) const
175{
176 return theArcs(Index);
177}
178
179//=============================================================================
180//function : BasicElt
181//Purpose :
182//=============================================================================
183Handle(MAT_BasicElt) MAT_Graph::BasicElt(const Standard_Integer Index) const
184{
185 return theBasicElts(Index);
186}
187
188//=============================================================================
189//function : Node
190//Purpose :
191//=============================================================================
192Handle(MAT_Node) MAT_Graph::Node(const Standard_Integer Index) const
193{
194 return theNodes(Index);
195}
196
197//=============================================================================
198//function : NumberOfArcs
199//Purpose :
200//=============================================================================
201Standard_Integer MAT_Graph::NumberOfArcs() const
202{
203 return numberOfArcs;
204}
205
206//=============================================================================
207//function : NumberOfNodes
208//Purpose :
209//=============================================================================
210Standard_Integer MAT_Graph::NumberOfNodes() const
211{
212 return numberOfNodes;
213}
214
215//=============================================================================
216//function : NumberOfInfiniteNodes
217//Purpose :
218//=============================================================================
219Standard_Integer MAT_Graph::NumberOfInfiniteNodes() const
220{
221 return numberOfInfiniteNodes;
222}
223
224//=============================================================================
225//function : NumberOfBasicElts
226//Purpose :
227//=============================================================================
228Standard_Integer MAT_Graph::NumberOfBasicElts() const
229{
230 return numberOfBasicElts;
231}
232
233//=============================================================================
234//function : FusionOfBasicElts
235//Purpose :
236//=============================================================================
237void MAT_Graph::FusionOfBasicElts(const Standard_Integer IndexElt1,
238 const Standard_Integer IndexElt2,
239 Standard_Boolean& MergeArc1,
240 Standard_Integer& IGeomArc1,
241 Standard_Integer& IGeomArc2,
242 Standard_Boolean& MergeArc2,
243 Standard_Integer& IGeomArc3,
244 Standard_Integer& IGeomArc4)
245{
246 Handle(MAT_BasicElt) Elt1 = theBasicElts(IndexElt1);
247 Handle(MAT_BasicElt) Elt2 = theBasicElts(IndexElt2);
248
249 if (Elt1 == Elt2) return;
250
251 Standard_Integer i;
252 Handle(MAT_Zone) Zone2 = new MAT_Zone(Elt2);
253
254 //--------------------------------------------------------------------
255 // Les arcs de la zone de Elt2 ne separent plus Elt2 et qq chose mais
256 // Elt1 et qq chose.
257 //--------------------------------------------------------------------
258 for (i = 1; i <= Zone2->NumberOfArcs(); i++) {
259 if (Zone2->ArcOnFrontier(i)->FirstElement() == Elt2) {
260 theArcs(Zone2->ArcOnFrontier(i)->Index())->SetFirstElement(Elt1);
261 }
262 else {
263 theArcs(Zone2->ArcOnFrontier(i)->Index())->SetSecondElement(Elt1);
264 }
265 }
266
267 //-------------------------------------------------------------------
268 // le EndArc de Elt1 et le StartArc de Elt2 peuvent separes les memes
269 // elements de base => Fusion des deux arcs et mise a jour des noeuds.
270 //-------------------------------------------------------------------
271 Handle(MAT_Arc) EA1 = Elt1->EndArc();
272 Handle(MAT_Arc) SA2 = Elt2->StartArc();
273
274 Handle(MAT_BasicElt) E1 = EA1->FirstElement();
275 Handle(MAT_BasicElt) E2 = EA1->SecondElement();
276 Handle(MAT_BasicElt) E3 = SA2->FirstElement();
277 Handle(MAT_BasicElt) E4 = SA2->SecondElement();
278 MergeArc1 = Standard_False;
279
280 if ( (E1 == E3 || E1 == E4) && (E2 == E3 || E2 == E4)) {
281 FusionOfArcs(theArcs(EA1->Index()),theArcs(SA2->Index()));
282 MergeArc1 = Standard_True;
283 IGeomArc1 = EA1->GeomIndex();
284 IGeomArc2 = SA2->GeomIndex();
285 }
286
287 //-------------------------------------------------
288 // La fin de Elt1 devient la fin de Elt2.
289 //-------------------------------------------------
290 Elt1->SetEndArc(Elt2->EndArc());
291
292 //-------------------------------------------------------------------
293 // le EndArc de Elt1 et le StartArc de Elt1 peuvent separer les memes
294 // elements de base.
295 // si les noeuds des arcs ne sont pas sur le contour
296 // => fusion des arcs.(contour ferme compose d un seul BasicElt)
297 // sinon rien (contour ferme compose de deux BasicElts)
298 //-------------------------------------------------------------------
299 Handle(MAT_Arc) SA1 = Elt1->StartArc();
300 EA1 = Elt1->EndArc();
301
302 if ( EA1 != SA1 ) {
51740958 303 E1 = EA1->FirstElement ();
304 E2 = EA1->SecondElement();
305 E3 = SA1->FirstElement ();
306 E4 = SA1->SecondElement();
7fd59977 307
308 Standard_Boolean OnFig = (EA1->FirstNode() ->OnBasicElt() ||
309 EA1->SecondNode()->OnBasicElt() ||
310 SA1->FirstNode() ->OnBasicElt() ||
311 SA1->SecondNode()->OnBasicElt() );
312
313 MergeArc2 = Standard_False;
314
315 if ((E1 == E3 || E1 == E4) && (E2 == E3 || E2 == E4) && !OnFig) {
316 FusionOfArcs(theArcs(EA1->Index()),theArcs(SA1->Index()));
317 MergeArc2 = Standard_True;
318 IGeomArc3 = EA1->GeomIndex();
319 IGeomArc4 = SA1->GeomIndex();
320 }
321 }
322
323 //----------------------------------------------------
324 // un element de base a ete elimine.
325 //----------------------------------------------------
326 theBasicElts.UnBind(Elt2->Index());
327 numberOfBasicElts--;
328}
329
330//=============================================================================
331// function : FusionOfArcs
332// purpose : Fusion de deux arcs separant les memes elements.
333// l <Arc1> ira du Second noeud de <Arc2> au second Noeud de <Arc1>.
334//=============================================================================
335void MAT_Graph::FusionOfArcs(const Handle(MAT_Arc)& Arc1,
336 const Handle(MAT_Arc)& Arc2)
337{
338
339 Handle(MAT_Node) OldNode1 = Arc1->FirstNode();
340 Handle(MAT_Node) OldNode2 = Arc2->FirstNode();
341
342 Arc1->SetFirstNode(Arc2->SecondNode());
343
344 //--------------------------------------------------------------------
345 // Mise a jour des voisinages autour du nouveau premier noeud de Arc1.
346 //--------------------------------------------------------------------
347 if (!Arc2->SecondNode()->Infinite()) {
348 Handle(MAT_Arc) LNeighbour = Arc2->Neighbour(Arc2->SecondNode(),MAT_Left);
349 Handle(MAT_Arc) RNeighbour = Arc2->Neighbour(Arc2->SecondNode(),MAT_Right);
350
351 Arc1->SetFirstArc(MAT_Left,LNeighbour);
352 Arc1->SetFirstArc(MAT_Right,RNeighbour);
353 theArcs(LNeighbour->Index())->SetNeighbour(MAT_Right,
354 Arc2->SecondNode(),
355 Arc1);
356 theArcs(RNeighbour->Index())->SetNeighbour(MAT_Left,
357 Arc2->SecondNode(),
358 Arc1);
359 }
360 else {
361 Handle(MAT_Arc) EmptyArc;
362 Arc1->SetFirstArc(MAT_Left ,EmptyArc);
363 Arc1->SetFirstArc(MAT_Right,EmptyArc);
364 }
365
366 //-------------------------------------------------------------------
367 // Mise a jour du premier noeud Arc1.
368 //-----------------------------------------------------------------
369 Arc1->FirstNode()->SetLinkedArc(Arc1);
370
371 //------------------------------------
372 // Elimination de Arc2 et des OldNode
373 //------------------------------------
374 if (theNodes.IsBound(OldNode1->Index())) {
375 theNodes.UnBind(OldNode1->Index());
376 numberOfNodes--;
377 }
378 if (theNodes.IsBound(OldNode2->Index())) {
379 theNodes.UnBind(OldNode2->Index());
380 numberOfNodes--;
381 }
382
383 // Note: the Arc2 is actually a reference to a handle contained in theArcs map;
384 // it is necessary to create copy of that handle and use only it to access
385 // that object, since the handle contained in the map is destroyed by UnBind()
386 Handle(MAT_Arc) anArc2 = Arc2;
387 theArcs .UnBind(Arc2->Index());
388 numberOfArcs--;
389
390 for (Standard_Integer i = 1; i <= 2; i++){
391 Handle(MAT_BasicElt) BE;
392 if (i == 1)
393 BE = theBasicElts(anArc2->FirstElement ()->Index());
394 else
395 BE = theBasicElts(anArc2->SecondElement ()->Index());
396
397 if (BE->StartArc() == anArc2) { BE->SetStartArc(Arc1);}
398 if (BE->EndArc () == anArc2) { BE->SetEndArc (Arc1);}
399 }
400}
401
402//=============================================================================
403// function : CompactArcs
404// purpose : Decalage des Arcs pour boucher les trous.
405//=============================================================================
406void MAT_Graph::CompactArcs()
407{
408 Standard_Integer IFind = 0;
409 Standard_Integer i = 1;
410 Standard_Boolean YaDecalage = Standard_False;
411
412 while (IFind < numberOfArcs) {
413 if (!theArcs.IsBound(i)) {
414 YaDecalage = Standard_True;
415 }
416 else {
417 IFind++;
418 if (YaDecalage) {
419 theArcs(i)->SetIndex(IFind);
420 theArcs.Bind(IFind,theArcs(i));
421 theArcs.UnBind(i);
422 }
423 }
424 i++;
425 }
426}
427
428//=============================================================================
429// function : CompactNodes
430// purpose : Decalage des Nodes pour boucher les trous.
431//=============================================================================
432void MAT_Graph::CompactNodes()
433{
434 Standard_Integer IFind = 0;
435 Standard_Integer i = 1;
436 Standard_Boolean YaDecalage = Standard_False;
437
438 while (IFind < numberOfNodes) {
439 if (!theNodes.IsBound(i)) {
440 YaDecalage = Standard_True;
441 }
442 else {
443 IFind++;
444 if (YaDecalage) {
445 theNodes(i)->SetIndex(IFind);
446 theNodes.Bind(IFind,theNodes(i));
447 theNodes.UnBind(i);
448 }
449 }
450 i++;
451 }
452}
453
454//=============================================================================
455// function : ChangeBasicElts
456// purpose :
457//=============================================================================
458void MAT_Graph::ChangeBasicElts(const MAT_DataMapOfIntegerBasicElt& NewMap)
459{
460 theBasicElts = NewMap;
461 MAT_DataMapIteratorOfDataMapOfIntegerBasicElt Ite;
462 for (Ite.Initialize(theBasicElts); Ite.More(); Ite.Next()) {
463 Ite.Value()->SetIndex(Ite.Key());
464 }
465}
466
467//=============================================================================
468//function : ChangeBasicElt
469//Purpose :
470//=============================================================================
471Handle(MAT_BasicElt) MAT_Graph::ChangeBasicElt(const Standard_Integer Index)
472{
473 return theBasicElts(Index);
474}
475
476//=============================================================================
477// function : UpDateNodes
478// purpose : Mise a jour des sequence d'ARC de chaque FirstNode de chaque arc.
479// et stockage de chaque noeud dans la table des noeuds.
480// Les noeuds racines sont traites dans PERFORM.
481//=============================================================================
482void MAT_Graph::UpDateNodes (Standard_Integer& IndTabNodes)
483{
484 Standard_Integer i;
485 Handle(MAT_Node) Bout;
486 Handle(MAT_Arc) CurrentArc;
487
488 for (i = 1; i <= numberOfArcs; i++) {
489 Bout = theArcs(i)->FirstNode();
490 theNodes.Bind(IndTabNodes,Bout);
491 Bout->SetIndex(IndTabNodes);
492 IndTabNodes--;
493 Bout->SetLinkedArc(theArcs(i));
494 }
495}
496
497
498//=============================================================================
499// function : MakeArc
500// purpose : Creation des <ARCS> en parcourant l'arbre issue de <aBisector>.
501//=============================================================================
502static Handle(MAT_Arc) MakeArc(const Handle(MAT_Bisector)& aBisector,
503 MAT_DataMapOfIntegerBasicElt& TheBasicElts,
504 MAT_DataMapOfIntegerArc& TheArcs,
505 Standard_Integer& IndTabArcs)
506{
507 Handle(MAT_Arc) CurrentArc;
508 Handle(MAT_Arc) PrevArc;
509 Handle(MAT_Arc) NextArc;
510 Handle(MAT_Node) Extremite;
511 Handle(MAT_ListOfBisector) BisectorList;
512 Standard_Real DistExt;
513
0797d9d3 514#ifdef OCCT_DEBUG_Graph
7fd59977 515 cout<<"Construction Arc : Index"<<aBisector->IndexNumber()<<endl;
516 cout<<"Construction Arc : Bisector"<<aBisector->BisectorNumber()<<endl;
517#endif
518
519 CurrentArc = new MAT_Arc(IndTabArcs,
520 aBisector->BisectorNumber(),
521 TheBasicElts(aBisector->FirstEdge()->EdgeNumber()),
522 TheBasicElts(aBisector->SecondEdge()->EdgeNumber())
523 );
524 DistExt = aBisector->DistIssuePoint();
525 if (DistExt == Precision::Infinite()) {
526 DistExt = 1.0;
0797d9d3 527#ifdef OCCT_DEBUG_Graph
7fd59977 528 cout<<"PB:RECUPERATION DISTANCE SUR ISSUEPOINT."<<endl;
529#endif
530 }
531
532 Extremite = new MAT_Node(aBisector->IssuePoint(),CurrentArc,DistExt);
533
534 CurrentArc->SetFirstNode(Extremite);
535 BisectorList = aBisector->List();
536 BisectorList->First();
537
538 if (!BisectorList->More()) {
539 // -------------------
540 // Arc sur le contour.
541 // -------------------
542 TheBasicElts(aBisector->SecondEdge()->EdgeNumber())
543 ->SetStartArc(CurrentArc);
544 TheBasicElts(aBisector->FirstEdge()->EdgeNumber())
545 ->SetEndArc(CurrentArc);
546 }
547 else {
548 PrevArc = CurrentArc;
549
550 while (BisectorList->More()) {
551 NextArc = MakeArc(BisectorList->Current(),
552 TheBasicElts,
553 TheArcs,
554 IndTabArcs);
555 NextArc->SetSecondNode(Extremite);
556 NextArc->SetNeighbour (MAT_Left ,Extremite,PrevArc);
557 PrevArc->SetNeighbour (MAT_Right,Extremite,NextArc);
558 PrevArc = NextArc;
559 BisectorList->Next();
560 }
561 CurrentArc->SetNeighbour(MAT_Left ,Extremite,NextArc);
562 NextArc ->SetNeighbour(MAT_Right,Extremite,CurrentArc);
563 }
564
0797d9d3 565#ifdef OCCT_DEBUG_Graph
7fd59977 566 cout<<"IndTabArcs = "<<IndTabArcs<<endl;
567 cout<<"ArcIndex = "<<CurrentArc->ArcIndex()<<endl;
568#endif
569 CurrentArc->SetIndex(IndTabArcs);
570 TheArcs.Bind(IndTabArcs,CurrentArc);
571 IndTabArcs = IndTabArcs + 1;
572
573 return CurrentArc;
574}
575
576
577
578
579
Open CASCADE Technology repository