//k-mean.h
 #ifndef KMEAN_HEAD
 #define KMEAN_HEAD

 #include <vector>
 #include <map>

 //空間點的定義
 class Node
 {
     public:
        double pos_x;
        double pos_y;
        double pos_z;
      Node()
      {
          pos_x = 0.0;
          pos_y = 0.0;
          pos_z = 0.0;
      }
      Node(double x,double y,double z)
      {
          pos_x = x;
          pos_y = y;
          pos_z = z;
      }
       friend bool operator < (const Node& first,const Node& second)
       {
          //對x軸的比較
          if(first.pos_x < second.pos_x)
          {
        　　　　 return true;
          }
      　　else if (first.pos_x > second.pos_x)
          {
              return false;
     　　　}
         //對y軸的比較
      else
      {
        if(first.pos_y < second.pos_y)
             {
                 return true;
             }
             else if (first.pos_y > second.pos_y)
             {
                return false;
             }
             //對z軸的比較
         else
         {
             if(first.pos_z < second.pos_z)
                 {
                     return true;
                 }
                 else if (first.pos_z >=  second.pos_z)
                 {
                  　　return false;
                 }
             }
      }
       }

       friend bool operator == (const Node& first,const Node& second)
       {
             if(first.pos_x == second.pos_x && first.pos_y == second.pos_y && first.pos_z == second.pos_z)
             {
                 return true;
             }
             else
             {
                 return false;
             }
       }
 };

 class KMean
 {
 private:
     int cluster_num;//生成的簇的數量。
     std:: vector<Node> mean_nodes;//均值點
     std:: vector<Node> data;//所有的數據點
     std:: map <int , std:: vector<Node> > cluster;//簇,key為簇的下標，value為該簇中所有點

     void Init();//初始化函數（首先隨即生成代表點）
     void ClusterProcess();//聚類過程，將空間中的點分到不同的簇中
     Node GetMean(int cluster_index);//生成均值
     void NewCluster();//確定新的簇過程，該函數會調用ClusterProcess函數。
     double Kdistance(Node active,Node other);//判斷兩個點之間的距離

     public:
     KMean(int c_num,std:: vector<Node> node_vector);
     void Star();//啟動k均值算法

 };
#endif // KMEAN_HEAD

//k-mean.h
 #ifndef KMEAN_HEAD
 #define KMEAN_HEAD

 #include <vector>
 #include <map>

 //空間點的定義
 class Node
 {
     public:
        double pos_x;
        double pos_y;
        double pos_z;
      Node()
      {
          pos_x = 0.0;
          pos_y = 0.0;
          pos_z = 0.0;
      }
      Node(double x,double y,double z)
      {
          pos_x = x;
          pos_y = y;
          pos_z = z;
      }
       friend bool operator < (const Node& first,const Node& second)
       {
          //對x軸的比較
          if(first.pos_x < second.pos_x)
          {
        　　　　 return true;
          }
      　　else if (first.pos_x > second.pos_x)
          {
              return false;
     　　　}
         //對y軸的比較
      else
      {
        if(first.pos_y < second.pos_y)
             {
                 return true;
             }
             else if (first.pos_y > second.pos_y)
             {
                return false;
             }
             //對z軸的比較
         else
         {
             if(first.pos_z < second.pos_z)
                 {
                     return true;
                 }
                 else if (first.pos_z >=  second.pos_z)
                 {
                  　　return false;
                 }
             }
      }
       }

       friend bool operator == (const Node& first,const Node& second)
       {
             if(first.pos_x == second.pos_x && first.pos_y == second.pos_y && first.pos_z == second.pos_z)
             {
                 return true;
             }
             else
             {
                 return false;
             }
       }
 };

 class KMean
 {
 private:
     int cluster_num;//生成的簇的數量。
     std:: vector<Node> mean_nodes;//均值點
     std:: vector<Node> data;//所有的數據點
     std:: map <int , std:: vector<Node> > cluster;//簇,key為簇的下標，value為該簇中所有點

     void Init();//初始化函數（首先隨即生成代表點）
     void ClusterProcess();//聚類過程，將空間中的點分到不同的簇中
     Node GetMean(int cluster_index);//生成均值
     void NewCluster();//確定新的簇過程，該函數會調用ClusterProcess函數。
     double Kdistance(Node active,Node other);//判斷兩個點之間的距離

     public:
     KMean(int c_num,std:: vector<Node> node_vector);
     void Star();//啟動k均值算法

 };
