00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "g-map-generic.hh"
00026 #include <iostream>
00027 #include <sstream>
00028 #include <cstdlib>
00029 using namespace std;
00030 using namespace GMap3d;
00031
00032 bool CGMapGeneric::belongToSameOrientedOrbit(CDart* ADart1, CDart* ADart2,
00033 TOrbit AOrbit)
00034 {
00035 int mark = getNewMark();
00036
00037 halfMarkOrbit(ADart1, AOrbit, mark);
00038 bool same = isMarked(ADart2, mark);
00039 unmarkOrbit(ADart1, AOrbit, mark);
00040
00041 freeMark(mark);
00042
00043 return same;
00044 }
00045
00046 bool CGMapGeneric::isOrientable(CDart * ADart, TOrbit AOrbit)
00047 {
00048 assert(ADart!=NULL);
00049 assert(AOrbit>=ORBIT_SELF && AOrbit<=ORBIT_CC);
00050
00051 if (AOrbit!=ORBIT_VERTEX && AOrbit!=ORBIT_VOLUME && AOrbit!=ORBIT_CC)
00052 return true;
00053
00054 bool orientable = true;
00055
00056 bool usedDim[4];
00057 int selected = getNewMark();
00058
00059 for (int dim=0; dim<=3; ++dim)
00060 usedDim[dim] = AND_ORBIT(AOrbit, ORBIT_DIM[dim]) != ORBIT_SELF;
00061
00062 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00063
00064 setMark(**cov, selected);
00065
00066 for (; cov->cont() && orientable; ++(*cov))
00067 if (isMarked(**cov, selected))
00068 {
00069 for (int dim=0; dim<=3; ++dim)
00070 if (usedDim[dim] && !isFree(**cov, dim) &&
00071 isMarked(alpha(**cov, dim), selected))
00072 orientable = false;
00073 }
00074 else
00075 {
00076 for (int dim=0; dim<=3; ++dim)
00077 if (usedDim[dim] && !isFree(**cov, dim))
00078 setMark(alpha(**cov, dim), selected);
00079 }
00080
00081 delete cov;
00082
00083 unmarkOrbit(ADart, AOrbit, selected);
00084 freeMark(selected);
00085
00086 return orientable;
00087 }
00088
00089 void CGMapGeneric::countBorders(int ,
00090 int * ANb0, int * ANb1, int * ANb2, int * ANb3)
00091 {
00092 int * count[4] = { ANb0, ANb1, ANb2, ANb3 };
00093 int dim[4];
00094 int borderMark[4];
00095 int nbAsked = 0;
00096 int i;
00097
00098
00099 for (i=0; i<4; ++i)
00100 if (count[i] != NULL)
00101 {
00102 count[nbAsked] = count[i];
00103 * count[nbAsked] = 0;
00104 dim[nbAsked] = i;
00105 borderMark[nbAsked] = getNewMark();
00106 ++nbAsked;
00107 }
00108
00109 CDynamicCoverageAll it(this);
00110
00111
00112 for (; it.cont(); ++it)
00113 for (i=0; i<nbAsked; ++i)
00114 if (isFree(*it, dim[i]) && !isMarked(*it, borderMark[i]))
00115 {
00116 ++ * count[i];
00117 markOrbit(*it, ORBIT_BORDER[dim[i]], borderMark[i]);
00118 }
00119
00120
00121 for (it.reinit(); it.cont(); ++it)
00122 for (i=0; i<nbAsked; ++i)
00123 if (isMarked(*it, borderMark[i]))
00124 unmarkOrbit(*it, ORBIT_BORDER[dim[i]], borderMark[i]);
00125
00126
00127 for (i=0; i<nbAsked; ++i)
00128 freeMark(borderMark[i]);
00129 }
00130
00131 void CGMapGeneric::countBorders(CDart * ADart, TOrbit AOrbit,
00132 int * ANb0, int * ANb1, int * ANb2, int * ANb3)
00133 {
00134 assert(ADart != NULL);
00135
00136 int * count[4] = { ANb0, ANb1, ANb2, ANb3 };
00137 int dim[4];
00138 int borderMark[4];
00139 int nbAsked = 0;
00140 int i;
00141
00142
00143 for (i=0; i<4; ++i)
00144 if (count[i] != NULL)
00145 {
00146 count[nbAsked] = count[i];
00147 * count[nbAsked] = 0;
00148 dim[nbAsked] = i;
00149 borderMark[nbAsked] = getNewMark();
00150 ++nbAsked;
00151 }
00152
00153 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00154
00155
00156 for (; cov->cont(); ++(*cov))
00157 for (i=0; i<nbAsked; ++i)
00158 if (isFree(**cov, dim[i]) && !isMarked(**cov, borderMark[i]))
00159 {
00160 ++ * count[i];
00161 markOrbit(**cov, ORBIT_BORDER[dim[i]], borderMark[i]);
00162 }
00163
00164
00165 for (cov->reinit(); cov->cont(); ++(*cov))
00166 for (i=0; i<nbAsked; ++i)
00167 if (isMarked(**cov, borderMark[i]))
00168 unmarkOrbit(**cov, ORBIT_BORDER[dim[i]], borderMark[i]);
00169
00170
00171 delete cov;
00172
00173 for (i=0; i<nbAsked; ++i)
00174 freeMark(borderMark[i]);
00175 }
00176
00177 void CGMapGeneric::countCells(int ,
00178 int * ANb0, int * ANb1, int * ANb2,
00179 int * ANb3, int * ANb4, int * ANbDarts)
00180 {
00181 int * count[5] = { ANb0, ANb1, ANb2, ANb3, ANb4 };
00182 int dim[5];
00183 int cellMark[5];
00184 int nbAsked = 0;
00185 int nbDarts = 0;
00186 int i;
00187
00188
00189 for (i=0; i<5; ++i)
00190 if (count[i] != NULL)
00191 {
00192 count[nbAsked] = count[i];
00193 * count[nbAsked] = 0;
00194 dim[nbAsked] = i;
00195 cellMark[nbAsked] = getNewMark();
00196 ++nbAsked;
00197 }
00198
00199
00200 CDynamicCoverageAll it(this);
00201 for (; it.cont(); ++it, ++nbDarts)
00202 for (i=0; i<nbAsked; ++i)
00203 if (!isMarked(*it, cellMark[i]))
00204 {
00205 ++ * count[i];
00206 markOrbit(*it, ORBIT_CELL[dim[i]], cellMark[i]);
00207 }
00208
00209 if (ANbDarts != NULL)
00210 * ANbDarts = nbDarts;
00211
00212
00213 for (it.reinit(); it.cont(); ++it)
00214 for (i=0; i<nbAsked; ++i)
00215 if (isMarked(*it, cellMark[i]))
00216 unmarkOrbit(*it, ORBIT_CELL[dim[i]], cellMark[i]);
00217
00218
00219 for (i=0; i<nbAsked; ++i)
00220 freeMark(cellMark[i]);
00221 }
00222
00223 void CGMapGeneric::countCells(CDart * ADart, TOrbit AOrbit,
00224 int * ANb0, int * ANb1, int * ANb2,
00225 int * ANb3, int * ANb4, int * ANbDarts)
00226 {
00227 assert(ADart != NULL);
00228
00229 int * count[5] = { ANb0, ANb1, ANb2, ANb3, ANb4 };
00230 int dim[5];
00231 int cellMark[5];
00232 int nbAsked = 0;
00233 int nbDarts = 0;
00234 int i;
00235
00236
00237 for (i=0; i<5; ++i)
00238 if (count[i] != NULL)
00239 {
00240 count[nbAsked] = count[i];
00241 * count[nbAsked] = 0;
00242 dim[nbAsked] = i;
00243 cellMark[nbAsked] = getNewMark();
00244 ++nbAsked;
00245 }
00246
00247 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00248
00249
00250 for (; cov->cont(); ++(*cov), ++nbDarts)
00251 for (i=0; i<nbAsked; ++i)
00252 if (!isMarked(**cov, cellMark[i]))
00253 {
00254 ++ * count[i];
00255 markOrbit(**cov, ORBIT_CELL[dim[i]], cellMark[i]);
00256 }
00257
00258 if (ANbDarts != NULL)
00259 * ANbDarts = nbDarts;
00260
00261
00262 for (cov->reinit(); cov->cont(); ++(*cov))
00263 for (i=0; i<nbAsked; ++i)
00264 if (isMarked(**cov, cellMark[i]))
00265 unmarkOrbit(**cov, ORBIT_CELL[dim[i]], cellMark[i]);
00266
00267
00268 delete cov;
00269
00270 for (i=0; i<nbAsked; ++i)
00271 freeMark(cellMark[i]);
00272 }
00273
00274 void CGMapGeneric::getGlobalCharacteristics(int * ANbDarts,
00275 int * ANbVertices, int * ANbEdges,
00276 int * ANbFaces, int * ANbVolumes,
00277 int * ANbCC,
00278 int * ANb0Borders,
00279 int * ANb1Borders,
00280 int * ANb2Borders,
00281 int * ANb3Borders)
00282 {
00283 int mark = getNewMark();
00284
00285 negateMaskMark(mark);
00286
00287 countCells (mark, ANbVertices, ANbEdges, ANbFaces, ANbVolumes, ANbCC,
00288 ANbDarts);
00289
00290 countBorders(mark, ANb0Borders, ANb1Borders, ANb2Borders, ANb3Borders);
00291
00292 negateMaskMark(mark);
00293 freeMark(mark);
00294 }
00295
00296 void CGMapGeneric::getSurfaceCharacteristics(CDart * ADart,
00297 int * ANbDarts,
00298 int * ANbVertices,
00299 int * ANbEdges,
00300 int * ANbFaces,
00301 int * ANb0Borders,
00302 int * ANb1Borders,
00303 int * ANb2Borders,
00304 int * ANb2BordersWhenClosed,
00305 int * AEuler,
00306 int * AOrient,
00307 int * AGenus)
00308 {
00309 assert(ADart != NULL);
00310
00311 int nd ;
00312 int nc[3];
00313 int nb[3];
00314
00315 countCells (ADart, ORBIT_VOLUME, & nc[0], & nc[1], & nc[2], NULL, NULL, & nd);
00316 countBorders(ADart, ORBIT_VOLUME, & nb[0], & nb[1], & nb[2], NULL);
00317
00318 if (ANbDarts != NULL) * ANbDarts = nd;
00319 if (ANbVertices != NULL) * ANbVertices = nc[0];
00320 if (ANbEdges != NULL) * ANbEdges = nc[1];
00321 if (ANbFaces != NULL) * ANbFaces = nc[2];
00322 if (ANb0Borders != NULL) * ANb0Borders = nb[0];
00323 if (ANb1Borders != NULL) * ANb1Borders = nb[1];
00324 if (ANb2Borders != NULL) * ANb2Borders = nb[2];
00325
00326 bool needGenus = AGenus != NULL;
00327 bool needOrient = AOrient != NULL || needGenus;
00328 bool needEuler = AEuler != NULL || needOrient;
00329
00330 int euler = 0, orient = 0, genus = 0;
00331
00332 if (needEuler)
00333 {
00334
00335 int memoAlpha3 = getNewDirectInfo();
00336 int newDart = getNewMark();
00337
00338 CDynamicCoverageVolume vol(this, ADart);
00339
00340
00341 for (; vol.cont(); ++vol)
00342 {
00343 setDirectInfo(*vol, memoAlpha3, alpha3(*vol));
00344 (*vol)->setFree3();
00345 }
00346
00347
00348 negateMaskMark(newDart);
00349
00350 for (vol.reinit(); vol.cont(); ++vol)
00351 if (isFree0(*vol))
00352 stopUp(*vol, 0);
00353
00354 for (vol.reinit(); vol.cont(); ++vol)
00355 if (isFree1(*vol))
00356 stopUp(*vol, 1);
00357
00358 negateMaskMark(newDart);
00359
00360
00361 countCells (ADart, ORBIT_VOLUME,
00362 & nc[0], & nc[1], &nc[2], NULL, NULL, NULL);
00363 countBorders(ADart, ORBIT_VOLUME, & nb[0], & nb[1], & nb[2], NULL);
00364
00365 if (ANbVertices != NULL) * ANbVertices = nc[0];
00366 if (ANbEdges != NULL) * ANbEdges = nc[1];
00367 if (ANbFaces != NULL) * ANbFaces = nc[2];
00368 if (ANb0Borders != NULL) * ANb0Borders = nb[0];
00369 if (ANb1Borders != NULL) * ANb1Borders = nb[1];
00370 if (ANb2Borders != NULL) * ANb2Borders = nb[2];
00371
00372 if (ANb2BordersWhenClosed != NULL)
00373 * ANb2BordersWhenClosed = nb[2];
00374
00375
00376 euler = nc[0] - nc[1] + nc[2];
00377
00378
00379 for (vol.reinit(); vol.cont(); )
00380 {
00381 CDart * current = vol++;
00382
00383 if (isMarked(current, newDart))
00384 {
00385 alpha0(current)->setFree0();
00386 alpha1(current)->setFree1();
00387 alpha2(current)->setFree2();
00388
00389 delMapDart(current);
00390 }
00391 }
00392
00393
00394 for (vol.reinit(); vol.cont(); ++vol)
00395 (*vol)->setAlpha3(getDirectInfoAsDart(*vol, memoAlpha3));
00396
00397
00398 freeDirectInfo(memoAlpha3);
00399 freeMark(newDart);
00400
00401
00402 if (AEuler != NULL)
00403 * AEuler = euler;
00404 }
00405
00406 if (needOrient)
00407 {
00408 orient =
00409 isOrientable(ADart, ORBIT_VOLUME)
00410 ? 0
00411 : 2 - abs((euler + nb[2]) % 2);
00412
00413 if (AOrient != NULL)
00414 * AOrient = orient;
00415 }
00416
00417 if (needGenus)
00418 {
00419 assert((euler + nb[2] + orient) % 2 == 0);
00420
00421 genus = 1 - (euler + nb[2] + orient) / 2;
00422
00423 if (AGenus != NULL)
00424 * AGenus = genus;
00425 }
00426 }
00427
00428 string CGMapGeneric::getSurfaceName(int AB2, int AQ, int AG)
00429 {
00430 assert(0 <= AB2);
00431 assert(0 <= AQ && AQ <= 2);
00432 assert(0 <= AG);
00433
00434 ostringstream result;
00435
00436 result << "S(" << AB2 << "," << AQ << "," << AG << ")" << ": ";
00437
00438 switch (AQ)
00439 {
00440 case 0:
00441
00442 {
00443 if (AG == 0)
00444
00445 {
00446 switch (AB2)
00447 {
00448 case 0 : result << "Sphère"; break;
00449 case 1 : result << "Disque"; break;
00450 case 2 : result << "Ruban" ; break;
00451 default: result << "Sphère à " << AB2 << " bords";
00452 }
00453 }
00454 else
00455
00456 {
00457 result << "Tore";
00458
00459 if (AG > 1)
00460 result << " à " << AG << " trous";
00461
00462 if (AB2 > 0)
00463 result << (AG > 1 ? " et" : " à")
00464 << " " << AB2 << " bord" << (AB2 > 1 ? "s" : "");
00465 }
00466 }
00467 break;
00468 case 1:
00469
00470 {
00471 if (AB2 == 0)
00472 result << "Plan projectif réel";
00473 else
00474 result << "Ruban de Möbius";
00475
00476 if (AG > 0)
00477 result << " à " << AG << " trou" << (AG > 1 ? "s" : "");
00478
00479 if (AB2 > 1)
00480 result << (AG > 0 ? " et " : " à ") << AB2 << " bords";
00481 }
00482 break;
00483 case 2:
00484
00485 {
00486 result << "Bouteille de Klein";
00487
00488 if (AG > 0)
00489 result << " à " << AG << " trou" << (AG > 1 ? "s" : "");
00490
00491 if (AB2 > 0)
00492 result << (AG > 0 ? " et " : " à ")
00493 << AB2 << " bord" << (AB2 > 1 ? "s" : "");
00494 }
00495 break;
00496 default:
00497 assert(false);
00498 }
00499
00500 return result.str();
00501 }
00502
00503 bool CGMapGeneric::isConnex()
00504 {
00505 bool connex = true;
00506 int reached = getNewMark();
00507
00508
00509 markOrbit(getFirstDart(), ORBIT_CC, reached);
00510
00511
00512 for (CDynamicCoverageAll it(this); it.cont() && connex; ++it)
00513 if (! isMarked(*it, reached))
00514 connex = false;
00515
00516 if (connex)
00517 negateMaskMark(reached);
00518 else
00519 unmarkAll(reached);
00520
00521 freeMark(reached);
00522
00523 return connex;
00524 }
00525
00526 bool CGMapGeneric::checkTopology()
00527 {
00528
00529 for (int dim=0; dim<=3; ++dim)
00530 for (CDynamicCoverageAll it(this); it.cont(); ++it)
00531 if (!isFree(*it, dim) && *it != alpha(alpha(*it,dim),dim))
00532 {
00533 cerr << "CGMapGeneric::integrity: Le brin " << *it
00534 << " ne vérifie pas la contrainte "
00535 << "alpha" << dim << "(alpha" << dim << "(brin)) == brin." << endl;
00536
00537 return false;
00538 }
00539
00540
00541 bool ok = true;
00542
00543 TOrbit involutions[3] = { ORBIT_02, ORBIT_03, ORBIT_13 };
00544 int alphaI [3] = { 0 , 0 , 1 };
00545 int alphaJ [3] = { 2, 3, 3 };
00546
00547 int treated = getNewMark();
00548
00549 for (int invoIndex=0; invoIndex<3 && ok; ++invoIndex)
00550 {
00551 TOrbit orbit = involutions[invoIndex];
00552 int ai = alphaI[invoIndex];
00553 int aj = alphaJ[invoIndex];
00554
00555 for (CDynamicCoverageAll it(this); it.cont() && ok; ++it)
00556 if (!isMarked(*it, treated))
00557 {
00558 if (isFree(*it, ai) || isFree(*it, aj))
00559 setMark(*it, treated);
00560 else
00561 {
00562 ok =
00563 alpha( alpha(*it, ai) , aj) == alpha( alpha(*it, aj) , ai);
00564
00565 if (!ok)
00566 {
00567 cerr << "CGMapGeneric::checkTopology: L'involution "
00568 << (invoIndex==0 ? "02" : invoIndex==1 ? "03" : "13")
00569 << " n'est pas respectée pour le brin " << *it
00570 << "." << endl;
00571 }
00572
00573 markOrbit(*it, orbit, treated);
00574 }
00575 }
00576
00577 if (ok)
00578 negateMaskMark(treated);
00579 else
00580 unmarkAll(treated);
00581 }
00582
00583 freeMark(treated);
00584
00585 return ok;
00586 }
00587
00588 bool CGMapGeneric::checkEmbeddings(TOrbit AOrbit, int AAttributeIdentity,
00589 bool AEmbeddingMustExist)
00590 {
00591 assert(isOrbitUsed(AOrbit));
00592
00593 bool ok = true;
00594
00595 int treated = getNewMark();
00596
00597 for (CDynamicCoverageAll it(this); it.cont(); ++it)
00598 if (!isMarked(*it, treated))
00599 {
00600 int i = 0;
00601
00602 CCoverage * cov = getDynamicCoverage(*it, AOrbit);
00603
00604 for (; cov->cont(); ++(*cov))
00605 {
00606 if ((**cov)->getAttribute(AOrbit, AAttributeIdentity) != NULL)
00607 ++i;
00608
00609 setMark(**cov, treated);
00610 }
00611
00612 delete cov;
00613
00614 if (i>1 || (i==0 && AEmbeddingMustExist))
00615 {
00616 static const char * ORBIT_NAMES[16] =
00617 {
00618 "brin","0","1","01","2","02","12","volume","3","03","13","face",
00619 "23","arête","sommet","composante connexe"
00620 };
00621
00622 cerr << "CGMapGeneric::checkEmbeddings: La cellule '"
00623 << ORBIT_NAMES[AOrbit] << "' incidente au brin " << *it << " ";
00624
00625 if (i==0)
00626 cerr << "n'est pas plongée!" << endl;
00627 else
00628 cerr << " est plongée " << i << " fois!" << endl;
00629
00630 ok = false;
00631 }
00632 }
00633
00634 negateMaskMark(treated);
00635 freeMark(treated);
00636
00637 return ok;
00638 }
00639
00640 bool CGMapGeneric::isIClosedOrbit(CDart * ADart, int ADimension, TOrbit AOrbit)
00641 {
00642 assert(ADart!=NULL);
00643 assert(0<=ADimension && ADimension<=3);
00644
00645 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00646
00647 bool closed = true;
00648
00649 for (; closed && cov->cont(); (*cov)++)
00650 closed = ! isFree(**cov, ADimension);
00651
00652 delete cov;
00653
00654 return closed;
00655 }
00656
00657 bool CGMapGeneric::isIFreeOrbit(CDart * ADart, int ADimension, TOrbit AOrbit)
00658 {
00659 assert(ADart!=NULL);
00660 assert(0<=ADimension && ADimension<=3);
00661
00662 CCoverage * cov = getDynamicCoverage(ADart, AOrbit);
00663
00664 bool free = true;
00665
00666 for (; free && cov->cont(); (*cov)++)
00667 free = isFree(**cov, ADimension);
00668
00669 delete cov;
00670
00671 return free;
00672 }
00673
00674 int CGMapGeneric::getMapDimension()
00675 {
00676 int res = -1;
00677 int i = 0;
00678 for (CDynamicCoverageAll it(this); it.cont(); ++it)
00679 {
00680 for (i = res + 1; i < 4; ++i)
00681 if ( !isFree(*it, i) )
00682 {
00683 res = i;
00684 if (res == 3) return res;
00685 }
00686 }
00687
00688 return res;
00689 }
00690