Back to July Calendar

Next Entry (WebEQ)→
Next Entry (MathML)→

October 21, 2005

Drawing Necklaces

My goal today is to draw necklaces as sort of "colored beads" in a circle. First the Monte Carlo method will develop all the beads and then we'll just pick a random one and draw it.

It's been a while since I trotted out the openGL tools, so I'll start by just reminding everyone (at least, Me, Myself and I) how one goes about making a filled polygon to resemble a circle. Remember that circles are not primitive in openGL.

Here's the code I wrote:

/* filled red circle */
#include <GL/glut.h>   // This includes gl.h and glu.h
#include <cmath>
#include <iostream>
using namespace std;

void circle(GLfloat *, GLfloat, GLfloat);
void display(void);
void init();
	
int main(int argc, char** argv) {
      glutInit(&argc, argv);
      glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
      glutInitWindowSize(500,500);
      glutInitWindowPosition(0,0);
      glutCreateWindow("whimple");
      glutDisplayFunc(display);
      init();
      glutMainLoop();
}

void display(void) {
    glClear(GL_COLOR_BUFFER_BIT);
    glPolygonMode(GL_FRONT, GL_LINE);
    GLfloat smoothness = 25.0;
	GLfloat center[2] = {0.0,0.0};
	GLfloat radius = 1.0;  //unit circle
    circle(center, radius, smoothness); 
    glFlush();
}

void init() {
      //set clear color to white
      glClearColor(1.0,1.0,1.0,1.0);
      //set standard orthogonal (look straight at) clipping view
      glMatrixMode(GL_PROJECTION);
      glLoadIdentity();
      gluOrtho2D(-1.1,1.1,-1.1,1.0);
}

void circle(GLfloat *center, GLfloat radius, GLfloat EDGES) {
    #define PI 3.14159265 
    //GLfloat EDGES = 30; 
    glColor3f(1.0,0.0,0.0); //Red
    /* draw a circle */ 
    cout << "\nbefore";
    glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    glBegin(GL_POLYGON);
	for (GLfloat i = 0; i < EDGES; i++) { 
       //glBegin(GL_LINE_STRIP); 
		glVertex2f(center[0]+radius*cos((2*PI*i)/EDGES), 
			center[1]+radius*sin((2*PI*i)/EDGES)); 
		glVertex2f(center[0]+radius*cos((2*PI*(i+1))/EDGES), 
			center[1]+radius*sin((2*PI*(i+1))/EDGES)); 
    	}
    glEnd(); 
    cout << "\nafter";
} // end circle

The code produces output that looks like this:

This is actually a 30-gon. In the picture above, the graphics window is partially covering the console window. Since the code outputs "before" to console before entering the gl-loop, and "after" after leaving, and the loop is reentered after each resizing/positioning of the window, in the process of placing the graph window over the console window, we see the repeated glutMainLoop manifest in the console window.

Now we'd like to allow the user to enter the bead set, have the program generate all necklaces and then, depict a random necklace as arrangement of little circles evenly spaced along the perimeter of a large circle. So, if there are N beads to distribute around the necklace, then the center points (A and C in the diagram at right) can be placed at

where i = 0, 1, ... , N – 1.

The radii of the beads will be π/N, so positioning the beads should be a fairly simple matter, especially if you don't mind a slight overlap.

So we need to mesh the circle and necklace routines to draw a necklace of beads (circle of circles) with the various color schemes possible for a given bead set, independent of rotation and reflection. This means making the necklace program a function, which I actually split into two functions: getBeads() which has the user input a bead set (whole numbers) & returns the number of beads input--something we need to know if we're going place the beads around the necklace circle--and getNecklaces() which takes the bead set and generates a bunch of (if not all) distinct necklaces.

As you'd expect, most of the action of this program is in the display() function which gets passed to the glutDisplayFunc() as a parameter in main(). Essentially, the user is asked to supply a bead set, which can be entered as, say, "1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6," and then "0" to indicate the end. The necklaces are generated in a vector of vectors of type int, and a nested while loop structure is used to draw each bead for each necklace, allowing the user to pause between necklaces.

To do:

Use the reshape function to make the window reshapable.
Generate necklaces only as needed, instead of all at once.
Use mouse click to get next necklace.
Animate the necklace to spin slowly?
Throw a wiggle into the animation.
Make the beads shiny with a glint from a light source.

Here is some output from the program:

