Глава_07

Назад | Начало урока | Вперед
Содержание

Глава 6

Кластеризация

Подсказка

Принцип кластеризации и результат ее работы можно наглядно увидеть выведя коллекцию точек на плоскость. Для того, чтобы вывести точки на плоскость, воспользуемся уже готовым кодом, взятым по большей части из урока 9 книги Чепмена "Visual C++.NET". Этот код мы уже использовали в уроке 4 когда выводили на экран линию Коха, салфетку Серпинского и Драконову ломаную. Это удобная конструкция, в которой имеется главное окно, оно у нас является управляющим, и дочернее окно. Дочернее окно выступает в роли холста для рисования.

Структура Point, а так же функция Distance(), и шаблонные функции Centroid() и Cluster() останутся без изменений. А вызов функции Clusters() сделаем в новой функции Clusters_01. Это по сути функция рисования точек. Точки будут выглядеть в виде маленьких цветных кружков. Каждый кластер будет состоять из кружков своего цвета.

В функцию будем передавать контекст для рисования, начальный цвет, число точек и число кластеров. В данной конкретной реализации функции для простоты зададим жестко - 200 точек и 8 кластеров. Координаты точек, которые будут сохраняться в списке List будут находиться в диапазонах X от 0 до 240, Y от 0 до 120. Это как раз в области нашего холста.

Конечно данные считанные из текстового файла дали бы более реалистичные результаты. Но алгоритм кластеризации работает и в нашем случае.

Функция показывающая работу алгоритма кластеризации. Рисует точки в окне. Каждый кластер - своим цветом.



void CPaintDlg::Clusters_01(CPaintDC *cdc, int iColor, int numPoint, int numClusters, int x, int y){
	srand(time(NULL));      // Set seed for random numbers.

	int N, M;

	N = 200;

	M = 8;

	list lp;

	for(int i = 0; i < N; i++){
		Point p;

		p.x = rand_0toN1(240);

		p.y = rand_0toN1(120);

		lp.push_back(p);
	}

	 vector<list<Point> > Clusters = Cluster(lp.begin(), lp.end(), M);
	  for(i = 0; i < M; i++)

		  for(list<Point>::iterator p = Clusters[i].begin(); p!= Clusters[i].end();p++){

			  CBrush *pOldBrush2 = NULL;  

			  CBrush brSolidBrush2(m_crColors[i]);

			  pOldBrush2 = cdc->SelectObject(&brSolidBrush2);

	          Point  pt;

			  pt.x = p->x;

			  pt.y = p->y;

			  cdc->Ellipse(pt.x, pt.y, pt.x+8, pt.y+8);
		  }

}

Функция Clusters_01 будет вызвана в функции DrawLine() в ответ на выбор пользователем радиокнопки с надписью "Кластер" в управляющем окне. Сама функция DrawLine() вызывается в функции OnPaint(). Вы можете выбрать цвет, в управляющем окне, при этом функция кластеризации будет вызываться вновь и точки появятся в новых местах холста, но при этом они будут распределены в кластеры.


// PaintDlg.cpp : implementation file

//


#include "stdafx.h"

#include "Graphics.h"

#include "PaintDlg.h"

#include "GraphicsDlg.h" //первое диалоговое окно 

// CPaintDlg dialog


IMPLEMENT_DYNAMIC(CPaintDlg, CDialog)

const COLORREF CPaintDlg::m_crColors[8] = {
 
	RGB( 0, 0, 0), // Black 

	RGB( 0, 0, 255), // Blue 

	RGB( 0, 255, 0), // Green 

	RGB( 0, 255, 255), // Cyan 

	RGB( 255, 0, 0), // Red 

	RGB( 255, 0, 255), // Magenta 

	RGB( 255, 255, 0), // Yellow 

	RGB( 255, 255, 255) // White 
}; 

CPaintDlg::CPaintDlg(CWnd* pParent /*=NULL*/)

	: CDialog(CPaintDlg::IDD, pParent)
{}



CPaintDlg::~CPaintDlg()
{

}

void CPaintDlg::DoDataExchange(CDataExchange* pDX)
{

	CDialog::DoDataExchange(pDX);

}

BEGIN_MESSAGE_MAP(CPaintDlg, CDialog)

	ON_WM_PAINT()

END_MESSAGE_MAP()


//------------------

int CPaintDlg::rand_0toN1(int n) {

    return rand() % n;
}


//------------

 struct CPaintDlg::Point{
	  int x, y;
  };


//----------------

  double CPaintDlg::Distance(const Point& p1, const Point p2){
	  return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));

  }


//------------------------------

  template <class Iterator> 

	  Iterator::value_type Centroid(const Iterator begin, const Iterator end){

	  //	double minDist = numeric_limits::max();

	  double MinDist = 5000;

	  Iterator::value_type Element;
  
	  for(Iterator current = begin; current != end; current++){

		  double Dist = 0;

		  for(Iterator c = begin; c != end; c++)

			  Dist += Distance(*current, *c);


		  if(Dist < MinDist) {

			  MinDist = Dist; 

			  Element = *current;
		  }

	  }

	  return Element;

  };




