Скачиваний:
16
Добавлен:
01.05.2014
Размер:
10.52 Кб
Скачать
// TMergeHull.cpp: implementation of the TMergeHull class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ConvexHull.h"
#include "TMergeHull.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
#include "TEdge.h"



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

template<class T>
void swap(T &a, T &b)
{
 T t = a;
 a = b;
 b = t;
}


void TMergeHull::SetView(CConvexHullView* view)
{
	this->view = view; 
}
void TMergeHull::SetDocument(CConvexHullDoc* doc)
{
	this->doc = doc;
}
TMergeHull::TMergeHull()
{
	InpData = NULL;
	CountPoly = 0;
	First = NULL;
	Last = NULL;

}

TMergeHull::~TMergeHull()
{

}


int TMergeHull::Generate(TGVector* Vec, GenInfo gi)
{
   srand((unsigned)time(NULL));

   for (int i = 0; i < gi.count; i++) {
     double A = (double)rand()/RAND_MAX;
     double B = (double)(gi.max_x  - gi.min_x );
     double C = (double)gi.min_x;
     double randX = A*B+C;  
     A =(double)rand()/RAND_MAX;
     B= (double)(gi.max_y  - gi.min_y );
     C = (double)gi.min_y ;
     double randY = A*B+C;
     TPoint* point = new TPoint(randX, randY);  
     Vec->push_back(point);
   }
   return 0;
}


void selectionSort(TPoint* a[], int n, int (*cmp)(TPoint*,TPoint*))
{ //int t;
  
  for (int i = 0; i < n-1; i++) {
    int min = i;
    for (int j = i+1; j < n; j++) {
      if ((*cmp) (a[j], a[min]) < 0) {
//        t= j;
     //   min = j;
       TPoint* tmp = a[min];
       a[min]=a[j];
       a[j]=tmp;
       tmp=a[min];
      }
     // swap(a[j], a[min]);
    //  min=t;
    }
  }  
}  



template <class T>
void merge(T x[], int l, int m, int r, int (*cmp)(T, T))
{
    T *a = x + l;
    T *b = x + m + 1;
    T *c = new T[r - l + 1];
    int aindx = 0, bindx = 0, cindx = 0;
    int alim = m - l + 1, blim = r - m;
    while ((aindx < alim) && (bindx < blim))
      if ((*cmp)(a[aindx], b[bindx]) < 0)
        c[cindx++] = a[aindx++];
      else
        c[cindx++] = b[bindx++];
    while (aindx < alim)
      c[cindx++] = a[aindx++];
    while (bindx < blim)
      c[cindx++] = b[bindx++];
    aindx = cindx = 0;
    for (; aindx <= r ;) {
      a[aindx] = c[cindx];
      aindx++;
      cindx++;
    }
    delete c;
};

template <class T>
void mSort(T a[], int l, int r, int (*cmp)(T, T))
{
    if (l < r) {
      int m = (l + r) / 2;
      mSort(a, l, m, cmp);
      mSort(a, m+1, r, cmp);
      merge(a, l, m, r, cmp);
    }

};



template <class T>
void mergeSort(T* a, int n, int (*cmp)(T, T))
{
    mSort(a, 0, n, cmp);
};


Vertex* leastVertex(TPolygon &p, int (*cmp)(TPoint*, TPoint*))
{
     Vertex *bestV = p.v();
     p.advance(CLOCKWISE);
     for (int i = 1; i < p.size(); p.advance(CLOCKWISE), i++)
       if ((*cmp)(p.v(), bestV) < 0)
         bestV = p.v();
     p.setV(bestV);
     return bestV;
}


//Предусловие: окно *р проинадлежит ближней к s цепочке
//p -- выпуклый пол-н
void supportingLine(TPoint &s, TPolygon *p, int side)
{
    //если ищется левая (правая) касательная, то пол-н *p просматривается 
    //по (против) часовой стрелке
    int rotation = (side==LEFT) ? CLOCKWISE : COUNTER_CLOCKWISE;
    //*a -- окно *p
    Vertex *a = p->v();
    //*b -- сосед *a по (против) часовой стрелке
    Vertex *b = p->neighbor(rotation);
    //c -- взаимное положение точки s и окна пол-на *p
    int c = b->classify(s, *a);
    //пока окно пол-на *p не 
    while ((c == side) || (c == BEYOND) )
   // || (c == BETWEEN) ) 
{
       p->advance(rotation);
       a = p->v();
       b = p->neighbor(rotation);
       c = b->classify(s, *a);
    }                               
}



