src/INTERP_KERNEL/Geometric2D/QuadraticPolygon.cxx

   1 //  Copyright (C) 2007-2008  CEA/DEN, EDF R&D
   2 //
   3 //  This library is free software; you can redistribute it and/or
   4 //  modify it under the terms of the GNU Lesser General Public
   5 //  License as published by the Free Software Foundation; either
   6 //  version 2.1 of the License.
   7 //
   8 //  This library is distributed in the hope that it will be useful,
   9 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 //  Lesser General Public License for more details.
  12 //
  13 //  You should have received a copy of the GNU Lesser General Public
  14 //  License along with this library; if not, write to the Free Software
  15 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 //  See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19 #include "QuadraticPolygon.hxx"
  20 #include "ElementaryEdge.hxx"
  21 #include "EdgeArcCircle.hxx"
  22 #include "AbstractEdge.hxx"
  23 #include "EdgeLin.hxx"
  24 #include "Bounds.hxx"
  25 #include "Edge.txx"
  26
  27 #include <fstream>
  28 #include <iomanip>
  29
  30 using namespace std;
  31 using namespace INTERP_KERNEL;
  32
  33 namespace INTERP_KERNEL
  34 {
  35   const unsigned MAX_SIZE_OF_LINE_XFIG_FILE=1024;
  36 }
  37
  38 QuadraticPolygon::QuadraticPolygon(const char *file)
  39 {
  40   char currentLine[MAX_SIZE_OF_LINE_XFIG_FILE];
  41   ifstream stream(file);
  42   stream.exceptions(ios_base::eofbit);
  43   try
  44     {
  45       do
  46         stream.getline(currentLine,MAX_SIZE_OF_LINE_XFIG_FILE);
  47       while(strcmp(currentLine,"1200 2")!=0);
  48       do
  49         {
  50           Edge *newEdge=Edge::buildFromXfigLine(stream);
  51           if(!empty())
  52             newEdge->changeStartNodeWith(back()->getEndNode());
  53           pushBack(newEdge);
  54         }
  55       while(1);
  56     }
  57   catch(ifstream::failure& e)
  58     {
  59     }
  60   front()->changeStartNodeWith(back()->getEndNode());
  61 }
  62
  63 QuadraticPolygon::~QuadraticPolygon()
  64 {
  65 }
  66
  67 QuadraticPolygon *QuadraticPolygon::buildLinearPolygon(std::vector<Node *>& nodes)
  68 {
  69   QuadraticPolygon *ret=new QuadraticPolygon;
  70   int size=nodes.size();
  71   for(int i=0;i<size;i++)
  72     {
  73       ret->pushBack(new EdgeLin(nodes[i],nodes[(i+1)%size]));
  74       nodes[i]->decrRef();
  75     }
  76   return ret;
  77 }
  78
  79 QuadraticPolygon *QuadraticPolygon::buildArcCirclePolygon(std::vector<Node *>& nodes)
  80 {
  81   QuadraticPolygon *ret=new QuadraticPolygon;
  82   int size=nodes.size();
  83   for(int i=0;i<size/2;i++)
  84     {
  85       EdgeLin *e1,*e2;
  86       e1=new EdgeLin(nodes[i],nodes[i+size/2]);
  87       e2=new EdgeLin(nodes[i+size/2],nodes[(i+1)%(size/2)]);
  88       SegSegIntersector inters(*e1,*e2);
  89       bool colinearity=inters.areColinears();
  90       delete e1; delete e2;
  91       if(colinearity)
  92         ret->pushBack(new EdgeLin(nodes[i],nodes[(i+1)%(size/2)]));
  93       else
  94         ret->pushBack(new EdgeArcCircle(nodes[i],nodes[i+size/2],nodes[(i+1)%(size/2)]));
  95       nodes[i]->decrRef(); nodes[i+size/2]->decrRef();
  96     }
  97   return ret;
  98 }
  99
 100 void QuadraticPolygon::buildDbgFile(const std::vector<Node *>& nodes, const char *fileName)
 101 {
 102   ofstream file(fileName);
 103   file << setprecision(16);
 104   file << "  double coords[]=" << endl << "    { ";
 105   for(vector<Node *>::const_iterator iter=nodes.begin();iter!=nodes.end();iter++)
 106     {
 107       if(iter!=nodes.begin())
 108         file << "," << endl << "      ";
 109       file << (*(*iter))[0] << ", " << (*(*iter))[1];
 110     }
 111   file << "};" << endl;
 112 }
 113
 114 void QuadraticPolygon::closeMe() const
 115 {
 116   if(!front()->changeStartNodeWith(back()->getEndNode()))
 117     throw(Exception("big error: not closed polygon..."));
 118 }
 119
 120 void QuadraticPolygon::circularPermute()
 121 {
 122   if(_sub_edges.size()>1)
 123     {
 124       ElementaryEdge *first=_sub_edges.front();
 125       _sub_edges.pop_front();
 126       _sub_edges.push_back(first);
 127     }
 128 }
 129
 130 void QuadraticPolygon::dumpInXfigFileWithOther(const ComposedEdge& other, const char *fileName) const
 131 {
 132   ofstream file(fileName);
 133   const int resolution=1200;
 134   Bounds box;
 135   box.prepareForAggregation();
 136   fillBounds(box);
 137   other.fillBounds(box);
 138   dumpInXfigFile(file,resolution,box);
 139   other.ComposedEdge::dumpInXfigFile(file,resolution,box);
 140 }
 141
 142 void QuadraticPolygon::dumpInXfigFile(const char *fileName) const
 143 {
 144   ofstream file(fileName);
 145   const int resolution=1200;
 146   Bounds box;
 147   box.prepareForAggregation();
 148   fillBounds(box);
 149   dumpInXfigFile(file,resolution,box);
 150 }
 151
 152 void QuadraticPolygon::dumpInXfigFile(std::ostream& stream, int resolution, const Bounds& box) const
 153 {
 154   stream << "#FIG 3.2  Produced by xfig version 3.2.5-alpha5" << endl;
 155   stream << "Landscape" << endl;
 156   stream << "Center" << endl;
 157   stream << "Metric" << endl;
 158   stream << "Letter" << endl;
 159   stream << "100.00" << endl;
 160   stream << "Single" << endl;
 161   stream << "-2" << endl;
 162   stream << resolution << " 2" << endl;
 163   ComposedEdge::dumpInXfigFile(stream,resolution,box);
 164 }
 165
 166 /*!
 167  * Warning contrary to intersectWith method this method is \b NOT const. 'this' and 'other' are modified after call of this method.
 168  */
 169 double QuadraticPolygon::intersectWithAbs(QuadraticPolygon& other)
 170 {
 171   double ret=0.;
 172   double fact=normalize(&other);
 173   vector<QuadraticPolygon *> polygs=intersectMySelfWith(other);
 174   for(vector<QuadraticPolygon *>::iterator iter=polygs.begin();iter!=polygs.end();iter++)
 175     {
 176       ret+=fabs((*iter)->getArea());
 177       delete *iter;
 178     }
 179   return ret*fact*fact;
 180 }
 181
 182 /*!
 183  * \b WARNING this method is const and other is const too. \b BUT location of Edges in 'this' and 'other' are nevertheless modified.
 184  * This is possible because loc attribute in Edge class is mutable.
 185  * This implies that if 'this' or/and 'other' are reused for intersect* method initLocations has to be called on each of this/them.
 186  */
 187 double QuadraticPolygon::intersectWith(const QuadraticPolygon& other) const
 188 {
 189   double ret=0.;
 190   vector<QuadraticPolygon *> polygs=intersectMySelfWith(other);
 191   for(vector<QuadraticPolygon *>::iterator iter=polygs.begin();iter!=polygs.end();iter++)
 192     {
 193       ret+=fabs((*iter)->getArea());
 194       delete *iter;
 195     }
 196   return ret;
 197 }
 198
 199 /*!
 200  * \b WARNING this method is const and other is const too. \b BUT location of Edges in 'this' and 'other' are nevertheless modified.
 201  * This is possible because loc attribute in Edge class is mutable.
 202  * This implies that if 'this' or/and 'other' are reused for intersect* method initLocations has to be called on each of this/them.
 203  */
 204 void QuadraticPolygon::intersectForPerimeter(const QuadraticPolygon& other, double& perimeterThisPart, double& perimeterOtherPart, double& perimeterCommonPart) const
 205 {
 206   perimeterThisPart=0.; perimeterOtherPart=0.; perimeterCommonPart=0.;
 207   QuadraticPolygon cpyOfThis(*this);
 208   QuadraticPolygon cpyOfOther(other); int nbOfSplits=0;
 209   splitPolygonsEachOther(cpyOfThis,cpyOfOther,nbOfSplits);
 210   performLocatingOperation(cpyOfOther);
 211   other.performLocatingOperation(cpyOfThis);
 212   cpyOfThis.dispatchPerimeterExcl(perimeterThisPart,perimeterCommonPart);
 213   cpyOfOther.dispatchPerimeterExcl(perimeterOtherPart,perimeterCommonPart);
 214   perimeterCommonPart/=2.;
 215 }
 216
 217 /*!
 218  * \b WARNING this method is const and other is const too. \b BUT location of Edges in 'this' and 'other' are nevertheless modified.
 219  * This is possible because loc attribute in Edge class is mutable.
 220  * This implies that if 'this' or/and 'other' are reused for intersect* method initLocations has to be called on each of this/them.
 221  *
 222  * polThis.size()==this->size() and polOther.size()==other.size().
 223  * For each ElementaryEdge of 'this', the corresponding contribution in resulting polygon is in 'polThis'.
 224  * For each ElementaryEdge of 'other', the corresponding contribution in resulting polygon is in 'polOther'.
 225  * As consequence common part are counted twice (in polThis \b and in polOther).
 226  */
 227 void QuadraticPolygon::intersectForPerimeterAdvanced(const QuadraticPolygon& other, std::vector< double >& polThis, std::vector< double >& polOther) const
 228 {
 229   polThis.resize(size());
 230   polOther.resize(other.size());
 231   IteratorOnComposedEdge it1((QuadraticPolygon *)this);
 232   int edgeId=0;
 233   for(it1.first();!it1.finished();it1.next(),edgeId++)
 234     {
 235       ElementaryEdge* curE1=it1.current();
 236       QuadraticPolygon cpyOfOther(other);
 237       QuadraticPolygon tmp;
 238       tmp.pushBack(curE1->clone());
 239       int tmp2;
 240       splitPolygonsEachOther(tmp,cpyOfOther,tmp2);
 241       other.performLocatingOperation(tmp);
 242       tmp.dispatchPerimeter(polThis[edgeId]);
 243     }
 244   //
 245   IteratorOnComposedEdge it2((QuadraticPolygon *)&other);
 246   edgeId=0;
 247   for(it2.first();!it2.finished();it2.next(),edgeId++)
 248     {
 249       ElementaryEdge* curE2=it2.current();
 250       QuadraticPolygon cpyOfThis(*this);
 251       QuadraticPolygon tmp;
 252       tmp.pushBack(curE2->clone());
 253       int tmp2;
 254       splitPolygonsEachOther(tmp,cpyOfThis,tmp2);
 255       performLocatingOperation(tmp);
 256       tmp.dispatchPerimeter(polOther[edgeId]);
 257     }
 258 }
 259
 260
 261 /*!
 262  * numberOfCreatedPointsPerEdge is resized to the number of edges of 'this'.
 263  * This method returns in ordered maner the number of newly created points per edge.
 264  * This method performs a split process between 'this' and 'other' that gives the result PThis.
 265  * Then for each edges of 'this' this method counts how many edges in Pthis have the same id.
 266  */
 267 void QuadraticPolygon::intersectForPoint(const QuadraticPolygon& other, std::vector< int >& numberOfCreatedPointsPerEdge) const
 268 {
 269   numberOfCreatedPointsPerEdge.resize(size());
 270   IteratorOnComposedEdge it1((QuadraticPolygon *)this);
 271   int edgeId=0;
 272   for(it1.first();!it1.finished();it1.next(),edgeId++)
 273     {
 274       ElementaryEdge* curE1=it1.current();
 275       QuadraticPolygon cpyOfOther(other);
 276       QuadraticPolygon tmp;
 277       tmp.pushBack(curE1->clone());
 278       int tmp2;
 279       splitPolygonsEachOther(tmp,cpyOfOther,tmp2);
 280       numberOfCreatedPointsPerEdge[edgeId]=tmp.recursiveSize()-1;
 281     }
 282 }
 283
 284 /*!
 285  * \b WARNING this method is const and other is const too. \b BUT location of Edges in 'this' and 'other' are nevertheless modified.
 286  * This is possible because loc attribute in Edge class is mutable.
 287  * This implies that if 'this' or/and 'other' are reused for intersect* method initLocations has to be called on each of this/them.
 288  */
 289 std::vector<QuadraticPolygon *> QuadraticPolygon::intersectMySelfWith(const QuadraticPolygon& other) const
 290 {
 291   QuadraticPolygon cpyOfThis(*this);
 292   QuadraticPolygon cpyOfOther(other); int nbOfSplits=0;
 293   splitPolygonsEachOther(cpyOfThis,cpyOfOther,nbOfSplits);
 294   //At this point cpyOfThis and cpyOfOther have been splited at maximum edge so that in/out can been done.
 295   performLocatingOperation(cpyOfOther);
 296   return other.buildIntersectionPolygons(cpyOfThis,cpyOfOther);
 297 }
 298
 299 /*!
 300  * This method is typically the first step of boolean operations between pol1 and pol2.
 301  * This method perform the minimal splitting so that at the end each edges constituting pol1 are fully either IN or OUT or ON.
 302  * @param pol1 IN/OUT param that is equal to 'this' when called.
 303  */
 304 void QuadraticPolygon::splitPolygonsEachOther(QuadraticPolygon& pol1, QuadraticPolygon& pol2, int& nbOfSplits)
 305 {
 306   IteratorOnComposedEdge it1(&pol1),it2(&pol2);
 307   MergePoints merge;
 308   ComposedEdge *c1=new ComposedEdge;
 309   ComposedEdge *c2=new ComposedEdge;
 310   for(it2.first();!it2.finished();it2.next())
 311     {
 312       ElementaryEdge* curE2=it2.current();
 313       if(!curE2->isThereStartPoint())
 314         it1.first();
 315       else
 316         it1=curE2->getIterator();
 317       for(;!it1.finished();)
 318         {
 319
 320           ElementaryEdge* curE1=it1.current();
 321           merge.clear(); nbOfSplits++;
 322           if(curE1->getPtr()->intersectWith(curE2->getPtr(),merge,*c1,*c2))
 323             {
 324               if(!curE1->getDirection()) c1->reverse();
 325               if(!curE2->getDirection()) c2->reverse();
 326               updateNeighbours(merge,it1,it2,c1,c2);
 327               //Substitution of simple edge by sub-edges.
 328               delete curE1; // <-- destroying simple edge coming from pol1
 329               delete curE2; // <-- destroying simple edge coming from pol2
 330               it1.insertElemEdges(c1,true);// <-- 2nd param is true to go next.
 331               it2.insertElemEdges(c2,false);// <-- 2nd param is false to avoid to go next.
 332               curE2=it2.current();
 333               //
 334               it1.assignMySelfToAllElems(c2);//To avoid that others
 335               SoftDelete(c1);
 336               SoftDelete(c2);
 337               c1=new ComposedEdge;
 338               c2=new ComposedEdge;
 339             }
 340           else
 341             {
 342               updateNeighbours(merge,it1,it2,curE1,curE2);
 343               it1.next();
 344             }
 345         }
 346     }
 347   Delete(c1);
 348   Delete(c2);
 349 }
 350
 351 void QuadraticPolygon::performLocatingOperation(QuadraticPolygon& pol2) const
 352 {
 353   IteratorOnComposedEdge it(&pol2);
 354   TypeOfEdgeLocInPolygon loc=FULL_ON_1;
 355   for(it.first();!it.finished();it.next())
 356     {
 357       ElementaryEdge *cur=it.current();
 358       loc=cur->locateFullyMySelf(*this,loc);
 359     }
 360 }
 361
 362 /*!
 363  * Given 2 polygons 'pol1' and 'pol2' (localized) the resulting polygons are returned.
 364  *
 365  * this : pol2 simplified.
 366  * @param pol1 pol1 split.
 367  * @param pol2 pol2 split.
 368  */
 369 std::vector<QuadraticPolygon *> QuadraticPolygon::buildIntersectionPolygons(const QuadraticPolygon& pol1, const QuadraticPolygon& pol2) const
 370 {
 371   vector<QuadraticPolygon *> ret;
 372   list<QuadraticPolygon *> pol2Zip=pol2.zipConsecutiveInSegments();
 373   if(!pol2Zip.empty())
 374     closePolygons(pol2Zip,pol1,ret);
 375   else
 376     {//borders of pol2 do not cross pol1,and pol2 borders are outside of pol1. That is to say, either pol2 and pol1
 377       //do not overlap or  pol1 is fully inside pol2. So in the first case no intersection, in the other case
 378       //the intersection is pol1.
 379       ElementaryEdge *e1FromPol1=pol1[0];
 380       TypeOfEdgeLocInPolygon loc=FULL_ON_1;
 381       loc=e1FromPol1->locateFullyMySelf(*this,loc);
 382       if(loc==FULL_IN_1)
 383         ret.push_back(new QuadraticPolygon(pol1));
 384     }
 385   return ret;
 386 }
 387
 388 /*!
 389  * Returns parts of potentially non closed-polygons. Each returned polygons are not mergeable.
 390  * this : pol2 split and locallized.
 391  */
 392 std::list<QuadraticPolygon *> QuadraticPolygon::zipConsecutiveInSegments() const
 393 {
 394   list<QuadraticPolygon *> ret;
 395   IteratorOnComposedEdge it((ComposedEdge *)this);
 396   int nbOfTurns=recursiveSize();
 397   int i=0;
 398   if(!it.goToNextInOn(false,i,nbOfTurns))
 399     return ret;
 400   i=0;
 401   //
 402   while(i<nbOfTurns)
 403     {
 404       QuadraticPolygon *tmp1=new QuadraticPolygon;
 405       TypeOfEdgeLocInPolygon loc=it.current()->getLoc();
 406       while(loc!=FULL_OUT_1 && i<nbOfTurns)
 407         {
 408           ElementaryEdge *tmp3=it.current()->clone();
 409           tmp1->pushBack(tmp3);
 410           it.nextLoop(); i++;
 411           loc=it.current()->getLoc();
 412         }
 413       if(tmp1->empty())
 414         {
 415           delete tmp1;
 416           continue;
 417         }
 418       ret.push_back(tmp1);
 419       it.goToNextInOn(true,i,nbOfTurns);
 420     }
 421   return ret;
 422 }
 423
 424 /*!
 425  * 'this' should be considered as pol2Simplified.
 426  * @param pol2zip is a list of set of edges (openned polygon) coming from split polygon 2.
 427  * @param pol1 is split pol1.
 428  * @param results the resulting \b CLOSED polygons.
 429  */
 430 void QuadraticPolygon::closePolygons(std::list<QuadraticPolygon *>& pol2Zip, const QuadraticPolygon& pol1,
 431                                      std::vector<QuadraticPolygon *>& results) const
 432 {
 433   bool directionKnownInPol1=false;
 434   bool directionInPol1;
 435   for(list<QuadraticPolygon *>::iterator iter=pol2Zip.begin();iter!=pol2Zip.end();)
 436     {
 437       if((*iter)->completed())
 438         {
 439           results.push_back(*iter);
 440           directionKnownInPol1=false;
 441           iter=pol2Zip.erase(iter);
 442           continue;
 443         }
 444       if(!directionKnownInPol1)
 445         if(!(*iter)->amIAChanceToBeCompletedBy(pol1,*this,directionInPol1))
 446           { delete *iter; iter=pol2Zip.erase(iter); continue; }
 447         else
 448           directionKnownInPol1=true;
 449       list<QuadraticPolygon *>::iterator iter2=iter; iter2++;
 450       list<QuadraticPolygon *>::iterator iter3=(*iter)->fillAsMuchAsPossibleWith(pol1,iter2,pol2Zip.end(),directionInPol1);
 451       if(iter3!=pol2Zip.end())
 452         {
 453           (*iter)->pushBack(*iter3);
 454           SoftDelete(*iter3);
 455           pol2Zip.erase(iter3);
 456         }
 457     }
 458 }
 459
 460 /*!
 461  * 'this' is expected to be set of edges (not closed) of pol2 split.
 462  */
 463 bool QuadraticPolygon::amIAChanceToBeCompletedBy(const QuadraticPolygon& pol1Splitted,const QuadraticPolygon& pol2NotSplitted, bool& direction)
 464 {
 465   IteratorOnComposedEdge it((QuadraticPolygon *)&pol1Splitted);
 466   bool found=false;
 467   Node *n=getEndNode();
 468   ElementaryEdge *cur=it.current();
 469   for(it.first();!it.finished() && !found;)
 470     {
 471       cur=it.current();
 472       found=(cur->getStartNode()==n);
 473       if(!found)
 474         it.next();
 475     }
 476   if(!found)
 477     throw Exception("Internal error : polygons uncompatible each others. Should never happend");
 478   //Ok we found correspondance between this and pol1. Searching for right direction to close polygon.
 479   ElementaryEdge *e=_sub_edges.back();
 480   if(e->getLoc()==FULL_ON_1)
 481     {
 482       if(e->getPtr()==cur->getPtr())
 483         {
 484           direction=false;
 485           it.previousLoop();
 486           cur=it.current();
 487           Node *repr=cur->getPtr()->buildRepresentantOfMySelf();
 488           bool ret=pol2NotSplitted.isInOrOut(repr);
 489           repr->decrRef();
 490           return ret;
 491         }
 492       else
 493         {
 494           direction=true;
 495           Node *repr=cur->getPtr()->buildRepresentantOfMySelf();
 496           bool ret=pol2NotSplitted.isInOrOut(repr);
 497           repr->decrRef();
 498           return ret;
 499         }
 500     }
 501   else
 502     direction=cur->locateFullyMySelfAbsolute(pol2NotSplitted)==FULL_IN_1;
 503   return true;
 504 }
 505
 506 /*!
 507  * This method fills as much as possible 'this' (part of pol2 split) with edges of 'pol1Splitted'.
 508  */
 509 std::list<QuadraticPolygon *>::iterator QuadraticPolygon::fillAsMuchAsPossibleWith(const QuadraticPolygon& pol1Splitted,
 510                                                                                    std::list<QuadraticPolygon *>::iterator iStart,
 511                                                                                    std::list<QuadraticPolygon *>::iterator iEnd,
 512                                                                                    bool direction)
 513 {
 514   IteratorOnComposedEdge it((QuadraticPolygon *)&pol1Splitted);
 515   bool found=false;
 516   Node *n=getEndNode();
 517   ElementaryEdge *cur;
 518   for(it.first();!it.finished() && !found;)
 519     {
 520       cur=it.current();
 521       found=(cur->getStartNode()==n);
 522       if(!found)
 523         it.next();
 524     }
 525   if(!direction)
 526     it.previousLoop();
 527   Node *nodeToTest;
 528   std::list<QuadraticPolygon *>::iterator ret;
 529   do
 530     {
 531       cur=it.current();
 532       ElementaryEdge *tmp=cur->clone();
 533       if(!direction)
 534         tmp->reverse();
 535       pushBack(tmp);
 536       nodeToTest=tmp->getEndNode();
 537       direction?it.nextLoop():it.previousLoop();
 538       ret=checkInList(nodeToTest,iStart,iEnd);
 539       if(completed())
 540         return iEnd;
 541     }
 542   while(ret==iEnd);
 543   return ret;
 544 }
 545
 546 std::list<QuadraticPolygon *>::iterator QuadraticPolygon::checkInList(Node *n, std::list<QuadraticPolygon *>::iterator iStart,
 547                                                                       std::list<QuadraticPolygon *>::iterator iEnd)
 548 {
 549   for(list<QuadraticPolygon *>::iterator iter=iStart;iter!=iEnd;iter++)
 550     if((*iter)->isNodeIn(n))
 551       return iter;
 552   return iEnd;
 553 }