#endif // KMEAN_HEAD

 #include "k-mean.h"
 #include <vector>
 #include <map>
 #include <ctime>
 #include <cstdlib>
 #include <algorithm>
 #include <cmath>
 #include <iostream>

 using namespace std;
 #define MAXDISTANCE 1000000

 KMean::KMean(int c_num,vector<Node> node_vector)
 {
       cluster_num = c_num;
       data = node_vector;
       srand((int)time(0));
       Init();
 }

 void KMean::Init()//初始化函數（首先隨即生成代表點）
 {
      for(int i =0 ;i<cluster_num;)
      {
            int pos = rand() % data.size();

            bool insert_flag = true;

            //首先判斷選中的點是否是中心點
            for(unsigned int j = 0;j<mean_nodes.size();j++)
            {
                if(mean_nodes[j] ==  data[i])
                {
                    insert_flag = false;
                    break;
                }
            }

            if(insert_flag )
            {
                  mean_nodes.push_back(data[pos]);
                  i++;
            }
      }
      ClusterProcess();//進行聚類過程
 }

  void KMean::ClusterProcess()//聚類過程，將空間中的點分到不同的簇中
  {
             //遍歷空間上所有的點
             for( unsigned int i = 0 ; i < data.size();i++)
             {
                  //忽略中心點
                 bool continue_flag = false;
                 for(unsigned int j = 0;j<mean_nodes.size();j++)
                     {
                         if(mean_nodes[j] ==  data[i])
                         {
                                 continue_flag = true;
                                 break;
                         }
                     }
                 if(continue_flag)
                     {
                         continue;
                     }

                  //下面是聚類過程
                  //首先找到離當前點最近的中心點,并記錄下該中心點所在的簇
                  int min_kdistance = MAXDISTANCE;
                  int index = 0 ;
                  for(unsigned int j = 0;j < mean_nodes.size();j++)
                  {
                      double dis = Kdistance(data[i],mean_nodes[j]);
                      if(dis < min_kdistance)
                      {
                          min_kdistance = dis;
                          index = j;
                      }
                  }

                   //先將當前點從原先的簇中刪除
                   map<int,vector<Node> >::iterator iter;
         //搜索所有的簇
                   for(iter = cluster.begin();iter != cluster.end();++iter)
                   {

                vector<Node>::iterator node_iter;
                      bool jump_flag = false;
                      //對每個簇中的vector進行搜索
                      for(node_iter = iter->second.begin();node_iter != iter->second.end();node_iter++)
            　　　　  　{
          　　　　　　   if(*node_iter == data[i])
          　　　　　　　 {
                             //如果當前點就在更新的簇中，則忽略后面的操作
        　　　　　　         if(index == iter->first)
                            {
                     　　　　　　continue_flag = true;
                             }
                             else
                             {
　　　　　　                     iter->second.erase(node_iter);
                             }
          　　　       　　 jump_flag = true;
               　　　　  　　break;
             　　　　　　　}
              　　}
              　　　　　　if(jump_flag)
             　　　　　　 {
             　　　　　　　　break;
              　　　　　　}
                   　　}

                   if(continue_flag)
           　　　　{
                  　　 continue;
                   }
                   //將當前點插入到中心點所對應的簇中
                   //查看中心點是否已經存在map中
                  bool insert_flag = true;
                  for(iter = cluster.begin(); iter != cluster.end();++iter)
                  {

                     if(iter->first == index)
             　　　　　{
                     　　   iter->second.push_back(data[i]);
                       　　 insert_flag = false;
                　　　　　　　break;
              　　　　　}
                  }
                  //不存在則創建新的元素對象
                  if(insert_flag)
                  {
                      vector<Node> cluster_node_vector;
                      cluster_node_vector.push_back(data[i]);
                      cluster.insert(make_pair(index,cluster_node_vector));
                  }
             }
  }

  double KMean::Kdistance(Node active,Node other)
  {
         return sqrt(pow((active.pos_x-other.pos_x),2) + pow((active.pos_y - other.pos_y),2) + pow((active.pos_z - other.pos_z),2));
  }

  Node KMean::GetMean(int cluster_index)
  {
      //對傳入的參數進行判斷，查看是否越界
      if( cluster_num <0 || unsigned (cluster_index) >= mean_nodes.size() )
      {
          Node new_node;
          new_node.pos_x = -1.0;
          new_node.pos_y = -1.0;
          new_node.pos_z = -1.0;
          return new_node;
      }

      //求出簇中所有點的均值
      Node sum_node;
      Node aver_node;
        for(int j = 0;j < cluster[cluster_index].size();j++)
         {
         　　sum_node.pos_x += cluster[cluster_index].at(j).pos_x;
            sum_node.pos_y += cluster[cluster_index].at(j).pos_y;
         　　sum_node.pos_z += cluster[cluster_index].at(j).pos_z;
     　　　}
         aver_node.pos_x = sum_node.pos_x*1.0/ cluster[cluster_index].size();
         aver_node.pos_y = sum_node.pos_y*1.0 / cluster[cluster_index].size();
         aver_node.pos_z = sum_node.pos_z*1.0 / cluster[cluster_index].size();

       //找到與均值最近的點
      double min_dis = MAXDISTANCE;
      Node new_mean_doc;

      for(unsigned int i  = 0;i< cluster[cluster_index].size();i++)
      {
            double dis = Kdistance(aver_node,cluster[cluster_index].at(i));
            if(min_dis > dis)
            {
                  min_dis = dis;
                  new_mean_doc = cluster[cluster_index].at(i);
            }
      }
      return new_mean_doc;
  }

  void KMean::NewCluster()//確定新的中心點
  {
       for (unsigned int i = 0;i < mean_nodes.size();i++)
       {
            Node new_node =GetMean(i);
            mean_nodes[i] = new_node;
       }
       ClusterProcess();
  }

 void KMean::Star()
 {
     for (int i = 0;i<100;i++)
     {
         NewCluster();
         cout << "no:"<< i<<endl;
         for(int j = 0;j < mean_nodes.size();j++)
     {
         cout << cluster[j].size()<<endl;
     }

     }
 }

#include <iostream>
#include <vector>
#include "k-mean.h"
#include <ctime>
#include <cstdlib>

using namespace std;
int main()
 {
     srand((int) time(0));

     vector<Node> data;

     for(int i =0;i<100;i++)
     {
          Node node;
          node.pos_x = (random() % 17 )*1.2;
          node.pos_y = (random() % 19 )*1.2;
          node.pos_z = (random() % 21) *1.2;
          data.push_back(node);
     }

     KMean kmean(3,data);
     kmean.Star();

     return 0;
 }