void TMergeHull::Run(TGVectorCollect* input_data, 
                     TGVectorCollect* intermed_data,
                     TGVectorCollect* output_data,
                     TRunMode run_mode) 
{
    _RunMode = run_mode;
    PointCount = 0;
    for (unsigned i = 0; i < ((*input_data)[INP_POINTS])->size(); i++) {
      if (G_POINT == (*(*input_data)[INP_POINTS])[i]->GetType())
        PointCount++; 
    }
    InpData = new TPoint*[PointCount];

    int point_find = 0;

    for (i = 0; point_find < PointCount; i++) {
      if (G_POINT == (*(*input_data)[INP_POINTS])[i]->GetType()){
        point_find++;
        InpData[i] = (TPoint*) (*(*input_data)[INP_POINTS])[i];
      }
    }
    IntermedData = intermed_data;
    selectionSort(InpData, PointCount, leftToRightCmp);
	
	int m=0;
    //mergeSort(InpData, PointCount, leftToRightCmp);
    if ( 0 < PointCount) {
        
		(*output_data)[OUTP_POLYGONS]->push_back(mHull(InpData, PointCount));//!!!!!!!!!!!!!leaks is here
		
	   (*IntermedData)[INTERM_POLYGONS]->pop_back();
	   (*IntermedData)[INTERM_POLYGONS]->clear();

    }   
	delete InpData;


	////////////////////////////GARBAGE/////////////////////////////////////
	if (CountPoly>0){
		PolygonContainer* ptr = Last;
		PolygonContainer* tempCont = NULL;
		TPolygon* tmp = NULL;
		for (i =0 ; i<CountPoly-1;i++){
				tmp = ptr->Item;
				if (tmp) delete tmp;
				tempCont = ptr;
				ptr = ptr->Prev;
				delete tempCont;
				
		}
		delete ptr;	
		CountPoly=0;		
	}
	////////////////////////////////////////////////////////////////////////
}



TPolygon* TMergeHull::mHull(TPoint *p[], int n)
{
    if (1 == n) {
//      TRACE("mHULL\n");
	  TPolygon*  q =  new TPolygon();
      q->insert(*p[0]);
      (*IntermedData)[INTERM_POLYGONS]->push_back(q);
	   

	//////////////////////////////////////////////////////////////////////
	//Чтобы потом очистить память
	if (CountPoly){
		Last->Next = new PolygonContainer();
		Last->Next->Prev = Last;
		Last = Last->Next;
		Last->Item = q;
		CountPoly++;
	}
	else{
		First =  new PolygonContainer();
		Last = First;
		Last->Item = q;
		CountPoly++;
	}
	//////////////////////////////////////////////////////////////////////	
	  
	
	  StepDone();
      
	  return q;
    }
    else {
      int m = n / 2;
      TPolygon *L = mHull(p, m);
	  //(*IntermedData)[INTERM_POLYGONS]->push_back(L);
      //StepDone();
	 

      TPolygon *R = mHull(p + m, n - m);
      //(*IntermedData)[INTERM_POLYGONS]->push_back(R);
      //StepDone();
	  
	


		
	  
      TPolygon* result = merge(L, R);
	  //delete (*(*IntermedData)[INTERM_POLYGONS])[0];
	  (*IntermedData)[INTERM_POLYGONS]->pop_back();	


	  
      
	  StepDone();
      
      return result;
    }
}




TPolygon* MySplit(Node* l_up, Node* l_down, Node* r_up, Node* r_down, TPolygon* &L, TPolygon* &R)
{
  Node* tmp;
  for (tmp = l_up->_next; l_up->_next != l_down; tmp = l_up->_next)
  {
    l_up = tmp->_next;
    delete tmp;
  }

  for (tmp = r_down->_next; r_down->_next != r_up; tmp = r_down->_next)
  {
    r_down = tmp->_next;
    delete tmp;
  }
 
  l_up->_next = r_up;
  r_up->_prev = l_up;

  r_down->_next = l_down;
  l_down->_prev = r_down;
  R = NULL;
  L=NULL;
  return new TPolygon((Vertex*)l_up);
}







