1 // File: GLViewer_Tools.cxx
2 // Created: April, 2005
5 //#include "GLViewerAfx.h"
6 #include "GLViewer_Tools.h"
14 /****************************************************************************
15 ** Class: GLViewer_LineList
16 ** Descr: Tools for distinct line
18 ** Created: UI team, 27.10.05
19 *****************************************************************************/
20 GLViewer_LineList::GLViewer_LineList( int size )
26 myArray = new double[myRealSize];
30 cout << "Can't allocate memory: " << size << endl;
34 memset( myArray, 0, myRealSize*sizeof(double) );
37 GLViewer_LineList::~GLViewer_LineList()
42 bool GLViewer_LineList::addSegment( double coord1, double coord2 )
51 if( 2*mySegmentNumber == myRealSize || !myArray )
56 while( index < mySegmentNumber)
58 readSegment( index, c1, c2 );
59 if( coord1 < c1 && coord2 < c1 )
61 for( int i = mySegmentNumber; i > index - 1; i--)
63 myArray[2*i] = myArray[2*i-2]; //2*(i-1)
64 myArray[2*i+1] = myArray[2*i-1];//2*(i-1)+1
68 // mySegmentNumber; what is means ?
71 else if( coord1 < c1 && coord2 < c2 )
73 myArray[index*2] = coord1;
76 else if( c1 < coord1 && coord2 < c2 )
80 else if( coord1 < c2 && c2 < coord2 )
83 myArray[2*index] = coord1;
85 if( index != mySegmentNumber - 1 )
87 for( int i = index+1; i < mySegmentNumber; i++ )
89 if( coord2 < myArray[2*i] )
91 myArray[2*index+1] = coord2;
94 for( int j = 0; i+j < mySegmentNumber;j++ )
96 myArray[2*(index+1+j)] = myArray[2*(i+j)];
97 myArray[2*(index+1+j)+1] = myArray[2*(i+j)+1];
99 for( int k = 0; k < mySegmentNumber - i; k++ )
101 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
102 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
104 mySegmentNumber -= i - index-1;
108 else if( coord2 < myArray[2*i+1] )
110 myArray[2*index+1] = myArray[2*i+1];
112 for( int j = index+1; j < mySegmentNumber-1;j++ )
114 myArray[2*j] = myArray[2*(i+j-index)];
115 myArray[2*j+1] = myArray[2*(i+j-index)+1];
117 for( int k = 0; k < mySegmentNumber - i-1; k++ )
119 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
120 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
122 mySegmentNumber -= i - index;
129 myArray[2*index+1] = coord2;
136 myArray[mySegmentNumber*2] = coord1;
137 myArray[mySegmentNumber*2+1] = coord2;
143 bool GLViewer_LineList::readSegment( int theIndex, double& coord1, double& coord2 )
145 if( theIndex > mySegmentNumber || !myArray)
148 coord1 = myArray[theIndex*2];
149 coord2 = myArray[theIndex*2+1];
154 int GLViewer_LineList::contains( double thePoint ) const
156 if( !myArray || mySegmentNumber == 0 )
159 for( int i = 0; i < mySegmentNumber; i++ )
160 if( myArray[2*i] <= thePoint && thePoint <= myArray[2*i+1] )
167 bool GLViewer_LineList::removeSegment( int theIndex )
169 if( theIndex > mySegmentNumber || !myArray)
172 for( int i = theIndex; i < mySegmentNumber; i++ )
174 myArray[i*2] = myArray[(i+1)*2];
175 myArray[i*2+1] = myArray[(i+1)*2+1];
178 myArray[mySegmentNumber*2] = 0.0;
179 myArray[mySegmentNumber*2+1] = 0.0;
183 bool GLViewer_LineList::removeSegment( double coord1, double coord2 )
185 if( coord1 > coord2 )
187 double temp = coord1;
192 if( 2*mySegmentNumber == myRealSize || !myArray )
197 while( index < mySegmentNumber)
199 readSegment( index, c1, c2 );
200 if( coord1 < c1 && coord2 < c1 )
205 else if( coord1 < c1 && coord2 < c2 )
207 myArray[index*2] = coord2;
210 else if( c1 < coord1 && coord2 < c2 )
212 if( 2*mySegmentNumber == myRealSize )
214 for( int i = mySegmentNumber; i > index + 1; i-- )
216 myArray[2*i] = myArray[2*(i-1)];
217 myArray[2*i+1] = myArray[2*(i-1)+1];
219 myArray[2*(index+1)+1] = myArray[2*index+1];
220 myArray[2*(index+1)] = coord2;
221 myArray[2*index+1] = coord1;
225 else if( coord1 < c2 && c2 < coord2 )
229 myArray[2*index+1] = coord1;
232 if( index != mySegmentNumber - 1 )
234 for( int i = index+1; i < mySegmentNumber; i++ )
236 if( coord2 < myArray[2*i] )
240 for( int j = 1; i+j-1 < mySegmentNumber;j++ )
242 myArray[2*(index+j)] = myArray[2*(i+j-1)];
243 myArray[2*(index+j)+1] = myArray[2*(i+j-1)+1];
245 for( int k = 0; k < mySegmentNumber - i; k++ )
247 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
248 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
250 mySegmentNumber -= i - index -1;
256 for( int j = 0; index + j + 1 < mySegmentNumber;j++ )
258 myArray[2*(index+j)] = myArray[2*(index+j+1)];
259 myArray[2*(index+j)+1] = myArray[2*(index+j+1)+1];
262 myArray[2*(mySegmentNumber - 1)] = 0.0;
263 myArray[2*(mySegmentNumber - 1)+1] = 0.0;
273 else if( coord2 < myArray[2*i+1] )
280 myArray[2*index] = coord2;
281 myArray[2*index+1] = myArray[2*i+1];
283 for( int j = 1; i+j < mySegmentNumber;j++ )
285 myArray[2*(index+j)] = myArray[2*(i+j)];
286 myArray[2*(index+j)+1] = myArray[2*(i+j)+1];
288 for( int k = 0; k < mySegmentNumber - i - 1; k++ )
290 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
291 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
293 mySegmentNumber -= i - index;
299 myArray[2*(index+1)] = coord2;
304 myArray[2*(index)] = coord2;
305 myArray[2*(index)+1] = myArray[2*(index+1)+1];
306 for( int j = index+1; j < mySegmentNumber-1; j++ )
308 myArray[2*j] = myArray[2*(j+1)];
309 myArray[2*j+1] = myArray[2*(j+1)+1];
312 myArray[2*mySegmentNumber] = 0.0;
313 myArray[2*mySegmentNumber+1] = 0.0;
325 myArray[2*index] = 0.0;
326 myArray[2*index+1] = 0.0;
335 void GLViewer_LineList::clear()
338 memset( myArray, 0, myRealSize*sizeof(double) );
341 void GLViewer_LineList::print()
343 cout << "MainCoord: " << myMainCoord <<" SIZE: " << myRealSize << " ENum: " << mySegmentNumber << " :::";
344 for( int i = 0; i < mySegmentNumber; i++ )
345 cout << " " << myArray[2*i] << " " << myArray[2*i+1] << " | ";
350 void GLViewer_LineList::show( FieldDim theDim )
355 glColor3f( 1.0, 0.0, 1.0 );
359 for( int i = 0; i < mySegmentNumber; i++ )
361 glVertex2d( myArray[2*i], myMainCoord );
362 glVertex2d( myArray[2*i+1], myMainCoord );
366 else if( theDim == FD_Y )
369 for( int i = 0; i < mySegmentNumber; i++ )
371 glVertex2d( myMainCoord, myArray[2*i] );
372 glVertex2d( myMainCoord, myArray[2*i+1] );
378 /****************************************************************************
379 ** Class: GLViewer_LineField
380 ** Descr: Tools for solving
382 ** Created: UI team, 27.10.05
383 *****************************************************************************/
384 GLViewer_LineField::GLViewer_LineField()
387 myGraphArray1 = NULL;
388 myGraphArray2 = NULL;
397 GLViewer_LineField::GLViewer_LineField( const int theMAXSize, const int theXN, const int theYN )
400 myGraphArray1 = NULL;
401 myGraphArray2 = NULL;
405 if( theXN <= 0 || theYN <= 0 )
414 myXLineArray = new GLViewer_LineList*[theXN];
415 myYLineArray = new GLViewer_LineList*[theYN];
417 for( int i = 0; i < theXN; i++ )
418 myXLineArray[i] = new GLViewer_LineList( theMAXSize );
420 for( int j = 0; j < theYN; j++ )
421 myYLineArray[j] = new GLViewer_LineList( theMAXSize );
428 GLViewer_LineField::~GLViewer_LineField()
432 for( int i = 0; i < myXSize; i++ )
433 delete myXLineArray[i];
440 for( int j = 0; j < myYSize; j++ )
441 delete myYLineArray[j];
447 delete myGraphArray1;
450 delete myGraphArray2;
453 void GLViewer_LineField::addLine( FieldDim theDim, GLViewer_LineList* )
458 void GLViewer_LineField:: addLine( FieldDim theDim, double theMC, double theBegin, double theEnd )
460 GLViewer_LineList* aLL = new GLViewer_LineList( 1 );
461 aLL->addSegment( theBegin, theEnd );
462 aLL->setMainCoord( theMC );
463 addLine( theDim, aLL );
467 int GLViewer_LineField::insertLine( FieldDim theDim, GLViewer_LineList* theLL, int thePosition )
469 if( !myXLineArray || !myYLineArray )
472 GLViewer_LineList** anArray = getLLArray( theDim );
476 int size = getDimSize( theDim );
478 if( thePosition >= size )
480 else if( thePosition < 0 )
482 if( anArray[size-1]->count() != 0 ) // no more space
485 for( int i = 0; i < size; i++ )
487 if( anArray[i]->count() == 0 )
494 double cur_mc = anArray[i]->mainCoord();
495 if( theLL->mainCoord() < cur_mc )
497 for( int j = 0; j+i+1 < size; j++ )
499 delete anArray[size-j-1];
500 anArray[size-j-1] = anArray[size-j-2];
510 delete anArray[thePosition];
511 anArray[thePosition] = theLL;
518 int GLViewer_LineField::insertLine( FieldDim theDim, double theMainCoord, double theBegin, double theEnd, int thePosition )
520 GLViewer_LineList* aLL = new GLViewer_LineList( 1 );
521 aLL->addSegment( theBegin, theEnd );
522 aLL->setMainCoord( theMainCoord );
523 return insertLine( theDim, aLL, thePosition );
527 FieldDim GLViewer_LineField::invertDim( FieldDim theFD )
535 GLViewer_LineList* GLViewer_LineField::getLine( int theIndex, FieldDim theFD )
537 if( !myXLineArray || !myYLineArray )
542 if( theIndex > myXSize )
545 return myXLineArray[theIndex];
547 else if( theFD == FD_Y )
549 if( theIndex > myYSize )
552 return myYLineArray[theIndex];
558 void GLViewer_LineField::setBorders( double X1, double X2, double Y1, double Y2 )
560 if( !myXLineArray || !myYLineArray )
563 for( int i = 0; i < myXSize; i++ )
565 myXLineArray[i]->clear();
566 myXLineArray[i]->addSegment( X1, X2 );
567 myXLineArray[i]->setMainCoord( Y1 + (Y2-Y1)*(double(i)/(myXSize-1)) );
570 for( int j = 0; j < myYSize; j++ )
572 myYLineArray[j]->clear();
573 myYLineArray[j]->addSegment( Y1, Y2 );
574 myYLineArray[j]->setMainCoord( X1 + (X2-X1)*(double(j)/(myYSize-1)) );
578 void GLViewer_LineField::addRectangle( double top, double right, double bottom, double left )
580 if( !myXLineArray || !myYLineArray )
582 for( int i = 0; i < myXSize; i++ )
584 double mainCoord = myXLineArray[i]->mainCoord();
585 if( mainCoord < top && mainCoord > bottom )
586 myXLineArray[i]->removeSegment( left, right );
589 for( int j = 0; j < myYSize; j++ )
591 double mainCoord = myYLineArray[j]->mainCoord();
592 if( mainCoord < right && mainCoord > left )
593 myYLineArray[j]->removeSegment( bottom, top );
597 void GLViewer_LineField::print()
599 cout << "My X matrix Number: " << myXSize << endl;
600 for( int i = 0; i < myXSize; i++ )
601 myXLineArray[i]->print();
603 cout << "My Y matrix Number: " << myYSize << endl;
604 for( int j = 0; j < myYSize; j++ )
605 myYLineArray[j]->print();
608 void GLViewer_LineField::show()
610 for( int i = 0; i < myXSize; i++ )
611 getLine( i, FD_X )->show( FD_X );
613 for( int j = 0; j < myYSize; j++ )
614 getLine( j, FD_Y )->show( FD_Y );
616 double* anArray = solution( count );
617 glColor3f( 1.0, 0.0, 0.0 );
619 for( int k = 0; k < count; k++ )
621 glVertex2d( anArray[4*k], anArray[4*k+1] );
622 glVertex2d( anArray[4*k+2], anArray[4*k+3] );
626 cout << "Show function" << endl;
629 int GLViewer_LineField::getDimSize( FieldDim theDim )
633 else if( theDim == FD_Y )
639 int* GLViewer_LineField::intersectIndexes( FieldDim theDim, int theIndex, const GLViewer_LineList* theLL, int& theSize )
642 if( !myXLineArray || !myYLineArray )
645 int aDimSize = getDimSize( theDim );
646 int* anArray = new int[aDimSize*2 ];
648 for( int i = 0; i < aDimSize; i++ )
650 GLViewer_LineList* aLL = getLine( i, theDim );
651 int index = aLL->contains( theLL->mainCoord() );
652 if( index != -1 && theLL->contains( aLL->mainCoord() ) == theIndex )
654 anArray[theSize*2] = i;
655 anArray[theSize*2+1] = index;
664 bool GLViewer_LineField::setPoint( FieldPoint thePoint, double theX, double theY )
666 if( !myXLineArray || !myYLineArray )
670 int xSeg = -1, ySeg = -1;
671 for( i = 0; i < myXSize; i++ )
673 GLViewer_LineList* aLL = getLine( i, FD_X );
674 if( aLL->mainCoord() == theY )
676 xSeg = aLL->contains( theX );
681 for( j = 0; j < myYSize; j++ )
683 GLViewer_LineList* aLL = getLine( j, FD_Y );
684 if( aLL->mainCoord() == theX )
686 ySeg = aLL->contains( theY );
691 if( xSeg != -1 && ySeg != -1 )
693 if( thePoint == FP_Start )
695 myStartPoint.myXLineIndex = i;
696 myStartPoint.myXSegmentIndex = xSeg;
697 myStartPoint.myYLineIndex = j;
698 myStartPoint.myYSegmentIndex = ySeg;
699 myStartPoint.mySolveIndex = -1;
703 myEndPoint.myXLineIndex = i;
704 myEndPoint.myXSegmentIndex = xSeg;
705 myEndPoint.myYLineIndex = j;
706 myEndPoint.myYSegmentIndex = ySeg;
707 myEndPoint.mySolveIndex = -1;
715 int GLViewer_LineField::segmentNumber()
717 if( !(myXLineArray || myYLineArray) )
721 for( int aDim = 0; aDim < 2; aDim++ )
722 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
723 aNumber += getLine( i, (FieldDim)aDim )->count();
728 void GLViewer_LineField::optimize()
730 if( !myXLineArray || !myYLineArray )
733 for( int aDim = 0; aDim < 2; aDim++ )
735 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
737 GLViewer_LineList* aLL = getLine( i, (FieldDim)aDim );
738 for( int k =0, aSegNum = aLL->count(); k < aSegNum; k++ )
740 // int index = i; unused
742 aLL->readSegment( k, a1, a2 );
743 for( int l = i+1, m = getDimSize( (FieldDim)aDim ); l < m; l++ )
746 GLViewer_LineList* aCurLL = getLine( l, (FieldDim)aDim );
747 for( int j = 0, count = aCurLL->count(); j < count; j++ )
750 aCurLL->readSegment( j, c1, c2 );
751 if( a1 == c1 && a2 == c2 )
753 if( !(aDim == 0 && myStartPoint.myXLineIndex == l && myStartPoint.myXSegmentIndex == j) &&
754 !(aDim == 0 && myEndPoint.myXLineIndex == l && myEndPoint.myXSegmentIndex == j) &&
755 !(aDim == 1 && myStartPoint.myYLineIndex == l && myStartPoint.myYSegmentIndex == j) &&
756 !(aDim == 1 && myEndPoint.myYLineIndex == l && myEndPoint.myYSegmentIndex == j) )
757 aCurLL->removeSegment( j );
767 if( end == -1 || end == 1)
775 void GLViewer_LineField::initialize()
777 if( !myXLineArray || !myYLineArray )
780 int size = segmentNumber();
785 myGraphArray1 = new GraphNode[size];
786 myGraphArray2 = new GraphNode[size];
791 for( int aDim = 0; aDim < 2; aDim++ )
793 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
795 GLViewer_LineList* aLL = getLine( i, (FieldDim)aDim );
796 for( int k =0, aSegNum = aLL->count(); k < aSegNum; k++ )
798 myGraphArray1[index].myCount = size;
799 myGraphArray1[index].myDim = (FieldDim)aDim;
800 myGraphArray1[index].myLineIndex = i;
801 myGraphArray1[index].mySegmentindex = k;
802 myGraphArray1[index].prevNodeIndex = -1;
804 myGraphArray2[index].myCount = size;
805 myGraphArray2[index].myDim = (FieldDim)aDim;
806 myGraphArray2[index].myLineIndex = i;
807 myGraphArray2[index].mySegmentindex = k;
808 myGraphArray2[index].prevNodeIndex = -1;
810 if( !isXSet && aDim == FD_X && myStartPoint.myXLineIndex == i && myStartPoint.myXSegmentIndex == k )
812 myGraphArray1[index].myCount = 0;
816 if( aDim == FD_Y && !isYSet && myStartPoint.myYLineIndex == i && myStartPoint.myYSegmentIndex == k )
818 myGraphArray1[index].myCount = 0;
828 void GLViewer_LineField::iteration()
830 int aParam = myCurCount;
833 int* aNodes = findByCount( aParam );
834 GraphNode* aCurArray = getCurArray();
836 for( int i = 0; i < aParam; i++ )
838 GraphNode aCurNode = aCurArray[aNodes[i]];
840 int* aInterNodes = intersectIndexes( invertDim( aCurNode.myDim ), aCurNode.mySegmentindex,
841 getLine( aCurNode.myLineIndex, aCurNode.myDim ), aSize );
842 for( int j = 0; j < aSize; j++ )
844 int index = findBySegment( invertDim( aCurNode.myDim ), aInterNodes[2*j], aInterNodes[2*j+1], false );
846 if( aCurArray[index].myCount > myCurCount )
848 aCurArray[index].myCount = myCurCount;
849 aCurArray[index].prevNodeIndex = aNodes[i];
853 delete[] aInterNodes;
859 GLViewer_LineField::IterationStatus GLViewer_LineField::checkComplete()
861 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
865 GraphNode* aCurArray = getCurArray(),
866 * aSecArray = getSecArray();
868 for( int i = 0, n = segmentNumber(); i < n; i++ )
870 if( aCurArray[i].myCount != aSecArray[i].myCount )
872 if( aCurArray[i].myDim == FD_X &&
873 aCurArray[i].myLineIndex == myEndPoint.myXLineIndex &&
874 aCurArray[i].mySegmentindex == myEndPoint.myXSegmentIndex )
876 cout << "Algorithm complete X!!!!!!!" << endl;
877 myEndPoint.mySolveIndex = i;
880 else if( aCurArray[i].myDim == FD_Y &&
881 aCurArray[i].myLineIndex == myEndPoint.myYLineIndex &&
882 aCurArray[i].mySegmentindex == myEndPoint.myYSegmentIndex )
884 cout << "Algorithm complete Y!!!!!!!" << endl;
885 myEndPoint.mySolveIndex = i;
891 aSecArray[i].myCount = aCurArray[i].myCount;
892 aSecArray[i].prevNodeIndex = aCurArray[i].prevNodeIndex;
897 if( myCurArrayIndex == 0)
902 cout << "Number of ways: " << count << endl;
906 return IS_NOT_SOLVED;
909 int* GLViewer_LineField::findByCount( int& theParam )
911 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
914 int count = segmentNumber();
915 int* anArray = new int[count];
918 GraphNode* aCurArray = getCurArray();
919 for( int i = 0; i < count; i++ )
921 GraphNode aCurNode = aCurArray[i];
922 if( aCurNode.myCount == theParam )
933 int GLViewer_LineField::findBySegment( FieldDim theDim, int theLineIndex, int theSegment, bool inCurArray )
935 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 || getDimSize( theDim ) <= theLineIndex )
938 GraphNode* aCurArray;
940 aCurArray = getCurArray();
942 aCurArray = getSecArray();
944 for( int i = 0, n = segmentNumber(); i < n; i++ )
946 GraphNode aCurNode = aCurArray[i];
947 if( aCurNode.myDim == theDim && aCurNode.myLineIndex == theLineIndex && aCurNode.mySegmentindex == theSegment )
954 GLViewer_LineField::EndStatus GLViewer_LineField::startAlgorithm()
956 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
961 cout << "-----------Iteration #" << myCurCount << "-------------" << endl;
964 IterationStatus is = checkComplete();
967 else if( is == IS_LOOP )
969 else if( is == IS_SOLVED )
975 double* GLViewer_LineField::solution( int& theSize )
977 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
980 if( myEndPoint.mySolveIndex == -1 )
983 theSize = myCurCount+1;
984 double* anArray = new double[theSize*4];
986 GraphNode* aCurArray = getCurArray();
988 int index = myEndPoint.mySolveIndex;
989 for( int i = 0; i <= myCurCount; i++ )
994 GLViewer_LineList* aLL = getLine( aCurArray[index].myLineIndex, aCurArray[index].myDim );
995 aLL->readSegment( aCurArray[index].mySegmentindex, c1, c2 );
997 if( aCurArray[index].myDim == FD_X )
1000 anArray[i*4+1] = aLL->mainCoord();
1001 anArray[i*4+2] = c2;
1002 anArray[i*4+3] = aLL->mainCoord();
1006 anArray[i*4] = aLL->mainCoord();
1007 anArray[i*4+1] = c1;
1008 anArray[i*4+2] = aLL->mainCoord();
1009 anArray[i*4+3] = c2;
1012 index = aCurArray[index].prevNodeIndex;
1018 GraphNode* GLViewer_LineField::getCurArray()
1020 if( !myGraphArray1 || !myGraphArray2 )
1023 if( myCurArrayIndex == 0)
1024 return myGraphArray1;
1026 return myGraphArray2;
1029 GraphNode* GLViewer_LineField::getSecArray()
1031 if( !myGraphArray1 || !myGraphArray2 )
1034 if( myCurArrayIndex == 0)
1035 return myGraphArray2;
1037 return myGraphArray1;
1040 int GLViewer_LineField::maxSegmentNum()
1042 if( !myXLineArray || !myYLineArray )
1046 for( int aDim = 0; aDim < 2; aDim++ )
1048 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
1050 int count = getLine( i, (FieldDim)aDim )->count();
1051 if( count > max_num )
1059 GLViewer_LineList** GLViewer_LineField::getLLArray( FieldDim theDim )
1061 if( theDim == FD_X )
1062 return myXLineArray;
1063 else if( theDim == FD_Y )
1064 return myYLineArray;