The current necklace is
4 2 3 1 3 4 1 2 3 2 1 3 1 4 2 4
beadCounter = 0
Draw circle with center at (0.6,0)
radius = 0.11781
beadCounter = 1
Draw circle with center at (0.554328,0.22961)
beadCounter = 2
Draw circle with center at (0.424264,0.424264)
beadCounter = 3
Draw circle with center at (0.22961,0.554328)
beadCounter = 4
Draw circle with center at (-2.62268e-008,0.6)
beadCounter = 5
Draw circle with center at (-0.22961,0.554328)
beadCounter = 6
Draw circle with center at (-0.424264,0.424264)
beadCounter = 7
Draw circle with center at (-0.554328,0.22961)
beadCounter = 8
Draw circle with center at (-0.6,-5.24537e-008)
beadCounter = 9
Draw circle with center at (-0.554328,-0.22961)
beadCounter = 10
Draw circle with center at (-0.424264,-0.424264)
beadCounter = 11
Draw circle with center at (-0.22961,-0.554328)
beadCounter = 12
Draw circle with center at (7.15493e-009,-0.6)
beadCounter = 13
Draw circle with center at (0.22961,-0.554328)
beadCounter = 14
Draw circle with center at (0.424264,-0.424264)
beadCounter = 15
Draw circle with center at (0.554328,-0.22961)
Enter a character to continue: -

The current necklace is
3 4 4 3 2 1 1 1 4 2 1 2 3 2 3 4
beadCounter = 0
Draw circle with center at (0.6,0)
radius = 0.11781
beadCounter = 1
Draw circle with center at (0.554328,0.22961)
beadCounter = 2
Draw circle with center at (0.424264,0.424264)
beadCounter = 3
Draw circle with center at (0.22961,0.554328)
beadCounter = 4
Draw circle with center at (-2.62268e-008,0.6)
beadCounter = 5
Draw circle with center at (-0.22961,0.554328)
beadCounter = 6
Draw circle with center at (-0.424264,0.424264)
beadCounter = 7
Draw circle with center at (-0.554328,0.22961)
beadCounter = 8
Draw circle with center at (-0.6,-5.24537e-008)
beadCounter = 9
Draw circle with center at (-0.554328,-0.22961)
beadCounter = 10
Draw circle with center at (-0.424264,-0.424264)
beadCounter = 11
Draw circle with center at (-0.22961,-0.554328)
beadCounter = 12
Draw circle with center at (7.15493e-009,-0.6)
beadCounter = 13
Draw circle with center at (0.22961,-0.554328)
beadCounter = 14
Draw circle with center at (0.424264,-0.424264)
beadCounter = 15
Draw circle with center at (0.554328,-0.22961)
Enter a character to continue: -

Here's the complete program for this:

/* circle */
#include <GL/glut.h>   // This includes gl.h and glu.h
#include <cmath>
#include <iostream>

#include<cstdlib>
#include<ctime>

#include <vector>
using namespace std;

const GLfloat twoPi = 6.28318530718;

int getBeads(vector<int> &);
GLfloat getNecklaces(vector<int> &, int, vector<vector<int> > &);
void circle(GLfloat *, GLfloat, GLfloat);
void display(void);
void init();

void Swap(vector<int> &v, int, int);
void printVector( const vector< int > &);
bool itsNew(const vector<vector<int> > &, const vector<int> &, int, int &);
	
int main(int argc, char** argv) {
      glutInit(&argc, argv);
      glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
      glutInitWindowSize(500,500);
      glutInitWindowPosition(0,0);
      glutCreateWindow("whimple");
      glutDisplayFunc(display);
      init();
      glutMainLoop();
}

void display(void) {
  // R is the radius of the necklace, center and radius are bead parameters
	GLfloat R = 0.3, center[2], radius;
	// V will hold the necklaces
	vector<vector<int> > V(0);
	// beadSet is supplied by the user
	vector<int> beadSet;
	V.clear();
	GLfloat numBeads;
	// get the beads from the user
	numBeads = getBeads(beadSet);
	int numNecks;
	// generate the necklaces 
	numNecks = getNecklaces(beadSet, numBeads, V);
	cout << "\nThere are : " << numBeads << " beads in " 
             << numNecks << " necklaces.";
	glClear(GL_COLOR_BUFFER_BIT);
  	glPolygonMode(GL_FRONT, GL_LINE);
  	GLfloat smoothness = 30.0;
	// choose bead size to fit around necklace of given radius
	radius = R*twoPi/(2*numBeads);
	cout << "\n\nThere are " << numNecks << " necklaces to display. "
	     << "\nWe'll draw a random collection of these after drawing the one "
	     << "\nyou entered first.";
	int neckCounter = 0;
	while(neckCounter < numNecks ) {
		GLfloat beadCounter = 0;
		cout << "\nThe current necklace is "; 
                printVector(V[neckCounter]);
		while(beadCounter < numBeads) {
			cout << "\nbeadCounter = " << beadCounter;
			center[0] = R*cos(beadCounter*twoPi/numBeads);
			center[1] = R*sin(beadCounter*twoPi/numBeads);
			switch(V[neckCounter][beadCounter])
			{
				case(1) : 
					glColor3f(1.0,0.0,0.0);
					break;
				case(2) : 
					glColor3f(0.0,1.0,0.0);
					break;
				case(3) : 
					glColor3f(0.0,0.0,1.0);
					break;
				case(4) : 
					glColor3f(0.5,0.0,0.5);
					break;
				case(5) : 
					glColor3f(0.5,0.5,0.0);
					break;
				case(6) : 
					glColor3f(0.0,0.5,0.5);
					break;
				default :
					break;
			}
			cout << "\nDraw circle with center at (" 
                             << center[0] << "," << center[1] 
				 << ")"; // << "\nradius = " << radius;
			circle(center, radius, smoothness); 
			++beadCounter;
			glFlush(); // Don't forget to flush...
		} // end bead while
		++neckCounter;
		cout << "\nEnter a character to continue: ";  cin >> n;
		glClear(GL_COLOR_BUFFER_BIT);
		glFlush(); //do we need this here?
	} // end necklace while
}