//--------------------------------


  template <class Iterator>
 
vector<list <typename Iterator::value_type> > Cluster(const Iterator begin, const Iterator end, int M){

       // создать М кластеров

	vector<list<Iterator::value_type> > Clusters(M);

      // приписать каждый элемент коллекции (объект) случайному кластеру

      //точнее заполнить кластера случайными значениями

     for(Iterator c = begin; c != end; c++)

		Clusters[rand_0toN1(M)].push_back(*c);


	 //массив центроидов


      vector<Iterator::value_type> Centroids(M);

	  bool modified;

	do{

		//заполним массив центроидов данными (собственно в каждом элементе

		// массива центроидов будет одно значение)

		for(int z = 0; z < M;z++){

			Centroids[z] = Centroid(Clusters[z].begin(), Clusters[z].end());

		}

		modified = false;

		vector<list<Iterator::value_type> > NewClusters(M);

		for(int OldCl = 0; OldCl < M; OldCl++){

			for(Iterator c =Clusters[OldCl].begin(); c!= Clusters[OldCl].end(); c++){
				double MinDist = 50000;

				int ClusterNo;

				for(int centroid = 0; centroid < M; centroid++){

					double Dist = Distance(*c, Centroids[centroid]);

					if(Dist < MinDist){

						MinDist = Dist; 

						ClusterNo = centroid;
					}

				}

			if(ClusterNo != OldCl) modified = true;


				NewClusters[ClusterNo].push_back(*c);
			}

		}

			Clusters = NewClusters;


	}//do

	while(modified);//пока происходят изменения


	return Clusters;
}

 


//--------------------------

void CPaintDlg::Clusters_01(CPaintDC *cdc, int iColor, int numPoint, int numClusters, int x, int y){

	srand(time(NULL));      // Set seed for random numbers.

	int N, M;

	N = 200;

	M = 8;

	list lp;

	for(int i = 0; i < N; i++){
		Point p;

		p.x = rand_0toN1(240);

		p.y = rand_0toN1(120);

		lp.push_back(p);
	}

	 vector<list<Point> > Clusters = Cluster(lp.begin(), lp.end(), M);
	  for(i = 0; i < M; i++)

		  for(list<Point>::iterator p = Clusters[i].begin(); p!= Clusters[i].end();p++){

			  CBrush *pOldBrush2 = NULL;  

			  CBrush brSolidBrush2(m_crColors[i]);

			  pOldBrush2 = cdc->SelectObject(&brSolidBrush2);

	          Point  pt;

			  pt.x = p->x;

			  pt.y = p->y;

			  cdc->Ellipse(pt.x, pt.y, pt.x+8, pt.y+8);
		  }

}

////////////////////////////


///////////////////////////


void CPaintDlg::DrawLine(CPaintDC* pdc, int iColor, int num)
{

    // Declare and create the pens

    CPen pnSolidPen (PS_SOLID, 1, m_crColors[iColor]);
    
    // Get the drawing area

    CRect rRect;

    GetClientRect(rRect);

    rRect.NormalizeRect();

    // Calculate the distance between each of the lines

    CPoint ptStart;

    CPoint ptEnd;

    int iDist = rRect.Height() / 8;

    CPen* pOldPen = NULL;

    // Specify the starting points

    ptStart.y = rRect.top;

    ptStart.x = rRect.left;

    ptEnd.y = ptStart.y;

    ptEnd.x = rRect.right;


        pOldPen = pdc->SelectObject(&pnSolidPen);

        // Move down to the next position

        ptStart.y = ptStart.y + 8*iDist;

        ptEnd.y = ptStart.y;

		switch(num){

			case 0: Clusters_01(pdc, iColor, 20, 5, (ptStart.x+20), (ptStart.y-30));

				break;

			case 1: 

				break;

			case 2: 

				break;

			default : break;
		}

    // Select the original pen

    pdc->SelectObject(pOldPen);
}



//-------------------------

void CPaintDlg::OnPaint()
{
	CPaintDC dc(this); // device context for painting

	// Get a pointer to the parent window

    CGraphicsDlg *pWnd = (CGraphicsDlg*)GetParent();

    // Do we have a valid pointer?

       //Указатель указывает на ранее созданный объект?

    if (pWnd)

    {
            // What we drawing?

			if (pWnd->m_iShape == 0)  

				DrawLine(&dc, pWnd->m_iColor, 0);

			if (pWnd->m_iShape == 1) 

				DrawLine(&dc, pWnd->m_iColor, 1);

			if (pWnd->m_iShape == 2) 

                DrawLine(&dc, pWnd->m_iColor, 2);

    }

    // Do not call CDialog::OnPaint() for painting messages
}

Результат

Подсказка

Исходники и exe-файл программы находятся ЗДЕСЬ

Назад | Начало урока | Вверх | Вперед
Содержание