myconvexhull.cpp

凸包算法在VC6下实现

// MyConvexHull.cpp: implementation of the CMyConvexHull class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "convexHull.h"
#include "MyConvexHull.h"
#include "convexHullView.h"
//#include "convexHullView.h"

#include <iostream>
using namespace std;

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

extern CString pDataFileName; 
extern COLORREF nodeColor, lineColor;
extern int nodeType;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMyConvexHull::CMyConvexHull()
{
	N = 0;
	memset(V, 0 , sizeof(V));
	back = 0;
	front = 0;
}

CMyConvexHull::~CMyConvexHull()
{

}
int CMyConvexHull::cross(Nodes a, Nodes b, Nodes c)
{
	int x_1 , x_2 , y_1 , y_2 , d;
	x_1 = b.x - c.x; x_2 = a.x - b.x;
	y_1 = b.y - c.y; y_2 = a.y - b.y;
	d = x_1*y_2 - x_2*y_1;
	if (d > 0) return 1;
	else if (d < 0) return -1;
	else return 0;
}

bool CMyConvexHull::cmp(Nodes a, Nodes b)
{
	if (a.y < b.y ) return true;
	if (a.y > b.y) return false;
	if (a.x < b.x) return true;
	return false;
}


void CMyConvexHull::Merge(int low, int mid, int high)
{
	int i = low , j = mid+1 , ptr = low;
	while (i <= mid && j <= high) {
		if (cmp (node[i] , node[j]) == true) temp[ptr++] = node[i++];
		else temp[ptr++] = node[j++];
	}
	while (i <= mid) temp[ptr++] = node[i++];
	while (j <= high) temp[ptr++] = node[j++];
	memcpy (&node[low] , &temp[low] , (high-low+1)*sizeof(Nodes));
	return ;
}

void CMyConvexHull::MergeSort(int low, int high)
{
	int mid = (low + high) >> 1;
	if (low < high) {
		MergeSort (low , mid);
		MergeSort (mid+1 , high);
	}
	Merge (low , mid , high);
	return ;

}

void CMyConvexHull::right_scan(int i)
{
	int result;
	while (result = cross (node[i] , node[V[front]] , node[V[front-1]]) == -1) front--;
    if (result = cross (node[i] , node[V[front]] , node[V[front-1]]) == 0) --front;  ////去除凸包边上的点;
	return ;
}

void CMyConvexHull::left_scan(int i)
{
	int result;
	while (result = cross (node[i] , node[V[back]] , node[V[back+1]]) == 1) back++;
	if (result = cross (node[i] , node[V[back]] , node[V[back+1]]) == 0) ++back; //去除凸包边上的点;
	return ;
}

void CMyConvexHull::Solve()
{
	int ptr = 0 , cross_r , cross_l , count;
	back = MaxNode; front = MaxNode-1;
	MergeSort (0 , N-1);
	if (N == 0) return ; V[++front] = ptr++;
	if (N == 1) return ; V[++front] = ptr++;
	count = 2;
	while (ptr < N && count <= 2) {  // 生成栈底凸包;
		cross_r = cross (node[ptr] , node[V[front]] , node[V[front-1]]);
		if (cross_r == 1) { V[++front] = ptr; V[--back] = ptr; ptr++; count++; continue ; }
		if (cross_r == -1) { cross_r = V[front]; V[front] = V[front-1]; V[front-1] = cross_r; V[++front] = ptr; V[--back] = ptr; ptr++; count++; continue ; }
		if (cross_r == 0) V[front] = ptr++;  //去除凸包上的点;
		// if (cross_r == 0) V[++front] = ptr++; //保留凸包上的点;
	}
	
	while (ptr < N) { 
		cross_r = cross (node[ptr] , node[V[front]] , node[V[front-1]]);
		cross_l = cross (node[ptr] , node[V[back]] , node[V[back+1]]);
		if (cross_r <= 0 && cross_l >= 0) {  // top;
			left_scan (ptr);
			right_scan (ptr);
			V[++front] = ptr; V[--back] = ptr; ptr++;
		} 
		else if (cross_r >= 0 && cross_l <= 0) ptr++; // inside;
		else if (cross_r >= 0 && cross_l >= 0) { // left side;
			left_scan (ptr);
			V[--back] = ptr; V[++front] = ptr; ptr++;
		}
		else if (cross_r <=0 && cross_l <= 0) { // right side;
			right_scan (ptr);
			V[--back] = ptr; V[++front] = ptr; ptr++;
		}
	}
	return ;
}

void CMyConvexHull::InputData(CString pFileName)
{
    CFile dataFile;
	dataFile.Open(pDataFileName, CFile::modeRead);
	dataFile.SeekToBegin();
    dataFile.Read(&N,sizeof(int));
//	char ch;
	for(int i=0; i<N; i++)
	{
       dataFile.Read(&node[i].x, sizeof(int));
//	   dataFile.Read(&ch, sizeof(char));
	   dataFile.Read(&node[i].y, sizeof(int));
//	   dataFile.Read(&ch, sizeof(char));
	}
    dataFile.Close();

}
int CMyConvexHull::GetN()
{
	return N;
}
void CMyConvexHull::Operation()
{
//	CClientDC dc((CConvexHullView*)GetParent());
//	CPen pen(0, 2, nodeColor);
/*	dc.SelectObject(&pen);
	int i;
	//绘点
	if(nodeType == 0)
	{
		for(i=0; i<N; i++)
		{
			
		}
	}
	else if(nodeType == 1)
	{
		for(i=0; i<N; i++)
		{
			
		}
	}
    //绘线

//	cout<<back<<" "<<(front-back)<<endl;
    dc.MoveTo(node[V[back]].x, node[V[back]].y);
	for(i=back+1;i<front;i++){
		dc.LineTo(node[V[i]].x,node[V[i]].y);
		dc.MoveTo(node[V[i]].x,node[V[i]].y);		
	}
	dc.MoveTo(node[V[back]].x,node[V[back]].y);	*/
}