1 // File: GLViewer_Tools.cxx
2 // Created: April, 2005
5 //#include "GLViewerAfx.h"
6 #include "GLViewer_Tools.h"
12 /****************************************************************************
13 ** Class: GLViewer_LineList
14 ** Descr: Tools for distinct line
16 ** Created: UI team, 27.10.05
17 *****************************************************************************/
18 GLViewer_LineList::GLViewer_LineList( int size )
24 myArray = new double[myRealSize];
28 cout << "Can't allocate memory: " << size << endl;
32 memset( myArray, 0, myRealSize*sizeof(double) );
35 GLViewer_LineList::~GLViewer_LineList()
40 bool GLViewer_LineList::addSegment( double coord1, double coord2 )
49 if( 2*mySegmentNumber == myRealSize || !myArray )
54 while( index < mySegmentNumber)
56 readSegment( index, c1, c2 );
57 if( coord1 < c1 && coord2 < c1 )
59 for( int i = mySegmentNumber; i > index - 1; i--)
61 myArray[2*i] = myArray[2*i-2]; //2*(i-1)
62 myArray[2*i+1] = myArray[2*i-1];//2*(i-1)+1
66 // mySegmentNumber; what is means ?
69 else if( coord1 < c1 && coord2 < c2 )
71 myArray[index*2] = coord1;
74 else if( c1 < coord1 && coord2 < c2 )
78 else if( coord1 < c2 && c2 < coord2 )
81 myArray[2*index] = coord1;
83 if( index != mySegmentNumber - 1 )
85 for( int i = index+1; i < mySegmentNumber; i++ )
87 if( coord2 < myArray[2*i] )
89 myArray[2*index+1] = coord2;
92 for( int j = 0; i+j < mySegmentNumber;j++ )
94 myArray[2*(index+1+j)] = myArray[2*(i+j)];
95 myArray[2*(index+1+j)+1] = myArray[2*(i+j)+1];
97 for( int k = 0; k < mySegmentNumber - i; k++ )
99 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
100 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
102 mySegmentNumber -= i - index-1;
106 else if( coord2 < myArray[2*i+1] )
108 myArray[2*index+1] = myArray[2*i+1];
110 for( int j = index+1; j < mySegmentNumber-1;j++ )
112 myArray[2*j] = myArray[2*(i+j-index)];
113 myArray[2*j+1] = myArray[2*(i+j-index)+1];
115 for( int k = 0; k < mySegmentNumber - i-1; k++ )
117 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
118 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
120 mySegmentNumber -= i - index;
127 myArray[2*index+1] = coord2;
134 myArray[mySegmentNumber*2] = coord1;
135 myArray[mySegmentNumber*2+1] = coord2;
141 bool GLViewer_LineList::readSegment( int theIndex, double& coord1, double& coord2 )
143 if( theIndex > mySegmentNumber || !myArray)
146 coord1 = myArray[theIndex*2];
147 coord2 = myArray[theIndex*2+1];
152 int GLViewer_LineList::contains( double thePoint ) const
154 if( !myArray || mySegmentNumber == 0 )
157 for( int i = 0; i < mySegmentNumber; i++ )
158 if( myArray[2*i] <= thePoint && thePoint <= myArray[2*i+1] )
165 bool GLViewer_LineList::removeSegment( int theIndex )
167 if( theIndex > mySegmentNumber || !myArray)
170 for( int i = theIndex; i < mySegmentNumber; i++ )
172 myArray[i*2] = myArray[(i+1)*2];
173 myArray[i*2+1] = myArray[(i+1)*2+1];
176 myArray[mySegmentNumber*2] = 0.0;
177 myArray[mySegmentNumber*2+1] = 0.0;
181 bool GLViewer_LineList::removeSegment( double coord1, double coord2 )
183 if( coord1 > coord2 )
185 double temp = coord1;
190 if( 2*mySegmentNumber == myRealSize || !myArray )
195 while( index < mySegmentNumber)
197 readSegment( index, c1, c2 );
198 if( coord1 < c1 && coord2 < c1 )
203 else if( coord1 < c1 && coord2 < c2 )
205 myArray[index*2] = coord2;
208 else if( c1 < coord1 && coord2 < c2 )
210 if( 2*mySegmentNumber == myRealSize )
212 for( int i = mySegmentNumber; i > index + 1; i-- )
214 myArray[2*i] = myArray[2*(i-1)];
215 myArray[2*i+1] = myArray[2*(i-1)+1];
217 myArray[2*(index+1)+1] = myArray[2*index+1];
218 myArray[2*(index+1)] = coord2;
219 myArray[2*index+1] = coord1;
223 else if( coord1 < c2 && c2 < coord2 )
227 myArray[2*index+1] = coord1;
230 if( index != mySegmentNumber - 1 )
232 for( int i = index+1; i < mySegmentNumber; i++ )
234 if( coord2 < myArray[2*i] )
238 for( int j = 1; i+j-1 < mySegmentNumber;j++ )
240 myArray[2*(index+j)] = myArray[2*(i+j-1)];
241 myArray[2*(index+j)+1] = myArray[2*(i+j-1)+1];
243 for( int k = 0; k < mySegmentNumber - i; k++ )
245 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
246 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
248 mySegmentNumber -= i - index -1;
254 for( int j = 0; index + j + 1 < mySegmentNumber;j++ )
256 myArray[2*(index+j)] = myArray[2*(index+j+1)];
257 myArray[2*(index+j)+1] = myArray[2*(index+j+1)+1];
260 myArray[2*(mySegmentNumber - 1)] = 0.0;
261 myArray[2*(mySegmentNumber - 1)+1] = 0.0;
271 else if( coord2 < myArray[2*i+1] )
278 myArray[2*index] = coord2;
279 myArray[2*index+1] = myArray[2*i+1];
281 for( int j = 1; i+j < mySegmentNumber;j++ )
283 myArray[2*(index+j)] = myArray[2*(i+j)];
284 myArray[2*(index+j)+1] = myArray[2*(i+j)+1];
286 for( int k = 0; k < mySegmentNumber - i - 1; k++ )
288 myArray[2*(mySegmentNumber - 1- k)] = 0.0;
289 myArray[2*(mySegmentNumber - 1- k)+1] = 0.0;
291 mySegmentNumber -= i - index;
297 myArray[2*(index+1)] = coord2;
302 myArray[2*(index)] = coord2;
303 myArray[2*(index)+1] = myArray[2*(index+1)+1];
304 for( int j = index+1; j < mySegmentNumber-1; j++ )
306 myArray[2*j] = myArray[2*(j+1)];
307 myArray[2*j+1] = myArray[2*(j+1)+1];
310 myArray[2*mySegmentNumber] = 0.0;
311 myArray[2*mySegmentNumber+1] = 0.0;
323 myArray[2*index] = 0.0;
324 myArray[2*index+1] = 0.0;
333 void GLViewer_LineList::clear()
336 memset( myArray, 0, myRealSize*sizeof(double) );
339 void GLViewer_LineList::print()
341 cout << "MainCoord: " << myMainCoord <<" SIZE: " << myRealSize << " ENum: " << mySegmentNumber << " :::";
342 for( int i = 0; i < mySegmentNumber; i++ )
343 cout << " " << myArray[2*i] << " " << myArray[2*i+1] << " | ";
348 void GLViewer_LineList::show( FieldDim theDim )
353 glColor3f( 1.0, 0.0, 1.0 );
357 for( int i = 0; i < mySegmentNumber; i++ )
359 glVertex2d( myArray[2*i], myMainCoord );
360 glVertex2d( myArray[2*i+1], myMainCoord );
364 else if( theDim == FD_Y )
367 for( int i = 0; i < mySegmentNumber; i++ )
369 glVertex2d( myMainCoord, myArray[2*i] );
370 glVertex2d( myMainCoord, myArray[2*i+1] );
376 /****************************************************************************
377 ** Class: GLViewer_LineField
378 ** Descr: Tools for solving
380 ** Created: UI team, 27.10.05
381 *****************************************************************************/
382 GLViewer_LineField::GLViewer_LineField()
385 myGraphArray1 = NULL;
386 myGraphArray2 = NULL;
395 GLViewer_LineField::GLViewer_LineField( const int theMAXSize, const int theXN, const int theYN )
398 myGraphArray1 = NULL;
399 myGraphArray2 = NULL;
403 if( theXN <= 0 || theYN <= 0 )
412 myXLineArray = new GLViewer_LineList*[theXN];
413 myYLineArray = new GLViewer_LineList*[theYN];
415 for( int i = 0; i < theXN; i++ )
416 myXLineArray[i] = new GLViewer_LineList( theMAXSize );
418 for( int j = 0; j < theYN; j++ )
419 myYLineArray[j] = new GLViewer_LineList( theMAXSize );
426 GLViewer_LineField::~GLViewer_LineField()
430 for( int i = 0; i < myXSize; i++ )
431 delete myXLineArray[i];
438 for( int j = 0; j < myYSize; j++ )
439 delete myYLineArray[j];
445 delete myGraphArray1;
448 delete myGraphArray2;
451 void GLViewer_LineField::addLine( FieldDim theDim, GLViewer_LineList* )
456 void GLViewer_LineField:: addLine( FieldDim theDim, double theMC, double theBegin, double theEnd )
458 GLViewer_LineList* aLL = new GLViewer_LineList( 1 );
459 aLL->addSegment( theBegin, theEnd );
460 aLL->setMainCoord( theMC );
461 addLine( theDim, aLL );
465 int GLViewer_LineField::insertLine( FieldDim theDim, GLViewer_LineList* theLL, int thePosition )
467 if( !myXLineArray || !myYLineArray )
470 GLViewer_LineList** anArray = getLLArray( theDim );
474 int size = getDimSize( theDim );
476 if( thePosition >= size )
478 else if( thePosition < 0 )
480 if( anArray[size-1]->count() != 0 ) // no more space
483 for( int i = 0; i < size; i++ )
485 if( anArray[i]->count() == 0 )
492 double cur_mc = anArray[i]->mainCoord();
493 if( theLL->mainCoord() < cur_mc )
495 for( int j = 0; j+i+1 < size; j++ )
497 delete anArray[size-j-1];
498 anArray[size-j-1] = anArray[size-j-2];
508 delete anArray[thePosition];
509 anArray[thePosition] = theLL;
516 int GLViewer_LineField::insertLine( FieldDim theDim, double theMainCoord, double theBegin, double theEnd, int thePosition )
518 GLViewer_LineList* aLL = new GLViewer_LineList( 1 );
519 aLL->addSegment( theBegin, theEnd );
520 aLL->setMainCoord( theMainCoord );
521 return insertLine( theDim, aLL, thePosition );
525 FieldDim GLViewer_LineField::invertDim( FieldDim theFD )
533 GLViewer_LineList* GLViewer_LineField::getLine( int theIndex, FieldDim theFD )
535 if( !myXLineArray || !myYLineArray )
540 if( theIndex > myXSize )
543 return myXLineArray[theIndex];
545 else if( theFD == FD_Y )
547 if( theIndex > myYSize )
550 return myYLineArray[theIndex];
556 void GLViewer_LineField::setBorders( double X1, double X2, double Y1, double Y2 )
558 if( !myXLineArray || !myYLineArray )
561 for( int i = 0; i < myXSize; i++ )
563 myXLineArray[i]->clear();
564 myXLineArray[i]->addSegment( X1, X2 );
565 myXLineArray[i]->setMainCoord( Y1 + (Y2-Y1)*(double(i)/(myXSize-1)) );
568 for( int j = 0; j < myYSize; j++ )
570 myYLineArray[j]->clear();
571 myYLineArray[j]->addSegment( Y1, Y2 );
572 myYLineArray[j]->setMainCoord( X1 + (X2-X1)*(double(j)/(myYSize-1)) );
576 void GLViewer_LineField::addRectangle( double top, double right, double bottom, double left )
578 if( !myXLineArray || !myYLineArray )
580 for( int i = 0; i < myXSize; i++ )
582 double mainCoord = myXLineArray[i]->mainCoord();
583 if( mainCoord < top && mainCoord > bottom )
584 myXLineArray[i]->removeSegment( left, right );
587 for( int j = 0; j < myYSize; j++ )
589 double mainCoord = myYLineArray[j]->mainCoord();
590 if( mainCoord < right && mainCoord > left )
591 myYLineArray[j]->removeSegment( bottom, top );
595 void GLViewer_LineField::print()
597 cout << "My X matrix Number: " << myXSize << endl;
598 for( int i = 0; i < myXSize; i++ )
599 myXLineArray[i]->print();
601 cout << "My Y matrix Number: " << myYSize << endl;
602 for( int j = 0; j < myYSize; j++ )
603 myYLineArray[j]->print();
606 void GLViewer_LineField::show()
608 for( int i = 0; i < myXSize; i++ )
609 getLine( i, FD_X )->show( FD_X );
611 for( int j = 0; j < myYSize; j++ )
612 getLine( j, FD_Y )->show( FD_Y );
614 double* anArray = solution( count );
615 glColor3f( 1.0, 0.0, 0.0 );
617 for( int k = 0; k < count; k++ )
619 glVertex2d( anArray[4*k], anArray[4*k+1] );
620 glVertex2d( anArray[4*k+2], anArray[4*k+3] );
624 cout << "Show function" << endl;
627 int GLViewer_LineField::getDimSize( FieldDim theDim )
631 else if( theDim == FD_Y )
637 int* GLViewer_LineField::intersectIndexes( FieldDim theDim, int theIndex, const GLViewer_LineList* theLL, int& theSize )
640 if( !myXLineArray || !myYLineArray )
643 int aDimSize = getDimSize( theDim );
644 int* anArray = new int[aDimSize*2 ];
646 for( int i = 0; i < aDimSize; i++ )
648 GLViewer_LineList* aLL = getLine( i, theDim );
649 int index = aLL->contains( theLL->mainCoord() );
650 if( index != -1 && theLL->contains( aLL->mainCoord() ) == theIndex )
652 anArray[theSize*2] = i;
653 anArray[theSize*2+1] = index;
662 bool GLViewer_LineField::setPoint( FieldPoint thePoint, double theX, double theY )
664 if( !myXLineArray || !myYLineArray )
668 int xSeg = -1, ySeg = -1;
669 for( i = 0; i < myXSize; i++ )
671 GLViewer_LineList* aLL = getLine( i, FD_X );
672 if( aLL->mainCoord() == theY )
674 xSeg = aLL->contains( theX );
679 for( j = 0; j < myYSize; j++ )
681 GLViewer_LineList* aLL = getLine( j, FD_Y );
682 if( aLL->mainCoord() == theX )
684 ySeg = aLL->contains( theY );
689 if( xSeg != -1 && ySeg != -1 )
691 if( thePoint == FP_Start )
693 myStartPoint.myXLineIndex = i;
694 myStartPoint.myXSegmentIndex = xSeg;
695 myStartPoint.myYLineIndex = j;
696 myStartPoint.myYSegmentIndex = ySeg;
697 myStartPoint.mySolveIndex = -1;
701 myEndPoint.myXLineIndex = i;
702 myEndPoint.myXSegmentIndex = xSeg;
703 myEndPoint.myYLineIndex = j;
704 myEndPoint.myYSegmentIndex = ySeg;
705 myEndPoint.mySolveIndex = -1;
713 int GLViewer_LineField::segmentNumber()
715 if( !(myXLineArray || myYLineArray) )
719 for( int aDim = 0; aDim < 2; aDim++ )
720 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
721 aNumber += getLine( i, (FieldDim)aDim )->count();
726 void GLViewer_LineField::optimize()
728 if( !myXLineArray || !myYLineArray )
731 for( int aDim = 0; aDim < 2; aDim++ )
733 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
735 GLViewer_LineList* aLL = getLine( i, (FieldDim)aDim );
736 for( int k =0, aSegNum = aLL->count(); k < aSegNum; k++ )
738 // int index = i; unused
740 aLL->readSegment( k, a1, a2 );
741 for( int l = i+1, m = getDimSize( (FieldDim)aDim ); l < m; l++ )
744 GLViewer_LineList* aCurLL = getLine( l, (FieldDim)aDim );
745 for( int j = 0, count = aCurLL->count(); j < count; j++ )
748 aCurLL->readSegment( j, c1, c2 );
749 if( a1 == c1 && a2 == c2 )
751 if( !(aDim == 0 && myStartPoint.myXLineIndex == l && myStartPoint.myXSegmentIndex == j) &&
752 !(aDim == 0 && myEndPoint.myXLineIndex == l && myEndPoint.myXSegmentIndex == j) &&
753 !(aDim == 1 && myStartPoint.myYLineIndex == l && myStartPoint.myYSegmentIndex == j) &&
754 !(aDim == 1 && myEndPoint.myYLineIndex == l && myEndPoint.myYSegmentIndex == j) )
755 aCurLL->removeSegment( j );
765 if( end == -1 || end == 1)
773 void GLViewer_LineField::initialize()
775 if( !myXLineArray || !myYLineArray )
778 int size = segmentNumber();
783 myGraphArray1 = new GraphNode[size];
784 myGraphArray2 = new GraphNode[size];
789 for( int aDim = 0; aDim < 2; aDim++ )
791 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
793 GLViewer_LineList* aLL = getLine( i, (FieldDim)aDim );
794 for( int k =0, aSegNum = aLL->count(); k < aSegNum; k++ )
796 myGraphArray1[index].myCount = size;
797 myGraphArray1[index].myDim = (FieldDim)aDim;
798 myGraphArray1[index].myLineIndex = i;
799 myGraphArray1[index].mySegmentindex = k;
800 myGraphArray1[index].prevNodeIndex = -1;
802 myGraphArray2[index].myCount = size;
803 myGraphArray2[index].myDim = (FieldDim)aDim;
804 myGraphArray2[index].myLineIndex = i;
805 myGraphArray2[index].mySegmentindex = k;
806 myGraphArray2[index].prevNodeIndex = -1;
808 if( !isXSet && aDim == FD_X && myStartPoint.myXLineIndex == i && myStartPoint.myXSegmentIndex == k )
810 myGraphArray1[index].myCount = 0;
814 if( aDim == FD_Y && !isYSet && myStartPoint.myYLineIndex == i && myStartPoint.myYSegmentIndex == k )
816 myGraphArray1[index].myCount = 0;
826 void GLViewer_LineField::iteration()
828 int aParam = myCurCount;
831 int* aNodes = findByCount( aParam );
832 GraphNode* aCurArray = getCurArray();
834 for( int i = 0; i < aParam; i++ )
836 GraphNode aCurNode = aCurArray[aNodes[i]];
838 int* aInterNodes = intersectIndexes( invertDim( aCurNode.myDim ), aCurNode.mySegmentindex,
839 getLine( aCurNode.myLineIndex, aCurNode.myDim ), aSize );
840 for( int j = 0; j < aSize; j++ )
842 int index = findBySegment( invertDim( aCurNode.myDim ), aInterNodes[2*j], aInterNodes[2*j+1], false );
844 if( aCurArray[index].myCount > myCurCount )
846 aCurArray[index].myCount = myCurCount;
847 aCurArray[index].prevNodeIndex = aNodes[i];
851 delete[] aInterNodes;
857 GLViewer_LineField::IterationStatus GLViewer_LineField::checkComplete()
859 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
863 GraphNode* aCurArray = getCurArray(),
864 * aSecArray = getSecArray();
866 for( int i = 0, n = segmentNumber(); i < n; i++ )
868 if( aCurArray[i].myCount != aSecArray[i].myCount )
870 if( aCurArray[i].myDim == FD_X &&
871 aCurArray[i].myLineIndex == myEndPoint.myXLineIndex &&
872 aCurArray[i].mySegmentindex == myEndPoint.myXSegmentIndex )
874 cout << "Algorithm complete X!!!!!!!" << endl;
875 myEndPoint.mySolveIndex = i;
878 else if( aCurArray[i].myDim == FD_Y &&
879 aCurArray[i].myLineIndex == myEndPoint.myYLineIndex &&
880 aCurArray[i].mySegmentindex == myEndPoint.myYSegmentIndex )
882 cout << "Algorithm complete Y!!!!!!!" << endl;
883 myEndPoint.mySolveIndex = i;
889 aSecArray[i].myCount = aCurArray[i].myCount;
890 aSecArray[i].prevNodeIndex = aCurArray[i].prevNodeIndex;
895 if( myCurArrayIndex == 0)
900 cout << "Number of ways: " << count << endl;
904 return IS_NOT_SOLVED;
907 int* GLViewer_LineField::findByCount( int& theParam )
909 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
912 int count = segmentNumber();
913 int* anArray = new int[count];
916 GraphNode* aCurArray = getCurArray();
917 for( int i = 0; i < count; i++ )
919 GraphNode aCurNode = aCurArray[i];
920 if( aCurNode.myCount == theParam )
931 int GLViewer_LineField::findBySegment( FieldDim theDim, int theLineIndex, int theSegment, bool inCurArray )
933 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 || getDimSize( theDim ) <= theLineIndex )
936 GraphNode* aCurArray;
938 aCurArray = getCurArray();
940 aCurArray = getSecArray();
942 for( int i = 0, n = segmentNumber(); i < n; i++ )
944 GraphNode aCurNode = aCurArray[i];
945 if( aCurNode.myDim == theDim && aCurNode.myLineIndex == theLineIndex && aCurNode.mySegmentindex == theSegment )
952 GLViewer_LineField::EndStatus GLViewer_LineField::startAlgorithm()
954 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
959 cout << "-----------Iteration #" << myCurCount << "-------------" << endl;
962 IterationStatus is = checkComplete();
965 else if( is == IS_LOOP )
967 else if( is == IS_SOLVED )
973 double* GLViewer_LineField::solution( int& theSize )
975 if( !myXLineArray || !myYLineArray || !myGraphArray1 || !myGraphArray2 )
978 if( myEndPoint.mySolveIndex == -1 )
981 theSize = myCurCount+1;
982 double* anArray = new double[theSize*4];
984 GraphNode* aCurArray = getCurArray();
986 int index = myEndPoint.mySolveIndex;
987 for( int i = 0; i <= myCurCount; i++ )
992 GLViewer_LineList* aLL = getLine( aCurArray[index].myLineIndex, aCurArray[index].myDim );
993 aLL->readSegment( aCurArray[index].mySegmentindex, c1, c2 );
995 if( aCurArray[index].myDim == FD_X )
998 anArray[i*4+1] = aLL->mainCoord();
1000 anArray[i*4+3] = aLL->mainCoord();
1004 anArray[i*4] = aLL->mainCoord();
1005 anArray[i*4+1] = c1;
1006 anArray[i*4+2] = aLL->mainCoord();
1007 anArray[i*4+3] = c2;
1010 index = aCurArray[index].prevNodeIndex;
1016 GraphNode* GLViewer_LineField::getCurArray()
1018 if( !myGraphArray1 || !myGraphArray2 )
1021 if( myCurArrayIndex == 0)
1022 return myGraphArray1;
1024 return myGraphArray2;
1027 GraphNode* GLViewer_LineField::getSecArray()
1029 if( !myGraphArray1 || !myGraphArray2 )
1032 if( myCurArrayIndex == 0)
1033 return myGraphArray2;
1035 return myGraphArray1;
1038 int GLViewer_LineField::maxSegmentNum()
1040 if( !myXLineArray || !myYLineArray )
1044 for( int aDim = 0; aDim < 2; aDim++ )
1046 for( int i = 0, n = getDimSize( (FieldDim)aDim ); i < n; i++ )
1048 int count = getLine( i, (FieldDim)aDim )->count();
1049 if( count > max_num )
1057 GLViewer_LineList** GLViewer_LineField::getLLArray( FieldDim theDim )
1059 if( theDim == FD_X )
1060 return myXLineArray;
1061 else if( theDim == FD_Y )
1062 return myYLineArray;