这些天做C#实验以及这个KMeans算法演示器，学了一下openGL，感觉有待加强。
//Point.h
/*
Point 结构体定义及实现
结构体重载了2个运算符：
1.== //判断两个Point的坐标值是否相等
2.<< //用于显示（以友元函数的方式重载）
*/
#ifndef Point_h_
#define Point_h_
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
const int mWidth=3; //显示时每个字符宽度
//存放点坐标的结构
struct Point{
string name; //点名称
double x; //x轴坐标
double y; //y轴坐标
//默认的结构体构造器
Point()
:x(-999),y(-999){
}
Point(double xx,double yy,string n)
:x(xx),y(yy),name(n){
}
//复制构造函数
Point(const Point &p)
:x(p.x),y(p.y),name(p.name){
}
//赋值复制函数
Point operator=(const Point &p){
if(this==&p)
return *this;
x=p.x;
y=p.y;
name=p.name;
return *this;
}
//判断两个Point坐标值是否相等
bool operator==(const Point &point)const{
return x==point.x&&y==point.y;
}
//重载<<
friend ostream& operator<<(ostream &os,const Point &p){
os<<setw(mWidth)<<right<<p.name<<
"("<<setw(mWidth)<<left<<p.x
<<","<<setw(mWidth)<<p.y<<")"<<" ";
return os;
}
};
#endif
functions.h主要是一些函数
//functions.h
#ifndef functions_h_
#define functions_h_
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include "Point.h"
#include <ctime>
#include <windows.h>
using namespace std;
const int MAX=20; //聚类点数
const int M_GROUP=3; //簇数
const int LIMIT=20; //允许聚类的最大次数
const int X_LIMIT=15; //X轴最大坐标
const int Y_LIMIT=15; //Y----
//数字转字符串
string numberToString(int i){
stringstream s;
s<<i;
return s.str();
};
//delay(n) 延时n秒
void delay(double sec)
{
time_t start_time, cur_time; // 变量声明
time(&start_time);
do {
time(&cur_time);
}while((cur_time - start_time) < sec );
};
//生成随机点
//size 生成随机点的个数
bool randPoint(vector<Point> &vp,int size){
vp.clear();
srand(time(0));
int i=0;
//生成随机点
while(i<size){
int x=rand()%X_LIMIT;
int y=rand()%Y_LIMIT;
string name="p";
string num=numberToString(i+1);
name+=num;
//加入到数组中
vp.push_back(Point(x,y,name));
i++;
}
if(i==size)
return true;
else
return false;
};
//输出单个坐标
static int countTimes=0;//用于输出格式控制
void outPoint(Point &p){
cout<<p;
countTimes++;
if(countTimes%5==0)
cout<<endl;
};
//输出数组中所有点
//展示所有点的函数
void display(vector<Point> &vp){
countTimes=0;
for_each(vp.begin(),vp.end(),outPoint);
};
//清空流内容
void eatLine(){
while(cin.get()!='\n')
continue;
};
//选择起始中心点输入
//center 存储中心点的数组
//vp 所有点
bool inputCenter(vector<Point> ¢er,vector<Point> &vp){
//可分簇的最大数目
int vpSize=vp.size();
//清空center中内容
center.clear();
cout<<"\n请输入分簇的数目:0--"<<vpSize<<endl;
int group;
cin>>group;
while(group<=0||group>vpSize){
cout<<"输入有误！"<<endl;
cout<<"\n请输入分簇的数目:0--"<<vpSize<<endl;
cin>>group;
}
//选择起始中心点
int j=0;
while(j<group){
int locate;
cout<<"请选择"<<group<<"个坐标点作为起始点,输入1代表p1:"<<endl;
cin>>locate;
if(locate>0&&locate<=vpSize){
Point temp=vp[locate-1];
cout<<"已经成功选择了"<<j+1<<"个起始点!"<<temp;
center.push_back(temp);
if(j!=group-1)
cout<<"请继续完成剩余选择："<<endl;
else{
cout<<"\n选择完成！选择的中心点为:"<<endl;
display(center);
return true;
}
j++;
}else{
cout<<"选择有误！"<<"请重新输入正确的值:"
<<1<<"--"<<vpSize<<":"<<endl;
}
eatLine();//清空流
}
return false;
};
#endif
//kmeans.h
#ifndef kmeans_h_
#define kmeans_h_
/*
@author：天下无双
@date:2014-6-5
@version:9.0
聚类算法K-means实现：采用强算算法
随机生成20个点，然后进行分成三个聚类
change:
坐标点改为double类型
//已经完成聚类算法
//弃用指针，全部使用vector<Point>代替
//界面版openGL
*/
#include "functions.h"
#include "openglFunc.h"
#include "Point.h"
#include <vector>
#include <cmath>
//参数为一维数组，数组大小，簇大小，选择的初始点
//返回值为聚类进行次数
//判断两次中心是否相等
bool isEqual(vector<Point> &lhs,vector<Point> &rhs){
int size=rhs.size();
for(int i=0;i<size;i++){
if(lhs[i]==rhs[i])
continue;
else
return false;
}
return true;
};
//计算中心点
//当size为0时，返回一个(-999,-999)表示没有元素
Point calCenter(vector<Point> &arr){
int size=arr.size();
if(size!=0){
double xSum=0;
double ySum=0;
for(int i=0;i<size;i++){
xSum+=arr[i].x;//注意优先级
ySum+=arr[i].y;
}
double x=xSum/size;
double y=ySum/size;
return Point(x,y,"center");
}else
return Point(-999,-999,"中心点重复，该中心没有点");
};
//计算两个点之间的距离
double pointToPoint(const Point &lhs,const Point &rhs){
double xToX=abs(lhs.x-rhs.x);
double yToY=abs(lhs.y-rhs.y);
double sum=pow(xToX,2)+pow(yToY,2);
double f=sqrt(sum);
return f;
};
//kmeans
//vp 点数组
//center 起始中心点数组
int kMeans(vector<Point> &vp,vector<Point> ¢er){
vector<Point> first;// 记录聚类上一次的中心
vector<Point> second; //记录这一次聚类的中心
vector<vector<Point>> group;//存放簇
/*
center和group的关系
下标对应 0 1 2 3 4
center 0 1 2 3 4
group 00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
.. .. .. .. ..
*/
int centerSize=center.size();
int vpSize=vp.size();
//先复制起始点到第一次聚类中心
for(int i=0;i<centerSize;i++)
first.push_back(center[i]);
cout<<"\n选择的起始中心点为："<<endl;
display(first);
cout<<"图中标记为红色的为中心点："<<endl;
//表明第一次选择的中心点
paintCenterPoint(first);
//number 聚类进行的次数
int number=0;
//color用于显示点时自动选择颜色
int color=0;
//第一次选择的中心点不应该被擦除
bool flag=true;
do{
//先置group拥有相应的数组
group.clear();
for(int i=0;i<centerSize;i++){
vector<Point> p;
group.push_back(p);
}
//将每个点指派到数组里面去
for(int i=0;i<vpSize;i++){
//locate 距离最近的中心点的坐标在center的下标
int locate=0;
double min=999;
for(int j=0;j<centerSize;j++){
double f=pointToPoint(vp[i],first[j]);
//标记距离最短的那个中心点
if(f<min){
min=f;
locate=j;
}
}
//将点指派到对应的vector<Point>
group[locate].push_back(vp[i]);
//输出点指派信息
//cout<<vp[i]<<"将被指派到簇"<<locate+1<<";"<<endl;
}
//显示簇
cout<<"经过聚类后的分簇情况："<<endl;
for(int i=0;i<centerSize;i++){
cout<<"\n簇"<<numberToString(i+1)<<":"<<endl;
display(group[i]);
cout<<endl;
}
for(int i=0;i<centerSize;i++){
if(color==5)
color=0;//重置color
setColor(color++);
paintVectorPoint(group[i]);
}
//重新计算簇中心并存放在second中
//先清空second
second.clear();
for(int i=0;i<centerSize;i++){
second.push_back(calCenter(group[i]));
}
for(int i=0;i<centerSize;i++){
if(second[i].x!=-999&&second[i].y!=-999)
second[i].name="c"+numberToString(i+1);
}
cout<<"\n新的簇中心为:"<<endl;
display(second);
//擦除旧中心点
if(!flag)
RemoveCenterPoint(first);
else{
flag=false;
}
//标明每个新中心
paintCenterPoint(second);
if(isEqual(first,second)){
cout<<"\n聚类完成!"<<endl;
cout<<"共聚类"<<number<<"次"<<endl;
break;
}else if(number>LIMIT){
cout<<"聚类次数超过了限制次数!"<<endl;
cout<<"程序将退出"<<endl;
break;
}else{
cout<<"\n未达到条件，继续聚类!"<<endl<<endl<<endl;
//重置first中心
first.clear();
for(int i=0;i<centerSize;i++){
first.push_back(second[i]);
}
}
number++;
}while(true);
return 0;
};
#endif
//openglFunc.h#ifndef opengl_kmeans_h_#define opengl_kmeans_h_#include <GL/glut.h>#include <vector>#include <iterator>#include <windows.h>#include <string>#include "Point.h"#include "functions.h"//延时时间#define DELAYTIME 0.2//点的大小#define POINTSIZE 8//显示比例#define BILI 10//边#define BIAN 1//X,Y边#define XLIMIT 1.5#define YLIMIT 1.5void drawString(const char *str);//在屏幕上绘制单个点void paintPoint(Point &p){ float x=p.x*1.0/BILI; float y=p.y*1.0/BILI; glPointSize(POINTSIZE); glBegin(GL_POINTS); glVertex2f(x,y); glEnd(); const char *name=p.name.c_str(); glRasterPos2f(x+0.02f,y+0.0f); drawString(name); glFlush();};//绘制一个数组的点void paintVectorPoint(vector<Point> &vp){ int size=vp.size(); for(int i=0;i<size;i++){ paintPoint(vp[i]); delay(DELAYTIME); }};//绘制中心点，使用红颜色//不延时void paintCenterPoint(vector<Point> &vp){ int size=vp.size(); glColor3f(1.0,0.0,0.0); for(int i=0;i<size;i++){ paintPoint(vp[i]); }};//将坐标绘制成网格void paintGrid(){ glColor3f(0.0,0.0,0.0); //竖向网格 for(int i=1;i<10*XLIMIT;i++){ float xx=i*1.0/10; glBegin(GL_LINES); glVertex2f(xx,0.0); glVertex2f(xx,YLIMIT); glEnd(); } //横向网格 for(int i=1;i<10*YLIMIT;i++){ float yy=i*1.0/10; glBegin(GL_LINES); glVertex2f(0.0,yy); glVertex2f(XLIMIT,yy); glEnd(); } };//显示坐标轴// ASCII字符总共只有0到127，一共128种字符#define MAX_CHAR 128void drawString(const char* str) { static int isFirstCall = 1; static GLuint lists; if( isFirstCall ) { // 如果是第一次调用，执行初始化 // 为每一个ASCII字符产生一个显示列表 isFirstCall = 0; // 申请MAX_CHAR个连续的显示列表编号 lists = glGenLists(MAX_CHAR); // 把每个字符的绘制命令都装到对应的显示列表中 wglUseFontBitmaps(wglGetCurrentDC(), 0, MAX_CHAR, lists); } // 调用每个字符对应的显示列表，绘制每个字符 for(; *str!='\0'; ++str) glCallList(lists + *str);};//擦除旧的中心点//使其变为白色void RemoveCenterPoint(vector<Point> &vp){ int size=vp.size(); glColor3f(1.0,1.0,1.0); for(int i=0;i<size;i++){ paintPoint(vp[i]); } //重绘网格 paintGrid();};//绘制背景色为白色void paintNull(){ glColor3f(1.0,1.0,1.0); glBegin(GL_POLYGON); glVertex2f(-BIAN,-BIAN); glVertex2f(-BIAN,BIAN); glVertex2f(BIAN,BIAN); glVertex2f(BIAN,-BIAN); glEnd();};//绘制XY轴void paintXY(){ glColor3f(0.0,0.0,0.0); //绘制X轴 glBegin(GL_LINES); glVertex2f(-0.2,0); glVertex2f(XLIMIT,0); glEnd(); //Y glBegin(GL_LINES); glVertex2f(0.0,YLIMIT); glVertex2f(0.0,-0.2); glEnd(); //坐标轴数字 glColor3f(1.0f, 0.0f, 0.0f); glRasterPos2f(-0.05f,-0.05f); drawString("0"); glRasterPos2f(0.49f,-0.05f); drawString("5"); glRasterPos2f(0.99f,-0.05f); drawString("10"); glRasterPos2f(-0.05f,0.5f); drawString("5"); glRasterPos2f(-0.05f,0.99f); drawString("10"); glRasterPos2f(1.45f,-0.05f); drawString("y"); glRasterPos2f(-0.05f,1.45f); drawString("x"); glutSwapBuffers();};//设置各簇的颜色//i最大值为6void setColor(int i){ switch(i){ case 2:glColor3f(1.0, 1.0, 0.0);break; //--> 黄色 case 1:glColor3f(0.0, 0.0, 1.0);break; //--> 蓝色 case 0:glColor3f(0.0, 1.0, 0.0);break; //--> 绿色 //case 3:glColor3f(1.0, 0.0, 0.0);break; //--> 红色 case 4:glColor3f(0.0, 1.0, 1.0);break; //--> 青色 case 5:glColor3f(1.0, 0.0, 1.0);break; //--> 品红色 case 3:glColor3f(0.0, 0.0, 0.0);break; //--> 黑色 default:break; }}#endif
//tFunc.h#ifndef tFunc_h_#define tFunc_h_#include <iostream>#include "functions.h"#include <vector>#include "openglFunc.h"#include "kmeans.h"#include "functions.h"#include <string>using namespace std;void yourChoice(){ cout<<"请输入生成的随机点个数:(建议小于20点可以看得更清晰)"<<endl; int num; cin>>num; eatLine(); vector<Point> vp; vector<Point> center; randPoint(vp,num); cout<<"随机生成的坐标点如下:"<<endl; display(vp); cout<<"请等待画好点后选择中心点:"<<endl; paintVectorPoint(vp); inputCenter(center,vp); kMeans(vp,center); };//演示书本例子void Example(){ Point p[10]={ Point(3,4,"p1"), Point(3,6,"p2"), Point(7,3,"p3"), Point(4,7,"p4"), Point(3,8,"p5"), Point(8,5,"p6"), Point(4,5,"p7"), Point(4,1,"p8"), Point(7,4,"p9"), Point(5,5,"p10"), }; vector<Point> vp; vector<Point> center; for(int i=0;i<10;i++) vp.push_back(p[i]); center.push_back(p[6]); center.push_back(p[9]); paintVectorPoint(vp); kMeans(vp,center);};#endif
//main.cpp
#include "openglFunc.h"
#include "functions.h"
#include "tFunc.h"
#include "displayFunc.h"
int main(int argc,char **argv)
{
glutInit(&argc,argv);
Init();
glutMainLoop();
}
演示如下：