void init() {
      //set clear color to white
      glClearColor(1.0,1.0,1.0,1.0);
      //set standard orthogonal (look straight at) clipping view
      glMatrixMode(GL_PROJECTION);
      glLoadIdentity();
      gluOrtho2D(-1.1,1.1,-1.1,1.0);
}

void circle(GLfloat *center, GLfloat radius, GLfloat EDGES) {
	#define PI 3.14159265 
  /* draw a circle */ 
	glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
	glBegin(GL_POLYGON);
		for (GLfloat i = 0; i < EDGES; i++) { 
			glVertex2f(center[0]+radius*cos((2*PI*i)/EDGES), 
				center[1]+radius*sin((2*PI*i)/EDGES)); 
			glVertex2f(center[0]+radius*cos((2*PI*(i+1))/EDGES), 
				center[1]+radius*sin((2*PI*(i+1))/EDGES)); 
    	}
    glEnd(); 
} // end circle


void Swap(vector<int> &v, int m, int n) {
	 int temp = v[m];
	 v[m] = v[n];
	 v[n] = temp;
}

void printVector(const std::vector< int > &v) {  
	std::vector<int>::const_iterator i = v.begin();
	cout << endl;
	for( ; i != v.end(); ++i) {
		cout << *i << " ";
	}
}

bool itsNew(const vector<vector<int> > &V, 
            const vector<int> &W, int n, int &k) {
	// check rotations
	bool same;
	int rot = 0;
	int i = 0, j;
	do {
		do { // check if any forward rotation has all elements the same
			j = 0; // base index
			do { // compare all elements of a particular rotation
                             // until mismatch
			   
			   same = (V[i][j] == W[(j+rot)%n]);
			   // cout << "\nV["<<i<<"]["<<j<<"] == 
                           // W["<<(j+rot)%n<<"] is " <<same;
			   ++j;
			} while(same && j<n);
			if(!same) {  // check reflected rotations
	  		   j = 0;
	  		   do {
			      same = (V[i][j] == W[n-1-(j+rot)%n]);
				  // cout << "\nV["<<i<<"]["<<j<<"] == 
                                  // W["<<(j+rot)%n<<"] is " <<same;
				  ++j; 
 			   } while(same && j<n); // end do
            }//end if
			++rot;
		} while(!same && rot<n);
		++i;
		rot=0;  // Took too long to find this missing!
	} while(!same && i<=k);
	if(same) return false;
	else return true;
}

int getBeads(vector<int> &beadSet) {
	srand(time(0));
	// The user enters a set of beads as natural numbers.
	cout << "\nEnter bead set as whole numbers.  Enter zero to quit: \n";
	int numBeads = 0, x;
	cin >> x;
	while(x!=0) {	   	
		beadSet.push_back(x);
		cin >> x;
 		++numBeads;
	} 
	return numBeads;
}

GLfloat getNecklaces(vector<int> &beadSet, 
                     int numBeads, 
                     vector<vector<int> > &V) {
	cout << "\nIn getNecklaces.";
	V.clear();
	V.push_back(beadSet); //
	int Src, Dest;
	char a = 'n';
	int numNecks = 0;
	int count = 0;
	//bool isNew = true;
	while(count < 1000) {
	    // make a beadSet a random permutation
		for (Dest = numBeads-1; Dest > 0; Dest--)
		{       // Positions from [0] to [Dest]
		 	Src = rand() % (Dest+1);  
		 	Swap (beadSet,Src,Dest);
		}				
		if(itsNew(V,beadSet,numBeads,numNecks)) {
	 	    ++numNecks;
	 	    V.push_back(beadSet);
  	}
		++count;
		//if (count%5000 == 0) cout << "\nWith "
                //<< count << " guesses, we have " << k+1 << " necklaces.";
	}
	return numNecks; // return the number of beads
}