KMEANS聚类遇上凸包

代码下载：http://download.csdn.net/detail/hzq20081121107/7221575

程序功能：

在对话框上随机点上一些点，

在k值处设要划分几个聚类，在T值初设置进行几次迭代（用k-means求聚类）

点击cluster按钮，程序将以不同的颜色画出k个聚类，并且用凸包圈起每个聚类（双链法求凸包）。

程序效果图：

x、y为点的坐标，c为点的类别

struct cluNode
{
double x;
double y;
int c;
};

clunode【】为待分类的点的集合
cluNode clunode[1000];

nodeNum为待分类的点的数量
int nodeNum;

centerNode【】为聚类中心
cluNode centerNode[100];

CPoint按y从小到大其，当y相等时按x从小到大排序
int cmp(CPoint a,CPoint b)
{
return a.y < b.y || (a.y == b.y && a.x < b.x);
}

鼠标左键事件（取得待分类点）：

View Code

 1 void C聚类Dlg::OnLButtonDown(UINT nFlags, CPoint point)
 2 {
 3     clunode[nodeNum].x=point.x;
 4     clunode[nodeNum].y=point.y;
 5     clunode[nodeNum].c=1;
 6                   nodeNum++;
 7 
 8     CDC *pDC;
 9     pDC=GetDC();
10     int r=4;
11     CBrush MyBrush;
12     MyBrush.CreateSolidBrush(RGB(255,250,0));
13                   pDC->SelectObject(&MyBrush);
14     pDC->Ellipse(point.x-r,point.y-r,point.x+r,point.y+r);
15 
16     CDialogEx::OnLButtonDown(nFlags, point);
17 }

聚类：

View Code

void C聚类Dlg::OnBnClickedOk()
{
    UpdateData(true);
    int i,j,k;
    //设置中心点
    for(i=0;i<m_cluNum;i++)
    {
        centerNode[i]=clunode[i];
        centerNode[i].c=i;
    }
    //clusterDraw();
    //聚类
    double minDis,tempDis;
    int t=99;
    for(k=0;k<t;k++)
    {
        //重新分类
        for(i=0;i<nodeNum;i++)
        {
            clunode[i].c=0;
            minDis=(clunode[i].x-centerNode[0].x)*(clunode[i].x-centerNode[0].x)+(clunode[i].y-centerNode[0].y)*(clunode[i].y-centerNode[0].y);
            for(j=0;j<m_cluNum;j++)
            {
                tempDis=(clunode[i].x-centerNode[j].x)*(clunode[i].x-centerNode[j].x)+(clunode[i].y-centerNode[j].y)*(clunode[i].y-centerNode[j].y);
                if(tempDis<minDis)
                {
                    minDis=tempDis;
                    clunode[i].c=j;
                }
            }
        }
        //求分类中心点
        int cluLen[100]={0};
        for(i=0;i<m_cluNum;i++)    
            centerNode[i].x=centerNode[i].y=0; 
        for(i=0;i<nodeNum;i++)
        {
            centerNode[clunode[i].c].x+=clunode[i].x;
            centerNode[clunode[i].c].y+=clunode[i].y;
            cluLen[clunode[i].c]++;
        }
        for(i=0;i<m_cluNum;i++)
        {
            centerNode[i].x/=double(cluLen[i]);
            centerNode[i].y/=double(cluLen[i]);
        } 
        m_t=k;
        UpdateData(false);
        //clusterDraw();
    };
    clusterDraw();
}

根据聚类结果画凸包：

View Code

//画凸包
void C聚类Dlg::clusterDraw(void)
{
    CDC *pDC;
    pDC=GetDC();
    
    int r=4;
    int i,j,k;
    for(i=0;i<nodeNum;i++)
    {
        double ratio=double(clunode[i].c)/double(m_cluNum);
        CBrush MyBrush;
        MyBrush.CreateSolidBrush(RGB(255*ratio,255*(1-ratio),255*ratio));//255*ratio));
        pDC->SelectObject(&MyBrush);
        pDC->Ellipse(clunode[i].x-r,clunode[i].y-r,clunode[i].x+r,clunode[i].y+r);
    }

    CPoint pnt[1000];
    CPoint res[1000];
    for(j=0;j<m_cluNum;j++)
    {
        int pnum=0;
        for(i=0;i<nodeNum;i++)
        {
            if(clunode[i].c==j)
            {
              pnt[pnum].x=clunode[i].x;
              pnt[pnum].y=clunode[i].y;
              pnum++;
            }
        }
        int n=pnum;
        std::sort(pnt,pnt+n,cmp);//paixu();
        int len, k = 0, top = 1;
       
        if (n == 0) top=0; res[0] = pnt[0];
        if (n == 1) top=1; res[1] = pnt[1];
        if (n == 2) top=2; res[2] = pnt[2];
        for (i = 2; i < n; i++) 
        {
            while (top && mult(pnt[i], res[top], res[top-1]))
            top--;
            res[++top] = pnt[i];
        }
        len = top; res[++top] = pnt[n - 2];
        for (i = n - 3; i >= 0; i--) 
        {
            while (top!=len && mult(pnt[i], res[top], res[top-1])) top--;
            res[++top] = pnt[i];
        }
    
        pDC->MoveTo(res[0]);
        for(i=1;i<=top;i++)
        {
            pDC->LineTo(res[i]);
        }
    }
}

求叉积：

View Code

//叉积
bool C聚类Dlg::mult(CPoint sp, CPoint ep, CPoint op)
{
    return (sp.x - op.x) * (ep.y - op.y)>= (ep.x - op.x) * (sp.y - op.y);
}