//слияние выпуклых полигонов (L строго левее, чем R)
TPolygon * TMergeHull::merge(TPolygon * L, TPolygon * R)
{
    Vertex *l1, *r1, *l2, *r2;

    Vertex *vl = leastVertex(*L, rightToLeftCmp);
    Vertex *vr = leastVertex(*R, leftToRightCmp);

    brige(L, R, l1, r1, UPPER);

    TEdge* edge;
    edge = new TEdge(*l1,*r1);
    (*IntermedData)[INTERM_UP_BRIGES]->push_back(edge);

    
//!!	StepDone();
//    delete (*(*IntermedData)[INTERM_UP_BRIGES])[0];
//    (*IntermedData)[INTERM_UP_BRIGES]->pop_back();




    L->setV(vl);
    R->setV(vr);
    brige(L, R, l2, r2, LOWER);

    edge = new TEdge(*l2,*r2);
    (*IntermedData)[INTERM_DOWN_BRIGES]->push_back(edge);

    
//!!	StepDone();

    
	delete (*(*IntermedData)[INTERM_UP_BRIGES])[0];
    (*IntermedData)[INTERM_UP_BRIGES]->pop_back();

    delete (*(*IntermedData)[INTERM_DOWN_BRIGES])[0];
    (*IntermedData)[INTERM_DOWN_BRIGES]->pop_back();

    //MySplit(l1, l2, r1, r2, L, R); 
    //delete R;
	L->setV(l1);
    L->split_ver2(r1);
	

    R->setV(r2);
	//delete  
		R->split(l2)->Destroy() ;

    return L;
    //return R;
}





int leftToRightCmp(TPoint* a, TPoint* b)
{
  if (*a > *b)
    return 1;
  else
    if (*a < *b)
      return -1;
  return 0;
}

void TMergeHull::StepDone(void)
{
    if (BY_STEP == _RunMode) {
      _Stay = true;
      //while (_Stay) {
        //Application->ProcessMessages();
      //}
	  view->RedrawWindow(); 
	
	  ::WaitForSingleObject(g_eventContinue, INFINITE); 
    }

}

void TMergeHull::brige(TPolygon * L, TPolygon * R, Vertex* & vl, Vertex* & vr, int type)
{
	int countB;
	countB=0;

    int sides[2] = {LEFT, RIGHT};
    int indx = (type == UPPER) ? 0 : 1;
    TEdge *edge, *tmp=NULL;



    int BrigeType = (type == UPPER) ? INTERM_UP_BRIGES : INTERM_DOWN_BRIGES;
    do {
      //запоминаем положение окон полигонов
      vl = L->v();
      vr = R->v();
      //ищем положение окна пол-на L, из которого выходит левая 
      //касательная к R
      supportingLine(L->point(), R, sides[indx]);

      edge = new TEdge(L->point(), R->point());
      (*IntermedData)[BrigeType]->push_back(edge);

      
		
	if (edge!=tmp)
		StepDone();
	tmp = edge;


      
	  delete (*(*IntermedData)[BrigeType])[0];
      (*IntermedData)[BrigeType]->pop_back();
      
	  
	  
	  //ищем положение окна пол-на R, из которого выходит правая
      //касательная к L
      supportingLine(R->point(), L, sides[1-indx]);

      edge = new TEdge(L->point(), R->point());
      (*IntermedData)[BrigeType]->push_back(edge);

		
	if (edge!=tmp)
		StepDone();
	tmp = NULL;

      
	  
	  delete (*(*IntermedData)[BrigeType])[0];
      (*IntermedData)[BrigeType]->pop_back();
    }
      // пока положение какого-либо окна не изменилось при поиске касательной 
    while ((vl != L->v()) || (vr != R->v()));
}



int rightToLeftCmp(TPoint* a, TPoint* b)
{
    return leftToRightCmp(b, a);
}


void TMergeHull::NextStep(TRunMode run_mode)
{
    _RunMode = run_mode;
    _Stay = false;
}


void TMergeHull::setRunMode(TRunMode mode)
{
	_RunMode = mode;
}

Соседние файлы в папке ConvexHull_1