src/GLViewer/GLViewer_Tools.cxx

   1 // Copyright (C) 2007-2022  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License, or (at your option) any later version.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22
  23 //  Author : OPEN CASCADE
  24 // File:      GLViewer_Tools.cxx
  25 // Created:   April, 2005
  26 //
  27 #include "GLViewer_Tools.h"
  28
  29 #ifdef __APPLE__
  30 #include <OpenGL/gl.h>
  31 #else
  32 #include <GL/gl.h>
  33 #endif
  34
  35 #include <iostream>
  36 #include <string.h>
  37
  38 /*!
  39   Constructor
  40   \param size - size of internal array
  41 */
  42 GLViewer_LineList::GLViewer_LineList( int size )
  43 {
  44   myRealSize = 2*size;
  45   mySegmentNumber = 0;
  46   myMainCoord = 0.0;
  47
  48   myArray = new double[myRealSize];
  49
  50   if( !myArray )
  51   {
  52     std::cout << "Can't allocate memory: " << size << std::endl;
  53     myRealSize = 0;
  54   }
  55   else
  56     memset( myArray, 0, myRealSize*sizeof(double) );
  57 }
  58
  59 /*!
  60   Destructor
  61 */
  62 GLViewer_LineList::~GLViewer_LineList()
  63 {
  64   delete myArray;
  65 }
  66
  67 /*!
  68   Adds new line segment to list
  69   \param coord1, coord2 - co-ordinates of points
  70 */
  71 bool GLViewer_LineList::addSegment( double coord1, double coord2 )
  72 {
  73   if( coord1 > coord2 )
  74   {
  75     double temp = coord1;
  76     coord1 = coord2;
  77     coord2 = temp;
  78   }
  79
  80   if( 2*mySegmentNumber == myRealSize || !myArray )
  81     return false;
  82
  83   int index = 0;
  84   double c1, c2;
  85   while( index < mySegmentNumber)
  86   {
  87     readSegment( index, c1, c2 );
  88     if( coord1 < c1 && coord2 < c1 )
  89     {
  90       for( int i = mySegmentNumber; i > index - 1; i--)
  91       {
  92         myArray[2*i] = myArray[2*i-2]; //2*(i-1)
  93         myArray[2*i+1] = myArray[2*i-1];//2*(i-1)+1
  94       }
  95       myArray[0] = coord1;
  96       myArray[1] = coord2;
  97       // mySegmentNumber; what is means ?
  98       return true;
  99     }
 100     else if( coord1 < c1 && coord2 < c2 )
 101     {
 102       myArray[index*2] = coord1;
 103       return true;
 104     }
 105     else if( c1 < coord1 && coord2 < c2 )
 106     {
 107       return true;
 108     }
 109     else if( coord1 < c2 && c2 < coord2 )
 110     {
 111       if( c1 > coord1 )
 112         myArray[2*index] = coord1;
 113
 114       if( index != mySegmentNumber - 1 )
 115       {
 116         for( int i = index+1; i < mySegmentNumber; i++ )
 117         {
 118           if( coord2 < myArray[2*i] )
 119           {
 120             myArray[2*index+1] = coord2;
 121             if( index+1 != i )
 122             {
 123               for( int j = 0; i+j < mySegmentNumber;j++ )
 124               {
 125                 myArray[2*(index+1+j)] = myArray[2*(i+j)];
 126                 myArray[2*(index+1+j)+1] = myArray[2*(i+j)+1];
 127               }
 128               for( int k = 0; k < mySegmentNumber - i; k++ )
 129               {
 130                 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
 131                 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
 132               }
 133               mySegmentNumber -= i - index-1;
 134             }
 135             return true;
 136           }
 137           else if( coord2 < myArray[2*i+1] )
 138           {
 139             myArray[2*index+1] = myArray[2*i+1];
 140
 141             for( int j = index+1; j < mySegmentNumber-1;j++ )
 142             {
 143               myArray[2*j] = myArray[2*(i+j-index)];
 144               myArray[2*j+1] = myArray[2*(i+j-index)+1];
 145             }
 146             for( int k = 0; k < mySegmentNumber - i-1; k++ )
 147             {
 148               myArray[2*(mySegmentNumber - 1- k)] = 0.0;
 149               myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
 150             }
 151             mySegmentNumber -= i - index;
 152             return true;
 153           }
 154         }
 155       }
 156       else
 157       {
 158         myArray[2*index+1] = coord2;
 159         return true;
 160       }
 161     }
 162     index++;
 163   }
 164
 165   myArray[mySegmentNumber*2] = coord1;
 166   myArray[mySegmentNumber*2+1] = coord2;
 167   mySegmentNumber++;
 168
 169   return true;
 170 }
 171
 172 /*!
 173   Gets info about segment
 174   \param theIndex - index of segment
 175   \param coord1, coord2 - co-ordinates of points
 176 */
 177 bool GLViewer_LineList::readSegment( int theIndex, double& coord1, double& coord2 )
 178 {
 179   if( theIndex > mySegmentNumber || !myArray)
 180     return false;
 181
 182   coord1 = myArray[theIndex*2];
 183   coord2 = myArray[theIndex*2+1];
 184
 185   return true;
 186 }
 187
 188 /*!
 189   \return true if line list covers point
 190   \param thePoint - point co-ordinate
 191 */
 192 int GLViewer_LineList::contains( double thePoint ) const
 193 {
 194   if( !myArray || mySegmentNumber == 0 )
 195     return -1;
 196
 197   for( int i = 0; i < mySegmentNumber; i++ )
 198     if( myArray[2*i] <= thePoint && thePoint <= myArray[2*i+1] )
 199       return i;
 200
 201   return -1;
 202
 203 }
 204
 205 /*!
 206   Removes segment
 207   \param theIndex - segment index
 208 */
 209 bool GLViewer_LineList::removeSegment( int theIndex )
 210 {
 211   if( theIndex > mySegmentNumber || !myArray)
 212     return false;
 213
 214   for( int i = theIndex; i < mySegmentNumber; i++ )
 215   {
 216     myArray[i*2] = myArray[(i+1)*2];
 217     myArray[i*2+1] = myArray[(i+1)*2+1];
 218   }
 219   mySegmentNumber--;
 220   myArray[mySegmentNumber*2] = 0.0;
 221   myArray[mySegmentNumber*2+1] = 0.0;
 222   return true;
 223 }
 224
 225 /*!
 226   Removes segment from line list
 227   \param coord1, coord2 - co-ordinates of points
 228 */
 229 bool GLViewer_LineList::removeSegment( double coord1, double coord2 )
 230 {
 231   if( coord1 > coord2 )
 232   {
 233     double temp = coord1;
 234     coord1 = coord2;
 235     coord2 = temp;
 236   }
 237
 238   if( 2*mySegmentNumber == myRealSize || !myArray )
 239     return false;
 240
 241   int index = 0;
 242   double c1, c2;
 243   while( index < mySegmentNumber)
 244   {
 245     readSegment( index, c1, c2 );
 246     if( coord1 < c1 && coord2 < c1 )
 247     {
 248       //nothing
 249       return true;
 250     }
 251     else if( coord1 < c1 && coord2 < c2 )
 252     {
 253       myArray[index*2] = coord2;
 254       return true;
 255     }
 256     else if( c1 < coord1 && coord2 < c2 )
 257     {
 258       if( 2*mySegmentNumber == myRealSize )
 259         return false;
 260       for( int i = mySegmentNumber; i > index + 1; i-- )
 261       {
 262         myArray[2*i] = myArray[2*(i-1)];
 263         myArray[2*i+1] = myArray[2*(i-1)+1];
 264       }
 265       myArray[2*(index+1)+1] = myArray[2*index+1];
 266       myArray[2*(index+1)] = coord2;
 267       myArray[2*index+1] = coord1;
 268       mySegmentNumber++;
 269       return true;
 270     }
 271     else if( coord1 < c2 && c2 < coord2 )
 272     {
 273       if( c1 < coord1 )
 274       {
 275         myArray[2*index+1] = coord1;
 276       }
 277
 278       if( index != mySegmentNumber - 1 )
 279       {
 280         for( int i = index+1; i < mySegmentNumber; i++ )
 281         {
 282           if( coord2 < myArray[2*i] )
 283           {
 284             if( index+1 != i )
 285             {
 286               for( int j = 1; i+j-1 < mySegmentNumber;j++ )
 287               {
 288                 myArray[2*(index+j)] = myArray[2*(i+j-1)];
 289                 myArray[2*(index+j)+1] = myArray[2*(i+j-1)+1];
 290               }
 291               for( int k = 0; k < mySegmentNumber - i; k++ )
 292               {
 293                 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
 294                 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
 295               }
 296               mySegmentNumber -= i - index -1;
 297             }
 298             else
 299             {
 300               if( !(c1 < coord1) )
 301               {
 302                 for( int j = 0; index + j + 1 < mySegmentNumber;j++ )
 303                 {
 304                   myArray[2*(index+j)] = myArray[2*(index+j+1)];
 305                   myArray[2*(index+j)+1] = myArray[2*(index+j+1)+1];
 306                 }
 307
 308                 myArray[2*(mySegmentNumber - 1)] = 0.0;
 309                 myArray[2*(mySegmentNumber - 1)+1] = 0.0;
 310
 311                 mySegmentNumber --;
 312               }
 313
 314             }
 315
 316             return true;
 317
 318           }
 319           else if( coord2 < myArray[2*i+1] )
 320           {
 321             if( index+1 != i )
 322             {
 323               if( c1 < coord1 )
 324                 index++;
 325
 326               myArray[2*index] = coord2;
 327               myArray[2*index+1] = myArray[2*i+1];
 328
 329               for( int j = 1; i+j < mySegmentNumber;j++ )
 330               {
 331                 myArray[2*(index+j)] = myArray[2*(i+j)];
 332                 myArray[2*(index+j)+1] = myArray[2*(i+j)+1];
 333               }
 334               for( int k = 0; k < mySegmentNumber - i - 1; k++ )
 335               {
 336                 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
 337                 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
 338               }
 339               mySegmentNumber -= i - index;
 340             }
 341             else
 342             {
 343               if( c1 < coord1 )
 344               {
 345                 myArray[2*(index+1)] = coord2;
 346                 return true;
 347               }
 348               else
 349               {
 350                 myArray[2*(index)] = coord2;
 351                 myArray[2*(index)+1] = myArray[2*(index+1)+1];
 352                 for( int j = index+1; j < mySegmentNumber-1; j++ )
 353                 {
 354                   myArray[2*j] = myArray[2*(j+1)];
 355                   myArray[2*j+1] = myArray[2*(j+1)+1];
 356                 }
 357                 mySegmentNumber--;
 358                 myArray[2*mySegmentNumber] = 0.0;
 359                 myArray[2*mySegmentNumber+1] = 0.0;
 360               }
 361             }
 362             return true;
 363           }
 364         }
 365       }
 366       else
 367       {
 368         if( !(c1 < coord1) )
 369         {
 370           mySegmentNumber--;
 371           myArray[2*index] = 0.0;
 372           myArray[2*index+1] = 0.0;
 373         }
 374       }
 375     }
 376     index++;
 377   }
 378   return true;
 379 }
 380
 381 /*!
 382   Clears line list
 383 */
 384 void GLViewer_LineList::clear()
 385 {
 386   if( myArray )
 387     memset( myArray, 0, myRealSize*sizeof(double) );
 388 }
 389
 390 /*!
 391   Prints debug info about line list
 392 */
 393 void GLViewer_LineList::print()
 394 {
 395   std::cout << "MainCoord: " << myMainCoord <<" SIZE: " << myRealSize << " ENum: " << mySegmentNumber << " :::";
 396   for( int i = 0; i < mySegmentNumber; i++ )
 397     std::cout << "  " << myArray[2*i] << " " << myArray[2*i+1] << " | ";
 398
 399   std::cout << std::endl;
 400 }
 401
 402 /*!
 403   Draws line list with help of OpenGL
 404   \param theDim - dimension
 405 */
 406 void GLViewer_LineList::show( FieldDim theDim )
 407 {
 408   if( !myArray )
 409     return;
 410
 411   glColor3f( 1.0, 0.0, 1.0 );
 412   if( theDim == FD_X )
 413   {
 414     glBegin( GL_LINES );
 415       for( int i = 0; i < mySegmentNumber; i++ )
 416       {
 417         glVertex2d( myArray[2*i], myMainCoord );
 418         glVertex2d( myArray[2*i+1], myMainCoord );
 419       }
 420     glEnd();
 421   }
 422   else if( theDim == FD_Y )
 423   {
 424     glBegin( GL_LINES );
 425       for( int i = 0; i < mySegmentNumber; i++ )
 426       {
 427         glVertex2d( myMainCoord, myArray[2*i]  );
 428         glVertex2d( myMainCoord, myArray[2*i+1] );
 429       }
 430     glEnd();
 431   }
 432 }
 433
 434
 435 /*!
 436   Constructor
 437 */
 438 GLViewer_LineField::GLViewer_LineField()
 439 {
 440   myCurArrayIndex = 0;
 441   myGraphArray1 = NULL;
 442   myGraphArray2 = NULL;
 443
 444   myCurCount = 0;
 445
 446   myXSize = 0;
 447   myYSize = 0;
 448   myXLineArray = NULL;
 449   myYLineArray = NULL;
 450 }
 451
 452 /*!
 453   Constructor
 454 */
 455 GLViewer_LineField::GLViewer_LineField( const int theMAXSize, const int theXN, const int theYN )
 456 {
 457   myCurArrayIndex = 0;
 458   myGraphArray1 = NULL;
 459   myGraphArray2 = NULL;
 460
 461   myCurCount = 0;
 462
 463   if( theXN <= 0 || theYN <= 0 )
 464   {
 465     myXSize = 0;
 466     myYSize = 0;
 467     myXLineArray = NULL;
 468     myYLineArray = NULL;
 469   }
 470   else
 471   {
 472     myXLineArray = new GLViewer_LineList*[theXN];
 473     myYLineArray = new GLViewer_LineList*[theYN];
 474
 475     for( int i = 0; i < theXN; i++ )
 476       myXLineArray[i] = new GLViewer_LineList( theMAXSize );
 477
 478     for( int j = 0; j < theYN; j++ )
 479       myYLineArray[j] = new GLViewer_LineList( theMAXSize );
 480
 481     myXSize = theXN;
 482     myYSize = theYN;
 483   }
 484 }
 485
 486 /*!
 487   Destructor
 488 */
 489 GLViewer_LineField::~GLViewer_LineField()
 490 {
 491   if( myXLineArray )
 492   {
 493     for( int i = 0; i < myXSize; i++ )
 494       delete myXLineArray[i];
 495
 496     delete myXLineArray;
 497   }
 498
 499   if( myYLineArray )
 500   {
 501     for( int j = 0; j < myYSize; j++ )
 502       delete myYLineArray[j];
 503
 504     delete myYLineArray;
 505   }
 506
 507   if( myGraphArray1 )
 508     delete myGraphArray1;
 509
 510   if( myGraphArray2 )
 511     delete myGraphArray2;
 512 }
 513
 514 /*!
 515   Adds line
 516 */
 517 void GLViewer_LineField::addLine( FieldDim, GLViewer_LineList* )
 518 {
 519   //not implemented
 520 }
 521
 522 /*!
 523   Adds line
 524   \param theDim - dimension
 525   \param theMC - main co-ordinate
 526   \param theBegin - start co-ordinate
 527   \param theEnd - end co-ordinate
 528 */
 529 void GLViewer_LineField:: addLine( FieldDim theDim, double theMC, double theBegin, double theEnd )
 530 {
 531   GLViewer_LineList* aLL = new GLViewer_LineList( 1 );
 532   aLL->addSegment( theBegin, theEnd );
 533   aLL->setMainCoord( theMC );
 534   addLine( theDim, aLL );
 535 }
 536
 537 /*!
 538   Adds line
 539   \param theDim - dimension
 540   \param theLL - main co-ordinate
 541   \param thePosition - index in list
 542 */
 543 int GLViewer_LineField::insertLine( FieldDim theDim, GLViewer_LineList* theLL, int thePosition )
 544 {
 545   if( !myXLineArray || !myYLineArray )
 546     return -1;
 547
 548   GLViewer_LineList** anArray = getLLArray( theDim );
 549   if( !anArray )
 550     return -1;
 551
 552   int size = getDimSize( theDim );
 553
 554   if( thePosition >= size )
 555     return -1;
 556   else if( thePosition < 0 )
 557   {
 558     if( anArray[size-1]->count() != 0 ) // no more space
 559       return -1;
 560
 561     for( int i = 0; i < size; i++ )
 562     {
 563       if( anArray[i]->count() == 0 )
 564       {
 565         delete anArray[i];
 566         anArray[i] = theLL;
 567         return i;
 568       }
 569
 570       double cur_mc = anArray[i]->mainCoord();
 571       if( theLL->mainCoord() < cur_mc )
 572       {
 573         for( int j = 0; j+i+1 < size; j++ )
 574         {
 575           delete anArray[size-j-1];
 576           anArray[size-j-1] = anArray[size-j-2];
 577         }
 578         delete anArray[i];
 579         anArray[i] = theLL;
 580         return i;
 581       }
 582     }
 583   }
 584   else
 585   {
 586     delete anArray[thePosition];
 587     anArray[thePosition] = theLL;
 588     return thePosition;
 589   }
 590
 591   return -1;
 592 }
 593
 594 /*!
 595   Adds line
 596   \param theDim - dimension
 597   \param theMainCoord - main co-ordinate
 598   \param theBegin - start co-ordinate
 599   \param theEnd - end co-ordinate
 600   \param thePosition - index in list
 601 */
 602 int GLViewer_LineField::insertLine( FieldDim theDim, double theMainCoord, double theBegin, double theEnd, int thePosition )
 603 {
 604   GLViewer_LineList* aLL = new GLViewer_LineList( 1 );
 605   aLL->addSegment( theBegin, theEnd );
 606   aLL->setMainCoord( theMainCoord );
 607   return insertLine( theDim, aLL, thePosition );
 608 }
 609
 610 /*!
 611   \return other dimension
 612 */
 613 FieldDim GLViewer_LineField::invertDim( FieldDim theFD )
 614 {
 615   if( theFD == FD_X )
 616     return FD_Y;
 617   else
 618     return FD_X;
 619 }
 620
 621 /*!
 622   \return line list
 623   \param theIndex - index in list
 624   \param tehFD - dimension
 625 */
 626 GLViewer_LineList* GLViewer_LineField::getLine( int theIndex, FieldDim theFD )
 627 {
 628   if( !myXLineArray || !myYLineArray )
 629     return NULL;
 630
 631   if( theFD == FD_X )
 632   {
 633     if( theIndex > myXSize )
 634       return NULL;
 635
 636     return myXLineArray[theIndex];
 637   }
 638   else if( theFD == FD_Y )
 639   {
 640     if( theIndex > myYSize )
 641       return NULL;
 642
 643     return myYLineArray[theIndex];
 644   }
 645
 646   return NULL;
 647 }
 648
 649 /*!
 650   Sets borders of field
 651   \param X1, X2 - minimal and maximal abscisses
 652   \param Y1, Y2 - minimal and maximal ordinates
 653 */
 654 void GLViewer_LineField::setBorders( double X1, double X2, double Y1, double Y2 )
 655 {
 656   if( !myXLineArray || !myYLineArray )
 657     return;
 658
 659   for( int i = 0; i < myXSize; i++ )
 660   {
 661     myXLineArray[i]->clear();
 662     myXLineArray[i]->addSegment( X1, X2 );
 663     myXLineArray[i]->setMainCoord( Y1 + (Y2-Y1)*(double(i)/(myXSize-1)) );
 664   }
 665
 666   for( int j = 0; j < myYSize; j++ )
 667   {
 668     myYLineArray[j]->clear();
 669     myYLineArray[j]->addSegment( Y1, Y2 );
 670     myYLineArray[j]->setMainCoord( X1 + (X2-X1)*(double(j)/(myYSize-1)) );
 671   }
 672 }
 673
 674 /*!
 675   Adds rectangle
 676   \param top, right - a corner of rectangle
 677   \param bottom, left - other corner of rectangle
 678 */
 679 void GLViewer_LineField::addRectangle( double top, double right, double bottom, double left )
 680 {
 681   if( !myXLineArray || !myYLineArray )
 682     return;
 683   for( int i = 0; i < myXSize; i++ )
 684   {
 685     double mainCoord = myXLineArray[i]->mainCoord();
 686     if( mainCoord < top && mainCoord > bottom )
 687       myXLineArray[i]->removeSegment( left, right );
 688   }
 689
 690   for( int j = 0; j < myYSize; j++ )
 691   {
 692     double mainCoord = myYLineArray[j]->mainCoord();
 693     if( mainCoord < right && mainCoord > left )
 694       myYLineArray[j]->removeSegment( bottom, top );
 695   }
 696 }
 697
 698 /*!
 699   Prints debug info about line field
 700 */
 701 void GLViewer_LineField::print()
 702 {
 703   std::cout << "My X matrix Number: " << myXSize << std::endl;
 704   for( int i = 0; i < myXSize; i++ )
 705     myXLineArray[i]->print();
 706
 707   std::cout << "My Y matrix Number: " << myYSize << std::endl;
 708   for( int j = 0; j < myYSize; j++ )
 709     myYLineArray[j]->print();
 710 }
 711
 712 /*!
 713   Draws field with help of OpenGL
 714 */
 715 void GLViewer_LineField::show()
 716 {
 717   for( int i = 0; i < myXSize; i++ )
 718     getLine( i, FD_X )->show( FD_X );
 719
 720   for( int j = 0; j < myYSize; j++ )
 721     getLine( j, FD_Y )->show( FD_Y );
 722   int count = 0;
 723   double* anArray = solution( count );
 724   glColor3f( 1.0, 0.0, 0.0 );
 725   glBegin( GL_LINES );
 726   for( int k = 0; k < count; k++ )
 727   {
 728      glVertex2d( anArray[4*k], anArray[4*k+1] );
 729      glVertex2d( anArray[4*k+2], anArray[4*k+3] );
 730   }
 731   glEnd();
 732   delete[] anArray;
 733   std::cout << "Show function" << std::endl;
 734 }
 735
 736 /*!
 737   \return size
 738   \param theDim - dimension
 739 */
 740 int GLViewer_LineField::getDimSize( FieldDim theDim )
 741 {
 742   if( theDim == FD_X )
 743     return myXSize;
 744   else if( theDim == FD_Y )
 745     return myYSize;
 746
 747   return -1;
 748 }
 749
 750 /*!
 751   \return array of intersected indexes
 752   \param theDim - dimension
 753   \param theIndex - index
 754   \param theLL - line with that intersection is checked
 755   \param theSize - to return value of array size
 756 */
 757 int* GLViewer_LineField::intersectIndexes( FieldDim theDim, int theIndex, const GLViewer_LineList* theLL, int& theSize )
 758 {
 759   theSize = 0;
 760   if( !myXLineArray || !myYLineArray )
 761     return NULL;
 762
 763   int aDimSize = getDimSize( theDim );
 764   int* anArray = new int[aDimSize*2 ];
 765
 766   for( int i = 0; i < aDimSize; i++ )
 767   {
 768     GLViewer_LineList* aLL = getLine( i, theDim );
 769     int index = aLL->contains( theLL->mainCoord() );
 770     if( index != -1 && theLL->contains( aLL->mainCoord() ) == theIndex )
 771     {
 772       anArray[theSize*2] = i;
 773       anArray[theSize*2+1] = index;
 774       theSize++;
 775     }
 776   }
 777
 778   return anArray;
 779 }
 780
 781 /*!
 782   Sets start/end search point
 783   \param thePoint - type of point (start: FP_Start; end: FP_End )
 784   \param theX, theY - point co-ordinates
 785 */
 786 bool GLViewer_LineField::setPoint( FieldPoint thePoint, double theX, double theY )
 787 {
 788   if( !myXLineArray || !myYLineArray )
 789     return false;
 790
 791   int i = -1, j = -1;
 792   int xSeg = -1, ySeg = -1;
 793   for( i = 0; i < myXSize; i++ )
 794   {
 795     GLViewer_LineList* aLL = getLine( i, FD_X );
 796     if( aLL->mainCoord() == theY )
 797     {
 798       xSeg = aLL->contains( theX );
 799       break;
 800     }
 801   }
 802
 803   for( j = 0; j < myYSize; j++ )
 804   {
 805     GLViewer_LineList* aLL = getLine( j, FD_Y );
 806     if( aLL->mainCoord() == theX )
 807     {
 808       ySeg = aLL->contains( theY );
 809       break;
 810     }
 811   }
 812
 813   if( xSeg != -1 && ySeg != -1 )
 814   {
 815     if( thePoint == FP_Start )
 816     {
 817       myStartPoint.myXLineIndex = i;
 818       myStartPoint.myXSegmentIndex = xSeg;
 819       myStartPoint.myYLineIndex = j;
 820       myStartPoint.myYSegmentIndex = ySeg;
 821       myStartPoint.mySolveIndex = -1;
 822     }
 823     else
 824     {
 825       myEndPoint.myXLineIndex = i;
 826       myEndPoint.myXSegmentIndex = xSeg;
 827       myEndPoint.myYLineIndex = j;
 828       myEndPoint.myYSegmentIndex = ySeg;
 829       myEndPoint.mySolveIndex = -1;
 830     }
 831     return true;
 832   }
 833   else
 834     return false;
 835 }
 836
 837 /*!
 838   \return number of segments
 839 */
 840 int GLViewer_LineField::segmentNumber()
 841 {
 842   if( !(myXLineArray || myYLineArray) )
 843     return -1;
 844
 845   int aNumber = 0;
 846   for( int aDim = 0; aDim < 2; aDim++ )
 847     for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
 848       aNumber += getLine( i, (FieldDim)aDim  )->count();
 849
 850   return aNumber;
 851 }
 852
 853 /*!
 854   Removes all multiple segments
 855 */
 856 void GLViewer_LineField::optimize()
 857 {
 858   if( !myXLineArray || !myYLineArray )
 859     return;
 860
 861   for( int aDim = 0; aDim < 2; aDim++ )
 862   {
 863     for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
 864     {
 865       GLViewer_LineList* aLL = getLine( i, (FieldDim)aDim  );
 866       for( int k =0, aSegNum = aLL->count(); k < aSegNum; k++ )
 867       {
 868         // int index = i; unused
 869         double a1, a2;
 870         aLL->readSegment( k, a1, a2 );
 871         for( int l = i+1, m = getDimSize( (FieldDim)aDim ); l < m; l++ )
 872         {
 873           int end = -1;
 874           GLViewer_LineList* aCurLL = getLine( l, (FieldDim)aDim );
 875           for( int j = 0, count = aCurLL->count(); j < count; j++  )
 876           {
 877             double c1, c2;
 878             aCurLL->readSegment( j, c1, c2 );
 879             if( a1 == c1 && a2 == c2 )
 880             {
 881               if( !(aDim == 0 && myStartPoint.myXLineIndex == l && myStartPoint.myXSegmentIndex == j) &&
 882                   !(aDim == 0 && myEndPoint.myXLineIndex == l && myEndPoint.myXSegmentIndex == j) &&
 883                   !(aDim == 1 && myStartPoint.myYLineIndex == l && myStartPoint.myYSegmentIndex == j) &&
 884                   !(aDim == 1 && myEndPoint.myYLineIndex == l && myEndPoint.myYSegmentIndex == j) )
 885                 aCurLL->removeSegment( j );
 886               end = 0;
 887               break;
 888             }
 889             if( a1 < c1 )
 890             {
 891               end = 1;
 892               break;
 893             }
 894           }
 895           if( end == -1 || end == 1)
 896               break;
 897         }
 898       }
 899     }
 900   }
 901 }
 902
 903 /*!
 904   Some prepare actions
 905   Needs call setPoint before
 906 */
 907 void GLViewer_LineField::initialize()
 908 {
 909   if( !myXLineArray || !myYLineArray )
 910     return;
 911
 912   int size = segmentNumber();
 913
 914   myCurArrayIndex = 0;
 915   myCurCount = 0;
 916
 917   myGraphArray1 = new GraphNode[size];
 918   myGraphArray2 = new GraphNode[size];
 919
 920   int index = 0;
 921   bool isXSet = false,
 922        isYSet = false;
 923   for( int aDim = 0; aDim < 2; aDim++ )
 924   {
 925     for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
 926     {
 927       GLViewer_LineList* aLL = getLine( i, (FieldDim)aDim  );
 928       for( int k =0, aSegNum = aLL->count(); k < aSegNum; k++ )
 929       {
 930         myGraphArray1[index].myCount = size;
 931         myGraphArray1[index].myDim = (FieldDim)aDim;
 932         myGraphArray1[index].myLineIndex = i;
 933         myGraphArray1[index].mySegmentindex = k;
 934         myGraphArray1[index].prevNodeIndex = -1;
 935
 936         myGraphArray2[index].myCount = size;
 937         myGraphArray2[index].myDim = (FieldDim)aDim;
 938         myGraphArray2[index].myLineIndex = i;
 939         myGraphArray2[index].mySegmentindex = k;
 940         myGraphArray2[index].prevNodeIndex = -1;
 941
 942         if( !isXSet && aDim == FD_X && myStartPoint.myXLineIndex == i && myStartPoint.myXSegmentIndex == k )
 943         {
 944           myGraphArray1[index].myCount = 0;
 945           isXSet = true;
 946         }
 947
 948         if( aDim == FD_Y && !isYSet && myStartPoint.myYLineIndex == i && myStartPoint.myYSegmentIndex == k )
 949         {
 950           myGraphArray1[index].myCount = 0;
 951           isYSet = true;
 952         }
 953
 954         index++;
 955       }
 956     }
 957   }
 958 }
 959
 960 /*!
 961   One iteration of algorithm
 962 */
 963 void GLViewer_LineField::iteration()
 964 {
 965   int aParam = myCurCount;
 966   myCurCount++;
 967
 968   int* aNodes = findByCount( aParam );
 969   GraphNode* aCurArray = getCurArray();
 970
 971   for( int i = 0; i < aParam; i++ )
 972   {
 973     GraphNode aCurNode = aCurArray[aNodes[i]];
 974     int aSize = 0;
 975     int* aInterNodes = intersectIndexes( invertDim( aCurNode.myDim ), aCurNode.mySegmentindex,
 976                                          getLine( aCurNode.myLineIndex, aCurNode.myDim ), aSize );
 977     for( int j = 0; j < aSize; j++ )
 978     {
 979       int index = findBySegment( invertDim( aCurNode.myDim ), aInterNodes[2*j], aInterNodes[2*j+1], false );
 980       if( index != -1 )
 981         if( aCurArray[index].myCount > myCurCount )
 982         {
 983           aCurArray[index].myCount = myCurCount;
 984           aCurArray[index].prevNodeIndex = aNodes[i];
 985         }
 986     }
 987
 988     delete[] aInterNodes;
 989   }
 990
 991   delete[] aNodes;
 992 }
 993
 994 /*!
 995   Checks for complete status
 996 */
 997 GLViewer_LineField::IterationStatus GLViewer_LineField::checkComplete()
 998 {
 999   if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
1000     return IS_ERROR;
1001
1002   int count = 0;
1003   GraphNode* aCurArray = getCurArray(),
1004            * aSecArray = getSecArray();
1005
1006   for( int i = 0, n = segmentNumber(); i < n; i++ )
1007   {
1008     if( aCurArray[i].myCount != aSecArray[i].myCount )
1009     {
1010       if( aCurArray[i].myDim == FD_X &&
1011           aCurArray[i].myLineIndex == myEndPoint.myXLineIndex &&
1012           aCurArray[i].mySegmentindex == myEndPoint.myXSegmentIndex )
1013       {
1014         std::cout << "Algorithm complete X!!!!!!!" << std::endl;
1015         myEndPoint.mySolveIndex = i;
1016         return IS_SOLVED;
1017       }
1018       else if( aCurArray[i].myDim == FD_Y &&
1019                aCurArray[i].myLineIndex == myEndPoint.myYLineIndex &&
1020                aCurArray[i].mySegmentindex == myEndPoint.myYSegmentIndex )
1021       {
1022         std::cout << "Algorithm complete Y!!!!!!!" << std::endl;
1023         myEndPoint.mySolveIndex = i;
1024         return IS_SOLVED;
1025       }
1026       else
1027       {
1028         count++;
1029         aSecArray[i].myCount = aCurArray[i].myCount;
1030         aSecArray[i].prevNodeIndex = aCurArray[i].prevNodeIndex;
1031       }
1032     }
1033   }
1034
1035   if( myCurArrayIndex == 0)
1036     myCurArrayIndex = 1;
1037   else
1038     myCurArrayIndex = 0;
1039
1040   std::cout << "Number of ways: " << count << std::endl;
1041   if( count == 0 )
1042     return IS_LOOP;
1043
1044   return IS_NOT_SOLVED;
1045 }
1046
1047 /*!
1048   Finds LineList by counts and returns indexes
1049 */
1050 int* GLViewer_LineField::findByCount( int& theParam )
1051 {
1052   if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
1053     return NULL;
1054
1055   int count = segmentNumber();
1056   int* anArray = new int[count];
1057   int aSize = 0;
1058
1059   GraphNode* aCurArray = getCurArray();
1060   for( int i = 0; i < count; i++ )
1061   {
1062     GraphNode aCurNode = aCurArray[i];
1063     if( aCurNode.myCount == theParam )
1064     {
1065       anArray[aSize] = i;
1066       aSize++;
1067     }
1068   }
1069
1070   theParam = aSize;
1071   return anArray;
1072 }
1073
1074 /*!
1075   Finds LineList by segment and dimension
1076 */
1077 int GLViewer_LineField::findBySegment( FieldDim theDim, int theLineIndex, int theSegment, bool inCurArray )
1078 {
1079   if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 || getDimSize( theDim ) <= theLineIndex )
1080     return -1;
1081
1082   GraphNode* aCurArray;
1083   if( inCurArray )
1084     aCurArray = getCurArray();
1085   else
1086     aCurArray = getSecArray();
1087
1088   for( int i = 0, n = segmentNumber(); i < n; i++ )
1089   {
1090     GraphNode aCurNode = aCurArray[i];
1091     if( aCurNode.myDim == theDim && aCurNode.myLineIndex == theLineIndex && aCurNode.mySegmentindex == theSegment )
1092       return i;
1093   }
1094
1095   return -1;
1096 }
1097
1098 /*!
1099   Main method, performs algorithm execution
1100 */
1101 GLViewer_LineField::EndStatus GLViewer_LineField::startAlgorithm()
1102 {
1103   if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
1104     return ES_ERROR;
1105
1106   while( true )
1107   {
1108     std::cout << "-----------Iteration #" << myCurCount << "-------------" << std::endl;
1109     iteration();
1110
1111     IterationStatus is = checkComplete();
1112     if( is == IS_ERROR )
1113       return ES_ERROR;
1114     else if( is == IS_LOOP )
1115       return ES_LOOP;
1116     else if( is == IS_SOLVED )
1117       return ES_SOLVED;
1118   }
1119   return ES_SOLVED;
1120 }
1121
1122 /*!
1123   \return solution and size of solution
1124 */
1125 double* GLViewer_LineField::solution( int& theSize )
1126 {
1127   if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
1128     return NULL;
1129
1130   if( myEndPoint.mySolveIndex == -1 )
1131     return NULL;
1132
1133   theSize = myCurCount+1;
1134   double* anArray = new double[theSize*4];
1135
1136   GraphNode* aCurArray = getCurArray();
1137
1138   int index = myEndPoint.mySolveIndex;
1139   for( int i = 0; i <= myCurCount; i++  )
1140   {
1141     if( index == -1 )
1142       break;
1143     double c1, c2;
1144     GLViewer_LineList* aLL = getLine( aCurArray[index].myLineIndex, aCurArray[index].myDim );
1145     aLL->readSegment( aCurArray[index].mySegmentindex, c1, c2 );
1146
1147     if( aCurArray[index].myDim == FD_X )
1148     {
1149       anArray[i*4] = c1;
1150       anArray[i*4+1] = aLL->mainCoord();
1151       anArray[i*4+2] = c2;
1152       anArray[i*4+3] = aLL->mainCoord();
1153     }
1154     else
1155     {
1156       anArray[i*4] = aLL->mainCoord();
1157       anArray[i*4+1] = c1;
1158       anArray[i*4+2] = aLL->mainCoord();
1159       anArray[i*4+3] = c2;
1160     }
1161
1162     index = aCurArray[index].prevNodeIndex;
1163   }
1164
1165   return anArray;
1166 }
1167
1168 /*!
1169   \return current solution array
1170 */
1171 GraphNode* GLViewer_LineField::getCurArray()
1172 {
1173   if( !myGraphArray1 || !myGraphArray2 )
1174     return NULL;
1175
1176   if( myCurArrayIndex == 0)
1177     return myGraphArray1;
1178   else
1179     return myGraphArray2;
1180 }
1181
1182 /*!
1183   \return other solution array
1184 */
1185 GraphNode* GLViewer_LineField::getSecArray()
1186 {
1187   if( !myGraphArray1 || !myGraphArray2 )
1188     return NULL;
1189
1190   if( myCurArrayIndex == 0)
1191     return myGraphArray2;
1192   else
1193     return myGraphArray1;
1194 }
1195
1196 /*!
1197   \return maximum segment number
1198 */
1199 int GLViewer_LineField::maxSegmentNum()
1200 {
1201   if( !myXLineArray || !myYLineArray )
1202     return -1;
1203
1204   int max_num = -1;
1205   for( int aDim = 0; aDim < 2; aDim++ )
1206   {
1207     for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
1208     {
1209       int count = getLine( i, (FieldDim)aDim  )->count();
1210       if( count > max_num )
1211         max_num = count;
1212     }
1213   }
1214
1215   return max_num;
1216 }
1217
1218 /*!
1219   \return list of LileList by dimension
1220   \param theDim - dimension
1221 */
1222 GLViewer_LineList** GLViewer_LineField::getLLArray( FieldDim theDim )
1223 {
1224   if( theDim == FD_X )
1225     return myXLineArray;
1226   else if( theDim == FD_Y )
1227     return myYLineArray;
1228   else
1229     return NULL;
1230 }