/************************************************************************/
/*                                                                      */
/* FILE NAME : SYS2ARPJ.C                                               */
/*                                                                      */
/* STAR DECOMPOSITION OF POLYGON                                        */
/*                                                                      */
/* HASAN TIMUCIN OZDEMIR                                                */
/*                                                                      */
/*                                                                      */
/************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
#include<sys/time.h>
#include<reduce.h>
#include<mpl.h>



#define TRUE   1
#define true   1
#define FALSE  0
#define false  0

#define Square(x) ((x)*(x))
#define XOR(a,b)  (((a)==(b)?0:1))

struct point
{ float x;
  float y;
  struct KERPointNode *KerPair;
};

struct line
{ struct point first;
  struct point next;
};

struct lineNode
{  struct line MyLine;
   struct lineNode *NextEle;
};

struct VisiblePolyEle
{  int index;
   struct VisiblePolyEle *NextEle;
};

struct PointNode
{ struct point MyPoint;
  int MyIndex;
  struct VisiblePolyEle *VisibilityPolyList;
  struct PointNode *NextEle;
};

struct BaseTriangleEle   /* triangle (first,middle,last) */
{  int first;
   int middle;
   int last;
   struct BaseTriangleEle *NextEle;
};

struct SubPolyNode
{  int from;
   int to;
   struct BaseTriangleEle *BaseTrianglesList;
   struct SubPolyNode *NextEle;
};

struct MDElement
{  int from;
   int to;
   struct StarPolygon *RealMDList;
   int NumberOfRealList;
   struct StarPolygon *PseudoMDList;
   int NumberOfPseudoList;
};

struct NewMDElement
{  struct StarPolygon *RealMDList;
   int NumberOfRealList;
};

struct StarPolygon
{ struct StarPolygon *NextEle;
  int numberOfPoints;
  int *elements;
};

struct KERPointNode
{ struct point MyPoint;
  int MyIndex;
  struct VisiblePolyEle *VisibilityPolyList;
  struct KERPointNode *NextEle;
  int *component_num;
  struct StarPolygon **MinDecompList;
  int *psecomp_num;
  struct StarPolygon **PseudoDecompList;
};

typedef struct point Point;

typedef struct line Line;

struct point orij1 = {250,250};

struct lineNode *InteriorLines=NULL;

struct KERPointNode *KER=NULL;

struct PointNode *PolygonVertexVisiblityList=NULL;

struct SubPolyNode *SubPolygonList=NULL;

struct NewMDElement *P;

/********** Memory Allocation / Deallocation Routines   *********************/

void DeallocateStarPoly(struct StarPolygon *Ele)
{ if(Ele->elements)
	 free(Ele->elements);  /* deallocate the set */
  free(Ele);               /* deallocate the structure */
}/* end of DeallocateStarPoly() */

void DeallocateStarPolygonList(struct StarPolygon *Ele)
{ 
  return;
} /* end of DeallocateStarPolygonList() */

void AddInteriorLines(struct point from,struct point to)
{ struct lineNode *NewEle;
  if((NewEle=(struct lineNode *)calloc(1,sizeof(struct lineNode)))!=NULL)
  { NewEle->MyLine.first = from;
	NewEle->MyLine.next = to;
	NewEle->NextEle = InteriorLines;
	InteriorLines = NewEle;
  }/* end of if */
}/* end of AddInteriorLines() */

void DeallocateInteriorLines()
{ struct lineNode *ptr;
  struct lineNode *next;
  int old;
  ptr = InteriorLines;
  while(ptr!=NULL)
  { next = ptr ->NextEle;
	free(ptr);
	ptr = next;
  }/* end of while */
}/* end of DeallocateInteriorLines() */

void DefineSubPolygonList()
/* Put one dummy element;
*/
{ struct SubPolyNode *NewEntry;
  if((NewEntry=(struct SubPolyNode *)calloc(1,sizeof(struct SubPolyNode)))!=NULL)
  { NewEntry->from = 0;
	NewEntry->to   = 0;
	NewEntry->NextEle = SubPolygonList;
	NewEntry->BaseTrianglesList = NULL;
	SubPolygonList = NewEntry;
  }/* end of if */
}/* end of DefineSubPolygonList() */

void AddSubPolygonList(int vi, int vj)
{ struct SubPolyNode *NewEntry;
  struct SubPolyNode *ptr;
  struct SubPolyNode *previous;
  int ContSearch=TRUE;
  if((vj-vi)>1)
  { if((NewEntry=(struct SubPolyNode *)calloc(1,sizeof(struct SubPolyNode)))!=NULL)
	{ NewEntry->from = vi;
	  NewEntry->to   = vj;
	  NewEntry->NextEle = NULL;
	  NewEntry->BaseTrianglesList = NULL;

	  previous = ptr = SubPolygonList ;

	  while(ptr!=NULL&&ContSearch)
	  {
		if((ptr->to-ptr->from)<(vj-vi))
		{  previous = ptr;
		   ptr = previous->NextEle;
		}
		else ContSearch=FALSE;
	  }/* end of while() */

	  if(ContSearch&&SubPolygonList==NULL) SubPolygonList = NewEntry;
	  else
		{ NewEntry->NextEle = previous->NextEle;
		  previous->NextEle = NewEntry;
		}
	}/* end of if */
  }/* end of if */
}/* end of AddSubPolygonList() */

void AddBaseTriangle(struct SubPolyNode *Pnt,int idx1, int idx2, int idx3)
{ struct BaseTriangleEle *NewVPEle;
  if((NewVPEle=(struct BaseTriangleEle *)calloc(1,sizeof(struct BaseTriangleEle )))!=NULL)
  { NewVPEle->NextEle = Pnt->BaseTrianglesList;
	Pnt->BaseTrianglesList = NewVPEle;
	NewVPEle->first  = idx1;
	NewVPEle->middle = idx2;
	NewVPEle->last   = idx3;
	/*
	printf("\n %d,%d,%d is Base Triangle",NewVPEle->first,NewVPEle->middle,NewVPEle->last);
	*/
  }/* end of if */
  else
	printf("\n Error : AdddBaseTriangle not enough memory \n");
}/* end of AddBaseTriangle() */

void DeallocateBaseTriangleList(struct SubPolyNode *Pnt)
{ struct BaseTriangleEle *ptr;
  struct BaseTriangleEle *next;
  int old;
  ptr = Pnt->BaseTrianglesList;
  while(ptr!=NULL)
  { next = ptr ->NextEle;
	free(ptr);
	ptr = next;
  }/* end of while */
}/* end of DeallocateBaseTriangleList() */

void DeallocateSubPolyList()
{ struct SubPolyNode *ptr;
  struct SubPolyNode *next;
  int old;
  ptr = SubPolygonList;
  while(ptr!=NULL)
  { next = ptr ->NextEle;
	DeallocateBaseTriangleList(ptr);
	free(ptr);
	ptr = next;
  }/* end of while */
}/* end of DeallocateSubPolyList() */

struct KERPointNode *AddPointToKER(struct point newPoint,int max, int MyInd)
{ struct KERPointNode *NewEntry;
  int i;
  int retval=0;
  if((NewEntry=(struct KERPointNode *)calloc(1,sizeof(struct KERPointNode)))!=NULL)
  {	if((NewEntry->component_num = (int *)calloc(max*max,sizeof(int) )) !=NULL)
	{
	  NewEntry->MinDecompList = (struct StarPolygon **) calloc(max*max,sizeof(struct StarPolygon *));

	  if((NewEntry->MinDecompList)!=NULL)
	  { if((NewEntry->psecomp_num = (int *)calloc(max*max,sizeof(int) )) !=NULL)
		{
		  NewEntry->PseudoDecompList = (struct StarPolygon **) calloc(max*max,sizeof(struct StarPolygon *));

		  if((NewEntry->PseudoDecompList)!=NULL)
		  { for(i=0;i<max*max;i++)
			{ NewEntry->component_num[i]=0;
			  NewEntry->MinDecompList[i]=NULL;
			  NewEntry->psecomp_num[i]=0;
			  NewEntry->PseudoDecompList[i]=NULL;
			}
			NewEntry->MyPoint = newPoint;
			NewEntry->MyIndex = MyInd;
			NewEntry->NextEle = KER;
			NewEntry->VisibilityPolyList = NULL;
			KER = NewEntry;
			retval=1;
		  }
		  else { free(NewEntry->psecomp_num);
			 free(NewEntry->MinDecompList);
				 free(NewEntry->component_num);
				 free(NewEntry);
			   }
		}
			else { free(NewEntry->MinDecompList);
			   free(NewEntry->component_num);
			   free(NewEntry);
			 }
	  }
	  else { free(NewEntry->component_num);
		 free(NewEntry);
		   }
	}
	else free(NewEntry);
  }/* end of if */
  return(retval?NewEntry:NULL);
}/* end of AddPointNodeList() */

void AddMinDecompList(struct KERPointNode *KerEle,int max, int from, int to)
{ struct StarPolygon *NewEntry;
  int i;
  if((NewEntry=(struct StarPolygon *)calloc(1,sizeof(struct StarPolygon)))!=NULL)
  { NewEntry->numberOfPoints = from-to+1;
	if((NewEntry->elements=(int *)calloc(from-to+1,sizeof(int)))!=NULL)
	{ for(i=from;i<=to;i++) NewEntry->elements[i-from]=i;
	  NewEntry->NextEle=KerEle->MinDecompList[from*max+to];
	  KerEle->MinDecompList[from*max+to]=NewEntry;
	  KerEle->component_num[from*max+to]++;
	}/* end of if*/
	else free(NewEntry);
  }/* end of if */
}/* end of AddMinDecompList() */

struct StarPolygon *AllocateStarFromTriangle(struct BaseTriangleEle *Tri)
{ struct StarPolygon *NewEle=NULL;
  int retval=0;
  if((NewEle=(struct StarPolygon *)calloc(1,sizeof(struct StarPolygon)))!=NULL)
  { if((NewEle->elements=(int *)calloc(3,sizeof(int)))!=NULL)
	{ NewEle->numberOfPoints=3;
	  NewEle->elements[0]=Tri->first;
	  NewEle->elements[1]=Tri->middle;
	  NewEle->elements[2]=Tri->last;
	  NewEle->NextEle=NULL;
	  retval=1;
	}/* end of if */
	else free(NewEle);
  }/* end of if */
  return (retval?NewEle:NULL);

}/* end of AllocateStarFromTriangle() */

struct StarPolygon *AllocateStarFromIndices(int *Tri)
{ struct StarPolygon *NewEle=NULL;
  int retval=0;
  if((NewEle=(struct StarPolygon *)calloc(1,sizeof(struct StarPolygon)))!=NULL)
  { if((NewEle->elements=(int *)calloc(3,sizeof(int)))!=NULL)
	{ NewEle->numberOfPoints=3;
	  NewEle->elements[0]=Tri[0];
	  NewEle->elements[1]=Tri[1];
	  NewEle->elements[2]=Tri[2];
	  NewEle->NextEle=NULL;
	  retval=1;
	}/* end of if */
	else free(NewEle);
  }/* end of if */
  return (retval?NewEle:NULL);

}/* end of AllocateStarFromIndices() */

void swap(int *array, int k, int l)
{ int buffer;
  buffer = array[k];
  array[k]=array[l];
  array[l]=buffer;
}/* end of swap() */

void SortThem(int *array, int maxele)
{ int k,l;
  for(k=0;k<(maxele-1);k++)
	 for(l=k+1;l<maxele;l++)
	  if(array[l]<array[k]) swap(array,k,l);
}/* end of SortThem() */

IsInTheArray(int *array, int max, int SearchKey)
{ int retval=false;
  int i=0;
  while(!retval&&i<max)
   if(array[i]==SearchKey) retval=true;
   else i++;
  return retval;
}/* end of IsInTheArray() */

IsIncludes(struct StarPolygon *First, struct StarPolygon *Second)
{ struct StarPolygon *ptrMax;
  struct StarPolygon *ptrMin;
  int *temp;
  int i=0,k;
  SortThem(First->elements,First->numberOfPoints);
  SortThem(Second->elements,Second->numberOfPoints);
  ptrMax=(First->numberOfPoints>=Second->numberOfPoints?First:Second);
  ptrMin=(First->numberOfPoints<Second->numberOfPoints?First:Second);
  k=i=0;
  while(i<ptrMin->numberOfPoints)
  {	 k=k+IsInTheArray(ptrMax->elements,ptrMax->numberOfPoints,ptrMin->elements[i]);
	 i++;
  }/* end of while */
  if(k==ptrMin->numberOfPoints)
  { /* Maximum covers Minimum */
	if(ptrMax->numberOfPoints>ptrMin->numberOfPoints&&ptrMax!=First)
	{ temp = First->elements;
	  First->elements = ptrMax->elements;
	  First->numberOfPoints = ptrMax->numberOfPoints;
	  free(temp);
	}/* end of if */
  }/* end of if */
  return (k==ptrMin->numberOfPoints);
}/* end of IsIncludes() */

IsListInclude(struct StarPolygon *StarList, struct StarPolygon *SearchStar,
			  int Component_Num)
{ struct StarPolygon *ptr;
  int notInclude=true;
  int k;
  ptr=StarList;
  while(ptr!=NULL&&notInclude&&k<Component_Num)
  { if(IsIncludes(ptr,SearchStar)) notInclude=false;
	else ptr=ptr->NextEle;
	k++;
  }/* end of while() */
  return(!notInclude);
}/* end of IsLIstInclude() */

void AddStarPolyToMinDecompList(struct KERPointNode *KerEle,int max, int from,
								int to,	struct StarPolygon *NewEntry)
{ if((from>=0)&&(to>=0)&&(from<max)&&(to<max)&&(from<to))
  { if(!IsListInclude(KerEle->MinDecompList[from*max+to],NewEntry,KerEle->component_num[from*max+to]))
	{ NewEntry->NextEle = KerEle->MinDecompList[from*max+to];
	  KerEle->MinDecompList[from*max+to]=NewEntry;
	  KerEle->component_num[from*max+to]++;
	}
	else
	  { /*free(NewEntry->elements);
		*/
		free(NewEntry);
	  }
  }
  else printf("AddStarPolyToMinDecompList: Illegal access i=%d, j=%d\n",from,to);
}/* end of AddStarPolyToMinDecompList() */

void AddStarPolyToMinDecompListforP(struct KERPointNode *KerEle,int max, int from,
								int to,	struct StarPolygon *NewEntry)
{ if((from>=0)&&(to>=0)&&(from<max)&&(to<max)&&(from<to))
  { NewEntry->NextEle = KerEle->MinDecompList[from*max+to];
	KerEle->MinDecompList[from*max+to]=NewEntry;
	KerEle->component_num[from*max+to]++;
  }
  else printf("AddStarPolyToMinDecompList: Illegal access i=%d, j=%d\n",from,to);
}/* end of AddStarPolyToMinDecompListforP() */

void AddStarPolyToPseudoDecompList(struct KERPointNode *KerEle,int max, int from,
								int to,	struct StarPolygon *NewEntry)
{ if((from>=0)&&(to>=0)&&(from<max)&&(to<max)&&(from<to))
  { NewEntry->NextEle = KerEle->PseudoDecompList[from*max+to];
	KerEle->PseudoDecompList[from*max+to]=NewEntry;
	KerEle->psecomp_num[from*max+to]++;
  }
  else printf("AddStarPolyToPseudoDecompList: Illegal access i=%d, j=%d\n",from,to);
}/* end of AddStarPolyToMinDecompList() */


void AddStarPolyListToMinDecompList(struct KERPointNode *KerEle,int max, int from,
									int to,	struct StarPolygon *NewList, int maxcomp)
/* Copies the each elements of NewList to the KerEle's MD List
*/
{ struct StarPolygon *ptr;
  struct StarPolygon *ptrele;
  int i;
  int count=0;
  ptr=NewList;
  while(ptr!=NULL&&count<maxcomp)
  { if((ptrele=(struct StarPolygon *)calloc(1,sizeof(struct StarPolygon)))!=NULL)
	{ if((ptrele->elements=(int *)calloc(ptr->numberOfPoints,sizeof(int)))!=NULL)
	  { for(i=0;i<ptr->numberOfPoints;i++)
			ptrele->elements[i]=ptr->elements[i];
		ptrele->numberOfPoints=ptr->numberOfPoints;
		ptrele->NextEle=NULL;
		AddStarPolyToMinDecompList(KerEle,max,from,to,ptrele);
	  }/* end of if */
	  else free(ptrele);
	}/* end of if */
	ptr=ptr->NextEle;
	count++;
  }/* end of while() */
}/* end of AddStarPolyListToMinDecompList() */

void AddStarPolyListToMinDecompListforP(struct KERPointNode *KerEle,int max, int from,
									int to,	struct StarPolygon *NewList, int maxcomp)
/* Copies the each elements of NewList to the KerEle's MD List
*/
{ struct StarPolygon *ptr;
  struct StarPolygon *ptrele;
  int i;
  int count=0;
  ptr=NewList;
  while(ptr!=NULL&&count<maxcomp)
  { if((ptrele=(struct StarPolygon *)calloc(1,sizeof(struct StarPolygon)))!=NULL)
	{ if((ptrele->elements=(int *)calloc(ptr->numberOfPoints,sizeof(int)))!=NULL)
	  { for(i=0;i<ptr->numberOfPoints;i++)
			ptrele->elements[i]=ptr->elements[i];
		ptrele->numberOfPoints=ptr->numberOfPoints;
		ptrele->NextEle=NULL;
		AddStarPolyToMinDecompListforP(KerEle,max,from,to,ptrele);
	  }/* end of if */
	  else free(ptrele);
	}/* end of if */
	ptr=ptr->NextEle;
	count++;
  }/* end of while() */
}/* end of AddStarPolyListToMinDecompList() */

void Print_MDList(FILE *fp,struct StarPolygon *List,int num_ele)
{ int k,m;
  struct StarPolygon *ptr;
  fprintf(fp,"{ ");
  ptr=List;
  k=0;
  while(ptr!=NULL&&k<num_ele)
  { fprintf(fp,"( ");
	for(m=0;m<(ptr->numberOfPoints-1);m++) fprintf(fp,"%3d,",ptr->elements[m]);
	if(ptr->NextEle!=NULL)
		 fprintf(fp,"%3d ) , ",ptr->elements[m]);
	else fprintf(fp,"%3d )",ptr->elements[m]);

	ptr=ptr->NextEle;k++;
  }/* end of while */
  fprintf(fp," }\n");

}/* end of Print_MDList*/

void Print_MDListToScreen(struct StarPolygon *List,int num_ele)
{ int k,m;
  struct StarPolygon *ptr;
  printf("{ ");
  ptr=List;
  k=0;
  while(ptr!=NULL&&k<num_ele)
  { printf("( ");
	for(m=0;m<(ptr->numberOfPoints-1);m++) printf("%3d,",ptr->elements[m]);
	if(ptr->NextEle!=NULL)
		 printf("%3d ) , ",ptr->elements[m]);
	else printf("%3d )",ptr->elements[m]);

	ptr=ptr->NextEle;k++;
  }/* end of while */
  printf(" }\n");

}/* end of Print_MDListToScreen() */

/*CopyStarPolyListToP(struct KERPointNode *KerEle,int max, int from,
									int to,FILE *fp)
 Copies the each elements of NewList to the KerEle's MD List

{ struct StarPolygon *ptr;
  struct StarPolygon *ptrele;
  int i;
  P[from*max+to].NumberOfRealList=0;

  Print_MDList(fp,KerEle->MinDecompList[from*max+to],KerEle->component_num[from*max+to]);

  fprintf(fp," IN cOPY Routine \n");
  ptr=KerEle->MinDecompList[from*max+to];
  while(ptr!=NULL)
  { if((ptrele=(struct StarPolygon *)calloc(1,sizeof(struct StarPolygon)))!=NULL)
	{ if((ptrele->elements=(int *)calloc(ptr->numberOfPoints,sizeof(int)))!=NULL)
	  { fprintf(fp,"( ");
		for(i=0;i<ptr->numberOfPoints;i++)
			{ ptrele->elements[i]=ptr->elements[i];
			  fprintf(fp,"%d, ",ptrele->elements[i]);
			}
		fprintf(fp,") ");
		ptrele->numberOfPoints=ptr->numberOfPoints;
		ptrele->NextEle=P[from*max+to].RealMDList;
		P[from*max+to].RealMDList = ptrele;
		P[from*max+to].NumberOfRealList++;
	  }/* end of if
	  else { free(ptrele);
			 fprintf(fp,"\n CopyStarPolyListToP -- Memory Problem \n");
		   }
	}/* end of if
	else
	  fprintf(fp,"\n CopyStarPolyListToP -- Memory Problem \n");

	ptr=ptr->NextEle;
  }/* end of while()
  return(P[from*max+to].NumberOfRealList=KerEle->component_num[from*max+to]?1:0);

}/* end of CopyStarPolyListToP() */

void DeallocateMinDecompList(struct KERPointNode *KerEle,int max, int from, int to)
{ struct StarPolygon *ptr;
  struct StarPolygon *next;
  ptr= KerEle->MinDecompList[from*max+to];
  while(ptr!=NULL)
  { next = ptr->NextEle;
    if(ptr->elements!=NULL)
	 free(ptr->elements);  /* deallocate the set */
    free(ptr);                 /* deallocate the structure */
    ptr = next;
  }/* end of while */
  KerEle->component_num[from*max+to]=0;
}/* end of DeallocateMinDecompList() */

void DeallocateAllMinDecompList(struct KERPointNode *KerEle,int max)
{ int i,j;
  struct StarPolygon *ptr;
  struct StarPolygon *next;
  
  for(i=0;i<max;i++)
     for(j=0;j<max;j++)
     { 
       ptr= KerEle->MinDecompList[i*max+j];
       while(ptr!=NULL)
       { next = ptr->NextEle;
         if(ptr->elements!=NULL)
	     free(ptr->elements);  /* deallocate the set */
         free(ptr);                 /* deallocate the structure */
         ptr = next;
       }/* end of while */
       KerEle->component_num[i*max+j]=0;
     }/* end of for */
}/* end of DeallocateAllMinDecompList() */

void DeallocateAllPseudoMinDecompList(struct KERPointNode *KerEle,int max)
{ int i,j;
  for(i=0;i<max;i++)
	 for(j=0;j<max;j++)
	 { DeallocateStarPolygonList(KerEle->PseudoDecompList[i*max+j]);
	   KerEle->psecomp_num[i*max+j]=0;
	 }/* end of for */
}/* end of DeallocateAllPseudoMinDecompList() */

void AddVisibilityList(struct PointNode *Pnt, int idx)
{ struct VisiblePolyEle *NewVPEle;
  if((NewVPEle=(struct VisiblePolyEle *)calloc(1,sizeof(struct VisiblePolyEle)))!=NULL)
  { NewVPEle->index = idx;
	NewVPEle->NextEle = Pnt->VisibilityPolyList;
	Pnt->VisibilityPolyList = NewVPEle;
  }/* end of if */
  else printf("\n Error : AddVisibilityList not Enough Memory ");
}/* end of AddVisibilityList() */

void AddKERVisibilityList(struct KERPointNode *Pnt, int idx)
{ struct VisiblePolyEle *NewVPEle;
  if((NewVPEle=(struct VisiblePolyEle *)calloc(1,sizeof(struct VisiblePolyEle)))!=NULL)
  { NewVPEle->index = idx;
	NewVPEle->NextEle = Pnt->VisibilityPolyList;
	Pnt->VisibilityPolyList = NewVPEle;
  }/* end of if */
  else printf("\n Error : AddKERVisibilityList not Enough Memory ");
}/* end of AddVisibilityList() */

void DeallocateVisibilityPolygon(struct VisiblePolyEle *Pnt)
{ struct VisiblePolyEle *ptr;
  struct VisiblePolyEle *next;
  ptr = Pnt;
  while(ptr!=NULL)
  { next = ptr ->NextEle;
	free(ptr);
	ptr = next;
  }/* end of while */
}/* end of DeallocateVisibilityPolygon() */

void DeallocateVisibilityList(struct PointNode *Pnt)
{
  DeallocateVisibilityPolygon(Pnt->VisibilityPolyList);
}/* end of DeallocateVisibilityList() */

void DeallocateKERNode(struct KERPointNode *KerEle, int max)
{ DeallocateVisibilityPolygon(KerEle->VisibilityPolyList);
  DeallocateAllMinDecompList(KerEle,max);
  DeallocateAllPseudoMinDecompList(KerEle,max);
  free(KerEle->component_num);      /* Deallocate the component number array */
  free(KerEle->MinDecompList);      /* Deallocate the REAL MD list Headers */
  free(KerEle->psecomp_num);        /* Deallocate the component number array */
  free(KerEle->PseudoDecompList);   /* Deallocate the PSEUDO MD list Headers */
  free(KerEle);                     /* Deallocate the structure */
}/* end of DeallocateKER*/

void DeallocateKER(int max)
{ struct KERPointNode *ptr;
  struct KERPointNode *next;
  ptr = KER;
  while(ptr!=NULL)                 /* until hit the end */
  { next = ptr ->NextEle;
	DeallocateKERNode(ptr,max);
	ptr = next;                    /* goto next element */
  }/* end of while */
}/* end of DeallocateInteriorLines() */

void AddPointToPolyVisiblity(struct point newPoint, int indx)
{ struct PointNode *NewEntry;
  if((NewEntry=(struct PointNode *)calloc(1,sizeof(struct PointNode)))!=NULL)
  { NewEntry->MyPoint = newPoint;
	NewEntry->MyIndex = indx;
	NewEntry->NextEle = PolygonVertexVisiblityList;
	NewEntry->VisibilityPolyList = NULL;
	PolygonVertexVisiblityList = NewEntry;
  }/* end of if */
  else printf("\n Error : AddPointToPolyVisibility not enough memory ");
}/* end of AddPointToPolyVisibility() */

void AddPolyVisibilityList(struct PointNode *Pnt, int idx)
{ struct VisiblePolyEle *NewVPEle;
  if((NewVPEle=(struct VisiblePolyEle *)calloc(1,sizeof(struct VisiblePolyEle)))!=NULL)
  { NewVPEle->index = idx;
	NewVPEle->NextEle = Pnt->VisibilityPolyList;
	Pnt->VisibilityPolyList = NewVPEle;
  }/* end of if */
  else printf("\n Error : AddPolyVisibilityList not enough memory ");
}/* end of AddPolyVisibilityList() */

void DeallocatePolyVisibility()
{ struct PointNode *ptr;
  struct PointNode *next;
  int old;
  ptr = PolygonVertexVisiblityList;
  while(ptr!=NULL)
  { next = ptr ->NextEle;
	DeallocateVisibilityList(ptr);
	free(ptr);
	ptr = next;
  }/* end of while */
}/* end of DeallocateInteriorLines() */

void DeallocatePMatrix()
{
  free(P);

}/* end of DeallocatePMatrix() */

/************ F I L E    O U T P U T    R O U T I N E S  ******************/

void Print_SubPolygonList()
/* Print the Sub Polygons */
{ struct SubPolyNode *ptr;
  int k=0;
  ptr = SubPolygonList;
  while(ptr!=NULL)
  {  printf("\n index = %d   %d, %d ",++k,ptr->from,ptr->to);
	 ptr = ptr->NextEle;
  }/* end of while */
}/* end of Print_SubPolygonList() */

void Print_SubPolygonBaseTriangleList()
/* Print the Sub Polygons */
{ struct SubPolyNode *ptr;
  struct BaseTriangleEle *ptrBase;
  int k=0;
  ptr = SubPolygonList;
  while(ptr!=NULL)
  {  printf("\n index=%d Poly= %d %d => ",++k,ptr->from,ptr->to);
	 ptrBase = ptr->BaseTrianglesList;
	 while(ptrBase)
	 {  printf(" ( %d,%d,%d ) ",ptrBase->first,ptrBase->middle,ptrBase->last);
		ptrBase = ptrBase->NextEle;
	 }/* end of while */
	 ptr = ptr->NextEle;
  }/* end of while */
}/* end of Print_SubPolygonBaseTriangle() */

void Print_DecompList( FILE *fp, struct StarPolygon **DecompList,
					   int *comp_num, int max)
{ int i,j,k,m;
  struct StarPolygon *ptr;
  for(i=0;i<max;i++)
	 for(j=0;j<max;j++)
	   if(comp_num[i*max+j])
	   { fprintf(fp," %d, %d",j,i);
		 fprintf(fp,"{ ");
		 ptr=DecompList[i*max+j];
		 k=0;
		 while(ptr!=NULL&&k<comp_num[i*max+j])
		 { fprintf(fp,"( ");
		   for(m=0;m<ptr->numberOfPoints;m++) fprintf(fp,"%d,",ptr->elements[m]);
		   fprintf(fp,")");
		   ptr=ptr->NextEle;k++;
		 }/* end of while */
		 fprintf(fp," }\n");
	   }/* end of if */
}/* end of Print_DecompList() */

void Print_Visibility(FILE *fp, struct VisiblePolyEle *VisilityList)
{ struct VisiblePolyEle *ptr;
  ptr = VisilityList;
  fprintf(fp,"\n Visibility :");
  while(ptr!=NULL)
  { fprintf(fp,"%d ",ptr->index);
	ptr=ptr->NextEle;
  }/* end of while() */
}/* end of Print_Visibility() */

void Print_KERList()
{ FILE *fp;
  struct KERPointNode *ptr;
  if((fp=fopen("listker","w"))!=NULL)
  { ptr=KER;
	while(ptr!=NULL)
	{ fprintf(fp,"\n x=%f y=%f Index=%d ",ptr->MyPoint.x,ptr->MyPoint.y,ptr->MyIndex);
	  Print_Visibility(fp,ptr->VisibilityPolyList);
	  ptr=ptr->NextEle;
	}/* end of while */
	fclose(fp);
  }/* end of if */
}/* end of PrintKERList() */

void Print_KER(int max)
{ FILE *fp;
  struct KERPointNode *ptr;
  struct StarPolygon *ptrStar;
  int i,j,k,m;
  if((fp=fopen("outKer","w"))!=NULL)
  { ptr=KER;
	while(ptr!=NULL)
	{ fprintf(fp,"\n Point (%f,%f) --",ptr->MyPoint.x,ptr->MyPoint.y);
	  for(i=0;i<max;i++)
		 for(j=0;j<max;j++)
		   if(ptr->component_num[i*max+j]>0)
		   { k=0;
			 ptrStar = ptr->MinDecompList[i*max+j];
			 while(k<ptr->component_num[i*max+j])
			 { fprintf(fp,"( ");
			   for(m=0;m<ptrStar->numberOfPoints;m++)
					  fprintf(fp,"%d,",ptrStar->elements[m]);
			   fprintf(fp,")");
			   k++;
			 }/* end of while() */
		   }/* end of if */
	  ptr=ptr->NextEle;
	}/* end of while() */
	fclose(fp);
  }/* end of if */
}/* end of Print_KER() */

void Print_P(int max)
{ FILE *fp;
  int i,j;
  struct KERPointNode *ptrKER;
  if((fp=fopen("out2","w"))!=NULL)
  { for(i=0;i<max;i++)
	  for(j=0;j<max;j++)
	  { /*ptrKER=P[i*max+j];*/
		fprintf(fp,"\n P[%d,%d] --",i,j);
		Print_MDList(fp,P[i*max+j].RealMDList,P[i*max+j].NumberOfRealList);
	  }/* end of for */
	fclose(fp);
  }/* end of if */
}/* end of Print_P() */

/*void DisplayPMatrix(struct StarPolygon *RealMDList,struct point *poly, int maxele)
{ struct StarPolygon *ptr;
  int k=0;
  ptr = RealMDList;
  while(ptr!=NULL&&k<maxele)
  { //DisplayStarPolygon(ptr,poly);
	ptr=ptr->NextEle;
  }/* end of while
}/* end of */

void Print_Result(struct point *poly, int max)
/* Prints the result */
{ struct StarPolygon *ptr;
  int k=0;
  FILE *fp;
  if((fp=fopen("Endresult","w"))!=NULL)
  {
	/* Print the Polygon */
	for(k=0;k<max;k++)
	  fprintf(fp,"\n P[%3d].x=%12.6f  P[%3d].y=%12.6f ",k,poly[k].x,k,poly[k].y);

	fprintf(fp,"\n\n Decomposition Set = ");
	printf("\n\n Decomposition Set = ");

	Print_MDList(fp,P[max-1].RealMDList,P[max-1].NumberOfRealList);

	Print_MDListToScreen(P[max-1].RealMDList,P[max-1].NumberOfRealList);

	if(P[max-1].NumberOfRealList>1)
	 { fprintf(fp,"\n %d guards are enough to cover the gallery\n",P[max-1].NumberOfRealList);
	   printf("\n %d guards are enough to cover the gallery\n",P[max-1].NumberOfRealList);
	 }
	else
	 { fprintf(fp,"\n %d guard is enough to cover the gallery\n",P[max-1].NumberOfRealList);
	   printf("\n %d guard is enough to cover the gallery\n",P[max-1].NumberOfRealList);
	 }

	fclose(fp);
  }/* end of if */
  else
	{
	  printf("\n\n Decomposition Set = ");
	  Print_MDListToScreen(P[max-1].RealMDList,P[max-1].NumberOfRealList);
	  if(P[max-1].NumberOfRealList>1)
		printf("\n %d guards are enough to cover the gallery\n",P[max-1].NumberOfRealList);
	  else
		printf("\n %d guard is enough to cover the gallery\n",P[max-1].NumberOfRealList);
	}

}/* end of if */

/**************************************************************************/

/*float theta(struct point p1, struct point p2)
{ int dx,dy,ax,ay;
  float t;
  dx = p2.x-p1.x; ax=abs(dx);
  dy = p2.y - p1.y; ay=abs(dy);
  if((dx == 0) && ( dy==0)) t=0;
  else t=dy/(ax+ay);
  if(dx<0) t=2-t;
  else if(dy<0) t=4+t;
  return(t*90.0);
}/* end of theta */

float angle(struct point p1, struct point p2)
{ float dx,dy;
  float retval;
  dx = p2.x-p1.x; dx = abs(dx);
  dy = p2.y-p1.y; dy = abs(dy);
  if((dx==0)&&(dy==0)) retval=-1.0; /* they are same point */
  else if(dx==0)
	   { if(p2.y>p1.y) retval=90.0;
		 else retval=-90.0;
	   }
  else if(dy==0)
	   { if(p2.x>p1.x) retval=0.0;
		 else retval=180.0;
	   }
  else { retval=((1.0*dy)/(1.0*dx))*180.0/(3.14);
		 if((p2.y-p1.y)>0)
		 { if((p2.x-p1.x)<0) retval=180.0-retval;
		 }
		 else
		 { if((p2.x-p1.x)<0) retval=retval-180.0;
		   else retval=-1.0*retval;
		 }
	   }
  return (retval);
}/* end of angle() */

IsEqual(struct point p1, struct point p2)
{  return(((p1.x==p2.x)&&(p1.y==p2.y))?true:false);
}/* end of IsEqual() */

float Distance(struct point p1, struct point p2)
{ double val;
  val = (double)(Square(p2.x-p1.x)+Square(p2.y-p1.y));
  return((float)sqrt(val));
}/* end of Distance() */

float Area(struct point p1, struct point p2, struct point p3)
{ return(p1.x*p2.y-p1.y*p2.x+
		 p1.y*p3.x-p1.x*p3.y+
		 p2.x*p3.y-p3.x*p2.y);
}/* end of Area() */

Left(struct point p1, struct point p2, struct point p3)
{ return((Area(p1,p2,p3)>0?1:0));
}/* end of Left() */

LeftOn(struct point p1, struct point p2, struct point p3)
{ return((Area(p1,p2,p3)>=0?1:0));
}/* end of LeftOn() */

IsReflexive(struct point p1, struct point p2, struct point p3)
/* Returns TRUE if the interior angle of the vertex p2 is greater than 180.
*/
{ return((Area(p1,p2,p3)<0?1:0));
}/* end of IsReflexive() */

IsConvex(struct point p1, struct point p2, struct point p3)
/* Returns TRUE if the interior angle of the vertex p2 is less than or equal
   to 180.
*/
{ return(LeftOn(p1,p2,p3));
}/* end of IsConvex() */

Collinear(struct point p1, struct point p2, struct point p3)
/* Returns TRUE if the given three points are collinear.
*/
{ return((Area(p1,p2,p3)==0?1:0));
}/* end of Collinear() */

/*IsEdgeOfPolygon(struct point *Pol, int max, int Vi, int Vj)*/
IsEdgeOfPolygon(int max, int Vi, int Vj)
/*  Returns TRUE if the segment ViVj is en element of polygon's border.
*/
{ int retval=FALSE;
  if((Vi==((Vj+1)%max))||(Vi==((Vj-1)%max))) retval=TRUE;
  return retval;
}/* end of IsEdgeOfPolygon() */

IntersectProp(struct point p1, struct point p2, struct point p3, struct point p4)
{ int retval;
  if( Collinear(p1,p2,p3) || Collinear(p1,p2,p4) ||
	  Collinear(p3,p4,p1) || Collinear(p3,p4,p2)) retval=0;
  else retval=XOR(Left(p1,p2,p3),Left(p1,p2,p4)) &&
			  XOR(Left(p3,p4,p1),Left(p3,p4,p2));
  return(retval);
}/* end of IntersectProp() */

Between(struct point p1, struct point p2, struct point p3)
{ int retval;
  if(!Collinear(p1,p2,p3)) retval=0;
  else { if(p1.x != p2.x)
			  retval = ((p1.x <= p3.x) && (p3.x <= p2.x)) ||
					   ((p1.x >= p3.x) && (p3.x >= p2.x)) ;
		 else retval = ((p1.y <= p3.y) && (p3.y <= p2.y)) ||
					   ((p1.y >= p3.y) && (p3.y >= p2.y)) ;
	   }
  return(retval);
}/* end of Between() */

Intersect(struct point p1, struct point p2, struct point p3, struct point p4)
{ int retval=0;
  if(IntersectProp(p1,p2,p3,p4)) retval=1;
  else retval=((Between(p1,p2,p3) || Between(p1,p2,p4) ||
				Between(p3,p4,p1) || Between(p3,p4,p2))?1:0);
  return(retval);
}/* end of Intersect() */

Diagonalie(struct point *Pol, int max, int i, int j)
{ int k,kl;
  int notintersect=1;
  for(k=0;k<max&&notintersect;k++)
  { kl = (k+1)%max;
	if(k!=i&&k!=j&&kl!=i&&kl!=j)
	{
	  if(Intersect(Pol[i],Pol[j],Pol[k],Pol[kl])) notintersect=0;
	}
  }/* end of for */
  return(notintersect);
}/* end of Diagonalie() */

IsIntersectPolyBorder(struct point *Pol, int max, struct point vi,
					  struct point vj)
{ int k,kl;
  int notintersect=1;
  for(k=0;k<max&&notintersect;k++)
  { kl = (k+1)%max;
	if(!IsEqual(Pol[k],vi)&&!IsEqual(Pol[k],vj)&&
	   !IsEqual(Pol[kl],vi)&&!IsEqual(Pol[kl],vj))
	{
	  if(Intersect(vi,vj,Pol[k],Pol[kl])) notintersect=0;
	}
  }/* end of for */
  return(notintersect);
}/* end of IsIntersectPolyBorder() */

InCone(struct point *Pol, int max, int i, int j)
{ int inext;
  int iprev;
  int retval;
  inext = (i+1) %max;
  iprev = (i-1+max) %max;
  if(LeftOn(Pol[iprev],Pol[i],Pol[inext]))
	   retval = (Left(Pol[i],Pol[j],Pol[iprev]) && Left(Pol[j],Pol[i],Pol[inext]));
  else retval = !(LeftOn(Pol[i],Pol[j],Pol[inext]) && LeftOn(Pol[j],Pol[i],Pol[iprev]));
  return(retval);
}/* end of InCone() */

InConePoint(struct point *Pol, int max, int i, struct point pk)
{ int inext;
  int iprev;
  int retval;
  inext = (i+1) %max;
  iprev = (i-1+max) %max;
  if(LeftOn(Pol[iprev],Pol[i],Pol[inext]))
	   retval = (Left(Pol[i],pk,Pol[iprev]) && Left(pk,Pol[i],Pol[inext]));
  else retval = !(LeftOn(Pol[i],pk,Pol[inext]) && LeftOn(pk,Pol[i],Pol[iprev]));
  return(retval);
}/* end of InConePoint() */

Diagonal(struct point *Pol, int max, int i, int j)
/*  Returns TRUE if there is a diagonal between Vi and Vj passing through
	the interior area of the polygon.
*/
{ return(InCone(Pol,max,i,j) && Diagonalie(Pol,max,i,j));
}

IsVisible(struct point *Pol, int max, int i, int j)
/*  Returns the true value if the segment drawn from Vi to Vj is inside the
	polygon.
*/
{ return(InCone(Pol,max,i,j) && Diagonalie(Pol,max,i,j));
}

IsSubPolygon(struct point *Pol, int max, int Vi, int Vj)
{ int retval=false;
  if((Vi>=0)&&(Vi<max)&&(Vj>=0)&&(Vj<max)&&
	 (Vi<Vj)&&(IsVisible(Pol,max,Vi,Vj)))
		 retval=TRUE;
  return retval;
}/* end of IsSubPolygon()*/

IsConvexSubPoly(struct point *Pol, int max, int Vi, int Vj)
/*  Returns TRUE if the given subpolygon is convex
*/
{ int retval=TRUE;
  int i,j=Vj-Vi+1;
  if(IsSubPolygon(Pol,max,Vi,Vj))
  { for(i=0;i<j&&retval;i++)
	 if(IsReflexive(Pol[(Vi+i)%max],Pol[(Vi+i+1)%max],Pol[(Vi+i+2)%max])) retval=0;
  }/* end of if */
  return retval;
}/* end of IsConvexSubPoly() */

IsValidSubPolygon(struct point *Pol, int max, int Vi, int Vj)
{ int retval=FALSE;
  if(IsSubPolygon(Pol,max,Vi,Vj)&&
	 (Vi==0||Vj==0||Vi==(max-1)||Vj==(max-1)||
	  IsReflexive(Pol[(max+Vi-1)%max],Pol[Vi],Pol[(Vi+1)%max])||
	  IsReflexive(Pol[(max+Vj-1)%max],Pol[Vj],Pol[(Vj+1)%max]))) retval=TRUE;
  return retval;
}/* end of IsValidSubPolygon() */

IsInsideTheTriangle(struct point Ti, struct point Tm,
					struct point Tj, struct point candidate)
/* Returns TRUE if the point 'candidate' is inside the triangle Ti,Tm,Tj
*/
{ int retval=true;
  struct point temppoly[3];
  temppoly[0]=Ti;
  temppoly[1]=Tm;
  temppoly[2]=Tj;

  /*setcolor(LIGHTGREEN);
  //DisplayTri(Ti,Tm,Tj);
  //DisplayPointColor(candidate,YELLOW);
  //MyGetch();
  if(!(IsEqual(Ti,candidate)||IsEqual(Tm,candidate)||IsEqual(Tj,candidate)))
  { retval = retval & LeftOn(Ti,Tm,candidate);
	if(retval) retval = retval & LeftOn(Tm,Tj,candidate);
	if(retval) retval = retval & LeftOn(Tj,Ti,candidate);
  }*/
  if(!(IsEqual(Ti,candidate)||IsEqual(Tm,candidate)||IsEqual(Tj,candidate)))
	retval = retval & InConePoint(temppoly,3,0,candidate)
					& InConePoint(temppoly,3,1,candidate)
					& InConePoint(temppoly,3,2,candidate) ;
  return retval;
}/* end of IsInsideTheTriangle() */

struct point LineIntersection(struct point p1,struct point p2,
							  struct point a1, struct point a2)
{ struct point retval;
  float m1,m2;
  float c1,c2;
  float dx1,dx2;
  float dy1,dy2;
  dx1=p1.x-p2.x;
  dy1=p1.y-p2.y;
  m1=(p1.x!=p2.x?dy1/dx1:0);
  dx2=a1.x-a2.x;
  dy2=a1.y-a2.y;
  m2=(a1.x!=a2.x?dy2/dx2:0);
  c1=p1.y-m1*p1.x;
  c2=a1.y-m2*a1.x;
  retval.y = (m1!=m2?(c1*m2-c2*m1) / (m2-m1):0);
  retval.x = (m1!=m2?(c1 - c2) / (m2 - m1):0);
  return retval;
}/* end of LineIntersection() */

void Find_Intersection(struct point *Pol, int max, struct point from, struct point to)
{ int i,j;
  int old1;
  float m1,m2;
  float c1,c2;
  float Inx,Iny;
  float dx1,dx2;
  float dy1,dy2;
  struct point orij;
  struct point kp;
  orij.x=250;
  orij.y=250;

  for(i=0;i<max;i++)
  { if(!((from.x==Pol[i].x&&from.y==Pol[i].y)||(from.x==Pol[(i+1)%max].x&&from.y==Pol[(i+1)%max].y)))
	{ if(IntersectProp(from,to,Pol[i],Pol[(i+1)%max]))
	  {
		kp=LineIntersection(from,to,Pol[i],Pol[(i+1)%max]);
		/*old1=getcolor();
		//setcolor(CYAN);
		//DrawLine(orij,from,kp);*/
		AddInteriorLines(from,kp);
		AddPointToKER(kp,max,-1); /* It is not vertex */
		/*setcolor(BLUE);
		//circle(Inx*5.0+250.,250.-Iny*5.,2);
		//setcolor(old1);*/
	  }/* end of if */
	}/* end of if */
  }/* end of for */

}/* end of Find_Y() */

void DisplayDiag(struct point *Pol, int max)
/*
// Display all the segments inside the polygon
// A segment is inside the polygon unless it intersects any line segments
// of the polygon
*/
{ int i,j,k,maxk;
  int old,notintersect,old1;
  float dx,dy;
  float xv,yv;
  float m,c;
  int angle=0;
  int x1,y1;
  struct point to;
  /*struct point orij;
  //orij.x=250;
  //orij.y=250;
  //old=getcolor();
  //setcolor(GREEN);*/
  for(i=0;i<max;i++)
	if(Area(Pol[i],Pol[(i+1)%max],Pol[(i+2)%max])<0) /* if it is reflexive edge */
	{ for(j=0;j<max;j++)
	  { if(j!=i&&j!=(i+1)%max&&j!=(i+2)%max)
		{ if(Diagonal(Pol,max,(i+1)%max,j))
		  {	/* line(Pol[j].x*5+250,250-Pol[j].y*5,Pol[(i+1)%max].x*5+250,250-Pol[(i+1)%max].y*5); */

			dx = Pol[j].x - Pol[(i+1)%max].x;
			dy = Pol[j].y - Pol[(i+1)%max].y;

			angle=0;
			if(dx==0) { angle=1;}       /* VERTICAL    */
			else if(dy==0) { angle=-1;} /* HORIZONTAL  */
			else { m=dy/dx;
				   c=Pol[j].y-m*Pol[j].x;
				 }

			/*old1=getcolor();
			//setcolor(CYAN);*/
			if(angle==-1) /* HORIZONTAL  */
			{  to.y=Pol[(i+1)%max].y;
			   to.x=((Pol[j].x<Pol[(i+1)%max].x)?40.0:-40.0);
			}
			else if(angle==1) /* VERTICAL   */
				 { to.x=Pol[(i+1)%max].x;
				   to.y=((Pol[j].y<Pol[(i+1)%max].y)?40.0:-40.0);
				 }
			else { to.x=((Pol[j].x<Pol[(i+1)%max].x)?40.0:-40.0);
				   to.y=m*to.x+c;
				 }
			/* DrawLine(orij,Pol[(i+1)%max],to); */
			/*setcolor(old1);*/
			if(InConePoint(Pol,max,(i+1)%max,to))
			 Find_Intersection(Pol,max,Pol[(i+1)%max],to);
		  }
		}
		else
		  { if((Pol[j].x!=Pol[(i+1)%max].x)&&(Pol[j].y!=Pol[(i+1)%max].y))
			{ /*line(Pol[j].x*5+250,250-Pol[j].y*5,Pol[(i+1)%max].x*5+250,250-Pol[(i+1)%max].y*5);*/

			dx = Pol[j].x - Pol[(i+1)%max].x;
			dy = Pol[j].y - Pol[(i+1)%max].y;

			angle=0;
			if(dx==0) { angle=1;}       /* VERTICAL    */
			else if(dy==0) { angle=-1;} /* HORIZONTAL  */
			else { m=dy/dx;
				   c=Pol[j].y-m*Pol[j].x;
				 }

			/*old1=getcolor();
			//setcolor(CYAN);*/
			if(angle==-1) /* HORIZONTAL   */
			{  to.y=Pol[(i+1)%max].y;
			   to.x=((Pol[j].x<Pol[(i+1)%max].x)?40.0:-40.0);
			}
			else if(angle==1) /* VERTICAL */
				 { to.x=Pol[(i+1)%max].x;
				   to.y=((Pol[j].y<Pol[(i+1)%max].y)?40.0:-40.0);
				 }
			else { to.x=((Pol[j].x<Pol[(i+1)%max].x)?40.0:-40.0);
				   to.y=m*to.x+c;
				 }
			/*DrawLine(orij,Pol[(i+1)%max],to); */


			if(InConePoint(Pol,max,(i+1)%max,to))
			   Find_Intersection(Pol,max,Pol[(i+1)%max],to);

			}

		  }
	  }/* end of for */

	}/* end of if */
}/* end of DisplayDiag() */

void FindIntersectsinInteriorLines(int max)
{ struct lineNode *ptr;
  struct lineNode *ptr2;
  int old;
  struct point orij;
  struct point from;
  struct point to;
  int i,j;
  int old1;
  float m1,m2;
  float c1,c2;
  float Inx,Iny;
  float dx1,dx2;
  float dy1,dy2;
  struct point kp;
  orij.x=250;
  orij.y=250;
  ptr = InteriorLines;
  while(ptr!=NULL)
  { /*DrawLine(orij,ptr->MyLine.first,ptr->MyLine.next);*/
	ptr2=InteriorLines;
	while(ptr2!=NULL)
	{
	  if(!((ptr2->MyLine.first.x==ptr->MyLine.first.x&&ptr2->MyLine.first.y==ptr->MyLine.first.y) ||
		   (ptr2->MyLine.first.x==ptr->MyLine.next.x&&ptr2->MyLine.first.y==ptr->MyLine.next.y)))
	  { if(IntersectProp(ptr->MyLine.first,ptr->MyLine.next,ptr2->MyLine.first,ptr2->MyLine.next))
		{
		  kp=LineIntersection(ptr->MyLine.first,ptr->MyLine.next,
							  ptr2->MyLine.first,ptr2->MyLine.next);
		  /*old1=getcolor();
		    setcolor(CYAN);
		    DrawLine(orij,from,kp);   
		    AddInteriorLines(from,kp);*/

		  AddPointToKER(kp,max,-1); /* it is not vertex */

		  /*setcolor(WHITE);
		    circle(Inx*5.0+250.,250.-Iny*5.,2); 
		    setcolor(old1);*/
		}
	  }
	  ptr2 = ptr2->NextEle;
	}/* end of while */
	ptr = ptr->NextEle;
  }/* end of while */
}/* end of FindIntersectsinInteriorLines() */

void AddVerticesToKER(struct point *Pol, int max)
{ int i;
  for(i=0;i<max;i++)
	Pol[i].KerPair=AddPointToKER(Pol[i],max,i);
}/* end of AddVerticesToKER() */


void Display_Polygon(struct point *Pol, int max)
{ int i,old;
  float angle1;
  float angle2;
  float alpha11,alpha12,alpha21,alpha22;
  float length1,length2;
  float ang=0.0;
  FILE *out;
  char buf[40];
  out=fopen("out","w");
  for(i=0;i<max;i++)
	{ /*circle(Pol[i].x*5+250,250-Pol[i].y*5,2);
	  //line(Pol[i].x*5+250,250-Pol[i].y*5,Pol[(i+1)%max].x*5+250,250-Pol[(i+1)%max].y*5);
	  */
	  sprintf(buf,"%d",i);
	  /*outtextxy(Pol[i].x*5+254,254-Pol[i].y*5,buf);*/

	}

  /*outtextxy(Pol[0].x*5+254,254-Pol[0].y*5,"F");*/
  for(i=0;i<max;i++)
  { angle1=angle(Pol[(i+1)%max],Pol[i]);
	/*old=getcolor();
	//setcolor(MAGENTA);
	//line(Pol[i].x*5+250,250-Pol[i].y*5,Pol[(i+2)%max].x*5+250,250-Pol[(i+2)%max].y*5);
	//setcolor(old);
	/*length1=Distance(Pol[(i+1)%max],Pol[i]);
	alpha11=length1*cos(2.*3.14*(angle1/360.0));
	alpha12=length1*sin(2.*3.14*(angle1/360.0));
	fprintf(out,"\n %d alpha1=%f alpha2=%f length=%f",i,alpha11,alpha12,length1);
	*/
	angle2=angle(Pol[(i+1)%max],Pol[(i+2)%max]);

	/*length2=Distance(Pol[(i+1)%max],Pol[(i+2)%max]);
	alpha21=length2*cos(2.*3.14*(angle2/360.0));
	alpha22=length2*sin(2.*3.14*(angle2/360.0));
	fprintf(out,"\n %d alpha1=%f alpha2=%f length=%f",i,alpha11,alpha12,length1);
	*/

	if(angle1>=0)
	{ if(angle2>=0) ang = angle2 - angle1 ;
	  else ang = angle1 - angle2;
	}
	else
		 { if(angle2>=0) ang = (180.+angle1) + (180.0 - angle2);
		   else	ang = (360+angle2) - angle1 ;
		 }

	fprintf(out,"\n %d btw %d %d ang1=%f btw %d %d ang2=%f ang=%f",(i+1)%max,(i+1)%max,i,angle1,(i+1)%max,(i+2)%max,angle2,ang);

	/*if(ang>180)
	{ //old=getcolor();
	  //setcolor(RED);
	  //circle(Pol[(i+1)%max].x*5+250,250-Pol[(i+1)%max].y*5,2);
	  //setcolor(old);
	}
	*/

	/*ang = acos((alpha11*alpha21+alpha12*alpha22)/(length1*length2));
	if(Area(Pol[i],Pol[(i+1)%max],Pol[(i+2)%max])<0)
	{ //old=getcolor();
	  //setcolor(YELLOW);
	  //circle(Pol[(i+1)%max].x*5+250,250-Pol[(i+1)%max].y*5,2);
	  //setcolor(old);
	}
	*/


  }
  fclose(out);
  DisplayDiag(Pol,max);

}

void FindVisibilityListOfKER(struct point *Pol, int max)
/* Find the Visible Polygon vertices from the KER points
   The segment should not be intersected by any Boundary Segments of the
   n-gon.
*/
{ struct KERPointNode *ptr;
  int i;
  FILE *fp;
  fp=fopen("Visibil","w");
  ptr = KER;
  while(ptr!=NULL)
  { fprintf(fp,"\n X=%f Y=%f Index=%d Vi: ",ptr->MyPoint.x,ptr->MyPoint.y,ptr->MyIndex);
	for(i=0;i<max;i++)  /* We need to check all the vertices of Polygon P */
	  /*if(IntersectProp(ptr->MyLine.first,ptr->MyLine.next,ptr2->MyLine.first,ptr2->MyLine.next))
	  */
	  if(InConePoint(Pol,max,i,ptr->MyPoint)&&IsIntersectPolyBorder(Pol,max, Pol[i],ptr->MyPoint))
	  {	AddKERVisibilityList(ptr,i);
		/*DrawLine(orij1,ptr->MyPoint,Pol[i]);*/
		fprintf(fp," %d ",i);

	  }
	ptr = ptr->NextEle;
  }/* end of while */
  fclose(fp);
}/* end of FindVisibilityListOfKER() */

void FindVisibilityOfVertexList(struct point *Pol, int max)
/* Find the Visible Polygon vertices from the Polygon vertices
   The segment should not be intersected by any Boundary Segments of the
   n-gon.
*/

{ struct PointNode *ptr;
  int i;

  for(i=0;i<max;i++)
	 AddPointToPolyVisiblity(Pol[i],i);

  ptr = PolygonVertexVisiblityList;
  while(ptr!=NULL)
  { for(i=0;i<max;i++)  /* We need to check all the vertices of Polygon P */
	  /*if(IntersectProp(ptr->MyLine.first,ptr->MyLine.next,ptr2->MyLine.first,ptr2->MyLine.next))*/
	  if(InConePoint(Pol,max,i,ptr->MyPoint)&&IsIntersectPolyBorder(Pol,max, Pol[i],ptr->MyPoint))
	  {	AddVisibilityList(ptr,i);
		/*DrawLine(orij1,ptr->MyPoint,Pol[i]);*/
	  }
	  else /*if(IsEqual(ptr->MyPoint,Pol[(i-1+max)%max])||IsEqual(ptr->MyPoint,Pol[(i+1)%max]))*/
		   if((ptr->MyIndex!=-1)&&(ptr->MyIndex==((i-1+max)%max)||ptr->MyIndex==((i+1)%max)))
		   { AddVisibilityList(ptr,i);
			 /*DrawLine(orij1,ptr->MyPoint,Pol[i]);*/
		   }

	ptr = ptr->NextEle;
  }/* end of while */

}/* end of FindVisibilityOfVertexList()*/

void FindSubPolygonList(struct point *Pol, int max)
/* Find the Sub Polygons from Polygon vertices Visilibility List
*/
{ struct PointNode *ptr;
  struct VisiblePolyEle *ptr2;
  /* Each Visibility pair correseponds to a subpolygon */
  ptr = PolygonVertexVisiblityList;
  while(ptr!=NULL)
  {  ptr2 = ptr->VisibilityPolyList;
     while(ptr2!=NULL)
     { if((ptr2->index-(ptr->MyIndex))>1)
       { AddSubPolygonList(ptr->MyIndex,ptr2->index);
	 printf("\n %d , %d is sub polygon ",ptr->MyIndex,ptr2->index);
		 /*if(ptr->MyIndex<ptr2->index)
		 {  //Display_Polygon_Segments(Pol,max);
			//Display_SubPolygon(Pol,max,ptr->MyIndex,ptr2->index);
			//MyGetch();
		 } end of if */
	   }/* end of if */
	   ptr2 = ptr2->NextEle;
	 }/* end of while */
	 ptr = ptr->NextEle;
  }/* end of while */
}/* end of FindSubPolygonList()*/

void FindBaseTriangles(struct point *Pol, int max)
/* Finds Base Triangles for each Sub Polygon */
{ struct SubPolyNode *ptr;
  int i;
  ptr = SubPolygonList;
  while(ptr!=NULL)
  {	
    for(i=ptr->from+1;i<ptr->to;i++)
	if((IsEdgeOfPolygon(max, ptr->from,i)||
	   (IsValidSubPolygon(Pol,max, ptr->from, i) ))&&
	   (IsEdgeOfPolygon(max, i,ptr->to)||
	   (IsValidSubPolygon(Pol,max, i, ptr->to)) ))
	{  AddBaseTriangle(ptr,ptr->from,i, ptr->to);
	   /*
	   printf(" ( %d,%d,%d ) ",ptr->BaseTrianglesList->first,ptr->BaseTrianglesList->middle,ptr->BaseTrianglesList->last);
	   */
	}
	ptr = ptr->NextEle;
  }/* end of while */

}/* end of FindBaseTriangles()*/

IsIndexInTheSet(int *SearchArray, int maxele, int SearchKey )
{ int notFound = true;
  int i=0;
  while((i<maxele)&&notFound)
  { if(SearchArray[i]==SearchKey) notFound=false;
	else i++;
  }/* end of while */
  return(!notFound?1:0);
}/* end of ISINdexInTheSet() */

MergeTriangle(struct KERPointNode *KerPtr,int max,int from,int to,int *Triangle)
/*  This routine merges the triangle with the KerPtr->MinDecomp[from*max+to]
	StarPolygon list.
*/
{ struct StarPolygon *ptrStar;
  int notFound=true;
  int k,count=0;
  int tri_indx=0;
  int matchcount=0;
  int *temp;
  ptrStar = KerPtr->MinDecompList[from*max+to];
  while(ptrStar!=NULL&&notFound&&count<KerPtr->component_num[from*max+to])
  {
	/* find first two elements are in the decomp component */
	matchcount= IsIndexInTheSet(ptrStar->elements,ptrStar->numberOfPoints,Triangle[0]) +
				IsIndexInTheSet(ptrStar->elements,ptrStar->numberOfPoints,Triangle[1])+
				IsIndexInTheSet(ptrStar->elements,ptrStar->numberOfPoints,Triangle[2]);

	if(matchcount==2)
	{ /*notFound=false;*/
	  if(!IsIndexInTheSet(ptrStar->elements,ptrStar->numberOfPoints,Triangle[0]))
		 tri_indx=0;
	  else
	  if(!IsIndexInTheSet(ptrStar->elements,ptrStar->numberOfPoints,Triangle[1]))
		 tri_indx=1;
	  else
	   if(!IsIndexInTheSet(ptrStar->elements,ptrStar->numberOfPoints,Triangle[2]))
		 tri_indx=2;
	  /* create the elements array and copy the previuos values */
	  if((temp=(int *)calloc(ptrStar->numberOfPoints+1,sizeof(int)))!=NULL)
	  { for(k=0;k<ptrStar->numberOfPoints;k++)
		   temp[k]=ptrStar->elements[k];
		temp[k]=Triangle[tri_indx];         /* copy the new element */
		SortThem(temp,ptrStar->numberOfPoints+1);
		free(ptrStar->elements);     /* deallocate the previous one */
		ptrStar->elements=temp;      /* update */
		ptrStar->numberOfPoints++;    /* incremenet the element number */
		notFound=false;
	  }/* end of if */
	}/* end of if */
	ptrStar=ptrStar->NextEle;
	count++;
  }/* end of while() */
  return(!notFound);
}/* end of MergeTriangle(*/

IsXCanSeeVertex(struct KERPointNode *KerEle, int vi)
/*  Returns TRUE if the vi th vertex of the Polygon can be seen from the
	KerEle
*/
{ int retval=false;
  struct VisiblePolyEle *ptr;
  ptr=KerEle->VisibilityPolyList;
  while(ptr!=NULL&&!retval)
  { if(vi==ptr->index) retval=true;
	else ptr=ptr->NextEle;
  }/* end of while */
  return retval;
}/* end of IsXCanSeeVertex() */

void DPProcedure(struct point *Pol, int max)
{ /* struct MDElement **P; */
  int i,k;
  struct SubPolyNode *ptr;
  struct StarPolygon  *previousptr;
  struct KERPointNode *KerPtr;
  struct BaseTriangleEle *Triangle;
  struct StarPolygon *NewEle;
  struct KERPointNode *MinKerPtr;
  struct NewMDElement *ptrMD;
  int compare,look;
  int PreviousNumber;
  int trin[3];
  FILE *fp;
  fp=fopen("Dynamic","w");
  ptr = SubPolygonList;

  /* remove the first element*/ 
  if(ptr!=NULL&&(ptr->to-ptr->from)==0) ptr=ptr->NextEle;

  if((P=(struct NewMDElement *) calloc(max*max,sizeof(struct NewMDElement)))!=NULL)
  {
	/* Initialize the structure */
	for(i=0;i<max*max;i++)
	{ P[i].RealMDList=NULL;
	  P[i].NumberOfRealList=0;
	}

	while(ptr!=NULL&&((ptr->to-ptr->from)==2))   /* For each Pij */
	{

	  MinKerPtr=NULL;

	  /*Display_Polygon_Segments(Pol,max);
	  //Display_SubPolygon(Pol,max,ptr->from,ptr->to);
	  //MyGetch();*/

	  fprintf(fp,"\n Subpolygon from %d to %d ",ptr->from,ptr->to);

	  KerPtr=KER;

	  while(KerPtr!=NULL)  /* For each Potential Kernel Point */
	  {
		/* put all the KER points inside the triangle into REAL List*/

		/* put all the KER points that can be visible from one of the
				 points ptr->from, ptr->from+1, ptr->to and put these points
				 into PSEUDO list.
		*/
		trin[0]=ptr->from;
		trin[1]=(ptr->from)+1;
		trin[2]=ptr->to;

		if(IsInsideTheTriangle(Pol[ptr->from],Pol[(ptr->from)+1],
									 Pol[ptr->to],KerPtr->MyPoint))
		{ /* KerPtr has a MD for Pfrom,Pto */

		  /*KerPtr->component_num[i*max+j]=1;

		  //DisplayPointColor(KerPtr->MyPoint,LIGHTGRAY);
		  //MyGetch();*/
		  trin[0]=ptr->from;
		  trin[1]=(ptr->from)+1;
		  trin[2]=ptr->to;

		  if((NewEle=AllocateStarFromIndices(trin))!=NULL)
				AddStarPolyToMinDecompList(KerPtr,max, ptr->from,
											   ptr->to,NewEle);
		  /*
		  fprintf(fp,"\n %d can see  %d, %d to %d ",KerPtr->MyIndex,ptr->from,ptr->from+1,ptr->to);
		  */
		}
		else
		  { if(IsXCanSeeVertex(KerPtr,ptr->from)&&
			   IsXCanSeeVertex(KerPtr,(ptr->from)+1)&&
			   IsXCanSeeVertex(KerPtr,ptr->to))
			{
			  if((NewEle=AllocateStarFromIndices(trin))!=NULL)
					   AddStarPolyToPseudoDecompList(KerPtr,max, ptr->from,
													 ptr->to,NewEle);
			  /*
			  fprintf(fp,"\n %d can see  %d, %d to %d ",KerPtr->MyIndex,ptr->from,ptr->from+1,ptr->to);
			  */
			}/* end of if */
		  }

		KerPtr = KerPtr->NextEle;

	  }/* end of while() */



	  if((NewEle=AllocateStarFromIndices(trin))!=NULL)
	  { P[ptr->from*max+ptr->to].RealMDList=NewEle; /* assign Minimum value */
		P[ptr->from*max+ptr->to].NumberOfRealList=1; /* assign Minimum value */
	  }
	  ptr = ptr->NextEle;
	}/* end of while */


	Print_KER(max);

		printf("\n I finished first phase \n");


	while(ptr!=NULL)   /* For each Pij */
	{
	  compare=1;
	  MinKerPtr=NULL;

	  /*Display_Polygon_Segments(Pol,max);
	  //Display_SubPolygon(Pol,max,ptr->from,ptr->to);
	  //MyGetch();*/

	  fprintf(fp,"\n Subpolygon from %d to %d ",ptr->from,ptr->to);

	  printf("\n Subpolygon from %d to %d ",ptr->from,ptr->to);

	  /* Check the result of double merge whether it is a star-shaped polygon. */

	  /* If double merge is not a star-shaped polygon then try to single merge */

	  Triangle = ptr->BaseTrianglesList;

	  while(Triangle!=NULL)   /* For each Base Triangle */
	  {
		KerPtr=KER;

	fprintf(fp,"\n Triangle I=%d M=%d J=%d ",Triangle->first,Triangle->middle,Triangle->last);

	printf("\n Triangle I=%d M=%d J=%d ",Triangle->first,Triangle->middle,Triangle->last);

	while(KerPtr!=NULL)  /* For each Potential Kernel Point */
	{
	  /* put all the KER points inside the triangle into REAL List*/

	  /* put all the KER points that can be visible from one of the
			 points ptr->from, ptr->from+1, ptr->to and put these points
		 into PSEUDO list.  */

	  trin[0]=Triangle->first;
	  trin[1]=Triangle->middle;
	  trin[2]=Triangle->last;
	  look=0;
	  /*
	  fprintf(fp,"\n <<<<<<<<<<<<<--------------->>>>>>>>>>");
	  fprintf(fp,"\n Triangle I=%d M=%d J=%d Point Index=%d X=%f Y=%f ",
			 Triangle->first,Triangle->middle,
			 Triangle->last,KerPtr->MyIndex,KerPtr->MyPoint.x,KerPtr->MyPoint.y);
	  */
	  printf("\n Point Index=%d X=%f Y=%f ",KerPtr->MyIndex,KerPtr->MyPoint.x,KerPtr->MyPoint.y);


	  if((KerPtr->MinDecompList[Triangle->first*max+Triangle->middle]!=NULL)&&
			 (KerPtr->MinDecompList[Triangle->middle*max+Triangle->last]!=NULL))
	  {	/* DOUBLE MINIMAL DECOMPOSITION EXIST? */
		/*fprintf(fp,"\n Double Merge >>>>>>");*/
		printf("\n Double Merge >>>>>>");

	/*		fprintf(fp,"\n Decomp[%d,%d] ",ptr->from,ptr->to);
			Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);

			fprintf(fp,"\n Decomp[%d,%d] ",Triangle->first,Triangle->middle);
			Print_MDList(fp,KerPtr->MinDecompList[Triangle->first*max+Triangle->middle],KerPtr->component_num[Triangle->first*max+Triangle->middle]);
		*/
			if(KerPtr->MinDecompList[ptr->from*max+ptr->to]!=NULL)
			{  previousptr = KerPtr->MinDecompList[ptr->from*max+ptr->to];
			   PreviousNumber = KerPtr->component_num[ptr->from*max+ptr->to];
			   KerPtr->MinDecompList[ptr->from*max+ptr->to] = NULL;
			   KerPtr->component_num[ptr->from*max+ptr->to] = 0;
			}/* end of if */

			AddStarPolyListToMinDecompList(KerPtr,max,ptr->from, ptr->to,
					   KerPtr->MinDecompList[Triangle->first*max+Triangle->middle],
					   KerPtr->component_num[Triangle->first*max+Triangle->middle]);

		  /*	fprintf(fp,"\n Decomp[%d,%d] + Decomp[%d,%d] = ",ptr->from,ptr->to,Triangle->first,Triangle->middle);
			Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);

			fprintf(fp,"\n Decomp[%d,%d] ",Triangle->middle,Triangle->last);
			Print_MDList(fp,KerPtr->MinDecompList[Triangle->middle*max+Triangle->last],KerPtr->component_num[Triangle->middle*max+Triangle->last]);
		  */
			AddStarPolyListToMinDecompList(KerPtr,max,ptr->from, ptr->to,
					   KerPtr->MinDecompList[Triangle->middle*max+Triangle->last],
					   KerPtr->component_num[Triangle->middle*max+Triangle->last]);

			if(PreviousNumber>0&&KerPtr->component_num[ptr->from*max+ptr->to]>PreviousNumber)
			{ DeallocateStarPolygonList(KerPtr->MinDecompList[ptr->from*max+ptr->to]);
			  KerPtr->MinDecompList[ptr->from*max+ptr->to] = previousptr;
			  KerPtr->component_num[ptr->from*max+ptr->to] = PreviousNumber;
			}
			else DeallocateStarPolygonList(previousptr);

			/*
			fprintf(fp,"\n Decomp[%d,%d] + Decomp[%d,%d] = ",ptr->from,ptr->to,Triangle->middle,Triangle->last);
			Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);

			/*MergeTriangle(KerPtr,max,ptr->from,ptr->to,trin);

			//fprintf(fp,"\n After Add Decomp[%d,%d] ",ptr->from,ptr->to);
			//Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);
*/
			/*
			fprintf(fp,"\n Double Merge  Point Index=%d X=%f Y=%f ",KerPtr->MyIndex,KerPtr->MyPoint.x,
										 KerPtr->MyPoint.y);
			fprintf(fp," Total : %d",KerPtr->component_num[ptr->from*max+ptr->to]);
			*/
			previousptr = NULL;
			PreviousNumber = 0;

			look=1;
		  }
		  else
			if((KerPtr->MinDecompList[Triangle->first*max+Triangle->middle]!=NULL)&&
			   (IsXCanSeeVertex(KerPtr,Triangle->last)))
			{ /* SINGLE MINIMAL DECOMPOSITION EXIST? */

			  /* If x is visible from Tj */
			  /*if(IsXCanSeeVertex(KerPtr,Triangle->last))
			  //{*/
			   /*	fprintf(fp,"\n Single Merge Lower <<<<<<<<<<<<<--------------->>>>>>>>>>");
				printf("\n Single Merge Lower <<------>>>>");


				fprintf(fp,"\n Decomp[%d,%d] ",Triangle->first,Triangle->middle);
				Print_MDList(fp,KerPtr->MinDecompList[Triangle->first*max+Triangle->middle],KerPtr->component_num[Triangle->first*max+Triangle->middle]);

				fprintf(fp,"\n Decomp[%d,%d] ",ptr->from, ptr->to);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);
				*/

				if(KerPtr->MinDecompList[ptr->from*max+ptr->to]!=NULL)
				{ previousptr = KerPtr->MinDecompList[ptr->from*max+ptr->to];
				  PreviousNumber = KerPtr->component_num[ptr->from*max+ptr->to];
				  KerPtr->MinDecompList[ptr->from*max+ptr->to] = NULL;
				  KerPtr->component_num[ptr->from*max+ptr->to] = 0;
				}/* end of if */


				/* Add real List */

				AddStarPolyListToMinDecompList(KerPtr,max,ptr->from, ptr->to,
									KerPtr->MinDecompList[Triangle->first*max+Triangle->middle],
									KerPtr->component_num[Triangle->first*max+Triangle->middle]);

				/*fprintf(fp,"\n Decomp[%d,%d] + Decomp[%d,%d] = ",ptr->from,ptr->to,Triangle->first,Triangle->middle);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);
				*/
				/* Add the Triangle */
				if(!MergeTriangle(KerPtr,max,ptr->from,ptr->to,trin))
				{ fprintf(fp,"\n Merge Error Single Error \n");

				  if((NewEle=AllocateStarFromTriangle(Triangle))!=NULL)
								AddStarPolyToMinDecompList(KerPtr,max,
										   ptr->from,ptr->to,NewEle);
				  else
					fprintf(fp,"\n Single Memory Error \n");
				}

				/*fprintf(fp,"\n After Triangle Adding Decomp[%d,%d] {",ptr->from,ptr->to);

				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);

				fprintf(fp,"\n P[%d,%d] {",Triangle->middle,Triangle->last);

				Print_MDList(fp,P[Triangle->middle*max+Triangle->last].RealMDList,
								P[Triangle->middle*max+Triangle->last].NumberOfRealList);
				*/
				AddStarPolyListToMinDecompListforP(KerPtr,max,ptr->from, ptr->to,
									P[Triangle->middle*max+Triangle->last].RealMDList,
									P[Triangle->middle*max+Triangle->last].NumberOfRealList);


				if(PreviousNumber>0&&KerPtr->component_num[ptr->from*max+ptr->to]>PreviousNumber)
				{ DeallocateStarPolygonList(KerPtr->MinDecompList[ptr->from*max+ptr->to]);
				  KerPtr->MinDecompList[ptr->from*max+ptr->to] = previousptr;
				  KerPtr->component_num[ptr->from*max+ptr->to] = PreviousNumber;
				}
				else DeallocateStarPolygonList(previousptr);

				previousptr = NULL;
				PreviousNumber = 0;

								/*printf("\n after PreviousNumber");*/
				/*
				fprintf(fp,"\n Afterr Add P values Decomp[%d,%d] ",ptr->from,ptr->to);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);

				/*
				fprintf(fp,"\n Single Merge  Point Index=%d X=%f Y=%f ",KerPtr->MyIndex,KerPtr->MyPoint.x,
							   KerPtr->MyPoint.y);
				fprintf(fp," Total : %d",KerPtr->component_num[ptr->from*max+ptr->to]);
				*/
				/*fprintf(fp,"\n Decomp[%d,%d] {",ptr->from,ptr->to);

				//Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],KerPtr->component_num[ptr->from*max+ptr->to]);
*/

				look=1;

			}	/* SINGLE MINIMAL DECOMPOSITION EXIST? */
		  else
			if((KerPtr->MinDecompList[Triangle->middle*max+Triangle->last]!=NULL)&&
			   (IsXCanSeeVertex(KerPtr,Triangle->first)))
			{ /* SINGLE MINIMAL DECOMPOSITION EXIST? */
			  /* If x is visible from Ti */
			  /*if(IsXCanSeeVertex(KerPtr,Triangle->first))
			  //{*/

				/*fprintf(fp,"\n Single Merge Upper <<<<<<<<<<<<<--------------->>>>>>>>>>");
				printf("\n Single Merge Upper <<<<------>>");

				fprintf(fp,"\n Decomp[%d,%d] ",Triangle->middle,Triangle->last);
				Print_MDList(fp,KerPtr->MinDecompList[Triangle->middle*max+Triangle->last],
								KerPtr->component_num[Triangle->middle*max+Triangle->last]);

				fprintf(fp,"\n Decomp[%d,%d] ",ptr->from, ptr->to);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],
								KerPtr->component_num[ptr->from*max+ptr->to]);
				*/
				if(KerPtr->MinDecompList[ptr->from*max+ptr->to]!=NULL)
				{ previousptr = KerPtr->MinDecompList[ptr->from*max+ptr->to];
				  PreviousNumber = KerPtr->component_num[ptr->from*max+ptr->to];
				  KerPtr->MinDecompList[ptr->from*max+ptr->to] = NULL;
				  KerPtr->component_num[ptr->from*max+ptr->to] = 0;
				}/* end of if */

				AddStarPolyListToMinDecompList(KerPtr,max,ptr->from, ptr->to,
								KerPtr->MinDecompList[Triangle->middle*max+Triangle->last],
								KerPtr->component_num[Triangle->middle*max+Triangle->last]);


				/*fprintf(fp,"\n Decomp[%d,%d] + Decomp[%d,%d] = ",ptr->from,ptr->to,Triangle->middle,Triangle->last);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],
								KerPtr->component_num[ptr->from*max+ptr->to]);

				/* swap Triangle->first with Triangle->last */

				k=trin[0];
				trin[0]=trin[2];
				trin[2]=k;

				if(!MergeTriangle(KerPtr,max,ptr->from,ptr->to,trin))
				{ /*fprintf(fp,"\n Merge Error Single Error \n");*/

				  if((NewEle=AllocateStarFromTriangle(Triangle))!=NULL)
								AddStarPolyToMinDecompList(KerPtr,max,
										   ptr->from,ptr->to,NewEle);
				  else
				   fprintf(fp,"\n Single Memory Error \n");
				}

				/*fprintf(fp,"\n After triangle Decomp[%d,%d] ",ptr->from,ptr->to);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],
								KerPtr->component_num[ptr->from*max+ptr->to]);


				fprintf(fp,"\n P[%d,%d] ",Triangle->first,Triangle->middle);
				Print_MDList(fp,P[Triangle->first*max+Triangle->middle].RealMDList,
								P[Triangle->first*max+Triangle->middle].NumberOfRealList);

				 */
				AddStarPolyListToMinDecompListforP(KerPtr,max,ptr->from, ptr->to,
									P[Triangle->first*max+Triangle->middle].RealMDList,
									P[Triangle->first*max+Triangle->middle].NumberOfRealList);

								/*printf("\n before PreviousNumber");*/
				if(PreviousNumber>0&&KerPtr->component_num[ptr->from*max+ptr->to]>PreviousNumber)
				{ DeallocateStarPolygonList(KerPtr->MinDecompList[ptr->from*max+ptr->to]);
				  KerPtr->MinDecompList[ptr->from*max+ptr->to] = previousptr;
				  KerPtr->component_num[ptr->from*max+ptr->to] = PreviousNumber;
				}
				else DeallocateStarPolygonList(previousptr);

				previousptr = NULL;
				PreviousNumber = 0;

								/*printf("\n after PreviousNumber");*/
				/*
				fprintf(fp,"\n After Add P values Decomp[%d,%d] ",ptr->from,ptr->to);
				Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],
								KerPtr->component_num[ptr->from*max+ptr->to]);


				/*fprintf(fp,"\n Single Merge  Point Index=%d X=%f Y=%f ",KerPtr->MyIndex,KerPtr->MyPoint.x,
							 KerPtr->MyPoint.y);
				fprintf(fp," Total : %d",KerPtr->component_num[ptr->from*max+ptr->to]);
				*/
				look=1;
			}
		  else /* MERGE IS NOT POSSIBLE */

			  if((IsInsideTheTriangle(Pol[Triangle->first],Pol[Triangle->middle],
								   Pol[Triangle->last],KerPtr->MyPoint))||
				 (IsXCanSeeVertex(KerPtr,Triangle->first)&&
				  IsXCanSeeVertex(KerPtr,Triangle->middle)&&
				  IsXCanSeeVertex(KerPtr,Triangle->last)&&
				  Intersect(KerPtr->MyPoint,Pol[Triangle->middle],
							Pol[Triangle->first],Pol[Triangle->last])))
			  {
				 /*fprintf(fp,"\n Inside Triangle <<<<<<<<<<<<<--------------->>>>>>>>>>");
				 printf("\n Inside Triangle <<<<------>>>>>");

				 fprintf(fp,"\n P[%d,%d] ",Triangle->first,Triangle->middle);
				 Print_MDList(fp,P[Triangle->first*max+Triangle->middle].RealMDList,P[Triangle->first*max+Triangle->middle].NumberOfRealList);

				 /*if(KerPtr->MinDecompList[ptr->from*max+ptr->to]!=NULL)
				 { previousptr = KerPtr->MinDecompList[ptr->from*max+ptr->to];
				  PreviousNumber = KerPtr->component_num[ptr->from*max+ptr->to];
				  KerPtr->MinDecompList[ptr->from*max+ptr->to] = NULL;
				  KerPtr->component_num[ptr->from*max+ptr->to] = 0;
				 } end of if */

				 /*
				 fprintf(fp,"\n Decomp[%d,%d] ",ptr->from,ptr->to);
				 Print_MDList(fp,KerPtr->MinDecompList[ptr->from],
								 KerPtr->component_num[ptr->to]);
				 */
				 AddStarPolyListToMinDecompListforP(KerPtr,max,ptr->from, ptr->to,
								P[Triangle->first*max+Triangle->middle].RealMDList,
								P[Triangle->first*max+Triangle->middle].NumberOfRealList);
				 /*
				 fprintf(fp,"\n Decomp[%d,%d] + P[%d,%d] = ",ptr->from,ptr->to,Triangle->first,Triangle->middle);
				 Print_MDList(fp,KerPtr->MinDecompList[ptr->from],
								 KerPtr->component_num[ptr->to]);
				 */

				  if((NewEle=AllocateStarFromTriangle(Triangle))!=NULL)
								AddStarPolyToMinDecompList(KerPtr,max,
										   ptr->from,ptr->to,NewEle);
				  else
					   fprintf(fp,"\n Inside Memory Error \n");
				 /*
				 fprintf(fp,"\n After Triangle Decomp[%d,%d] ",ptr->from,ptr->to);
				 Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],
								KerPtr->component_num[ptr->from*max+ptr->to]);

				 fprintf(fp,"\n P[%d,%d] ",Triangle->middle,Triangle->last);
				 Print_MDList(fp,P[Triangle->middle*max+Triangle->last].RealMDList,
								 P[Triangle->middle*max+Triangle->last].NumberOfRealList);
				 */
				 AddStarPolyListToMinDecompListforP(KerPtr,max,ptr->from, ptr->to,
								P[Triangle->middle*max+Triangle->last].RealMDList,
								P[Triangle->middle*max+Triangle->last].NumberOfRealList);

				 /*
				 fprintf(fp,"\n Decomp[%d,%d] + P[%d,%d] = ",ptr->from,ptr->to,Triangle->middle,Triangle->last);
				 Print_MDList(fp,KerPtr->MinDecompList[ptr->from*max+ptr->to],
								 KerPtr->component_num[ptr->from*max+ptr->to]);
				 fprintf(fp," Total : %d",KerPtr->component_num[ptr->from*max+ptr->to]);

				 /*if(KerPtr->component_num[ptr->from*max+ptr->to]>PreviousNumber)
				 { DeallocateStarPolygonList(KerPtr->MinDecompList[ptr->from*max+ptr->to]);
				   KerPtr->MinDecompList[ptr->from*max+ptr->to] = previousptr;
				   KerPtr->component_num[ptr->from*max+ptr->to] = PreviousNumber;
				 }
				 else DeallocateStarPolygonList(previousptr);

				 previousptr = NULL;
				 PreviousNumber = 0;
				 */
				 look=1;
			  }

		/*  printf("\n Before Look ");*/


	  if(look)
	  { /*fprintf(fp,"\n Inside  Minimum Comparison Minimum=");*/
		if(!compare)
		fprintf(fp,"%d ",MinKerPtr->component_num[ptr->from*max+ptr->to]);
		else fprintf(fp," N/A  ");
		fprintf(fp," Point=%d ",KerPtr->component_num[ptr->from*max+ptr->to]);
			if(compare)
		{ MinKerPtr=KerPtr;compare=0;
			  /*fprintf(fp,"\n Initial Minimum ");*/
		}
		else
		  if((KerPtr->component_num[ptr->from*max+ptr->to]>0)&&
			 (KerPtr->component_num[ptr->from*max+ptr->to]<
			  MinKerPtr->component_num[ptr->from*max+ptr->to]))
			  { MinKerPtr=KerPtr;
			/*fprintf(fp,"\n Minimum is changed ");*/

		   }
	  }

	  KerPtr = KerPtr->NextEle;

	  /*printf("\n New Element ");*/

	}/* end of while() */

	Triangle = Triangle->NextEle;
	/*printf("\n New Triangle ");*/

	  }/* end of while */

	  if(MinKerPtr!=NULL)
	  { /*
		fprintf(fp,"\n Point Index=%d X=%f Y=%f ",MinKerPtr->MyIndex,MinKerPtr->MyPoint.x,
										   MinKerPtr->MyPoint.y);

		fprintf(fp,"\n RESULT -- Decomp[%d,%d] --> ",ptr->from,ptr->to);

/*		//Print_MDList(fp,MinKerPtr->MinDecompList[ptr->from*max+ptr->to],MinKerPtr->component_num[ptr->from*max+ptr->to]);
*/

		P[ptr->from*max+ptr->to].RealMDList = MinKerPtr->MinDecompList[ptr->from*max+ptr->to];
		P[ptr->from*max+ptr->to].NumberOfRealList = MinKerPtr->component_num[ptr->from*max+ptr->to];
		/*if(!CopyStarPolyListToP(MinKerPtr,max,ptr->from,ptr->to,fp))*/
				 /*fprintf(fp,"\n Copy Memory Error \n");*/

		fprintf(fp,"\n P[%d,%d] --> ",ptr->from,ptr->to);

		Print_MDList(fp,P[ptr->from*max+ptr->to].RealMDList,P[ptr->from*max+ptr->to].NumberOfRealList);

		fprintf(fp,"\n --->>> ");

	  }

	  /*if(MinKerPtr!=NULL) DisplayPointColor(MinKerPtr->MyPoint,RED);
	  //MyGetch();*/

	  ptr = ptr->NextEle;

	}/* end of while */

  }/* end of if */
  fclose(fp);
}/* end of DPProcedure() */

struct VisiblePolyEle *Find_VisibListPtr(int SearchIndex)
{ struct PointNode *ptr1;
  int notFound=true;
  ptr1=PolygonVertexVisiblityList;
  while(ptr1!=NULL&&notFound)
  { if(SearchIndex==ptr1->MyIndex) notFound=false;
	else ptr1=ptr1->NextEle;
  }/* end of while */
  return(notFound?NULL:ptr1->VisibilityPolyList);
}/* end of VisiblePolyEle() */

CanSee(struct VisiblePolyEle *Ele, int SearchKey)
{ int notFound=true;
  struct VisiblePolyEle *ptr;
  ptr=Ele;
  while(ptr!=NULL&&notFound)
  { if(ptr->index==SearchKey) notFound=false;
	else ptr=ptr->NextEle;
  }/* end of while */
  return(!notFound);
}/* end of CanSee() */

void Handle_Decomposition(int max)
{ struct StarPolygon *ptr1;
  struct StarPolygon *ptr2;
  struct StarPolygon *ptr2prev;
  struct VisiblePolyEle *visi;
  int k,j,i,p;
  ptr1=P[max-1].RealMDList;
  while(ptr1!=NULL&&ptr1->NextEle!=NULL)
  { ptr2=ptr1->NextEle;
	for(i=0;i<ptr1->numberOfPoints;i++)
	{
	  visi=Find_VisibListPtr(ptr1->elements[i]);

	  k=0;
	  for(j=0;j<ptr1->numberOfPoints;j++)
		if(i!=j)
		  k = k + CanSee(visi,ptr1->elements[j]);
		else k++;
	  if(visi!=NULL&&k==ptr1->numberOfPoints)
	  {
		ptr2prev=ptr1;
		while(ptr2!=NULL)
		{ k=0;

		  for(j=0;j<ptr2->numberOfPoints;j++)
			 if(ptr1->elements[i]!=ptr2->elements[j])
				  k = k + CanSee(visi,ptr2->elements[j]);
			 else k++;
		  if(k==ptr2->numberOfPoints)
		  { printf("\n %d can see ",ptr1->elements[i]);
			for(j=0;j<ptr2->numberOfPoints;j++)
				  printf(" %d, ",ptr2->elements[j]);

			ptr2prev->NextEle=ptr2->NextEle;
			P[max-1].NumberOfRealList--;
		  }
		  else ptr2prev=ptr2;
		  ptr2=ptr2prev->NextEle;
		}/* end of while() */
	  }/* end of if */
	}/* end of for */
	ptr1=ptr1->NextEle;
  }/* end of while */
}/* Handle_Decomposition() */

Read_Polygon(char *FileName,struct point **plgn, int *maxele)
{ FILE *fp;
  int linecount=0;
  int intbuf,retval,i;
  float floatbuf;
  float fl1,fl2;
  struct point *polygon;

  printf("\n File Name : %s \n",FileName);

  if((fp=fopen(FileName,"r"))!=NULL)
  { fscanf(fp,"%f \n",&floatbuf);
	intbuf=(int)floatbuf;

	if((polygon=(struct point *)calloc(intbuf,sizeof(struct point)))!=NULL)
	{ while(linecount<intbuf&&((retval=fscanf(fp,"%f %f \n",&fl1,&fl2))!=EOF))
	  if(retval==2)
	  { polygon[linecount].x=fl1;
		polygon[linecount].y=fl2;
		linecount++;
	  }
	}
	*maxele=linecount;
	*plgn=polygon;
	fclose(fp);
  }/* end of if */
  for(i=0;i<*maxele;i++)
	printf("\n index=%d  x=%f  y=%f ",i,polygon[i].x,polygon[i].y);
  /*getch();*/
  return retval;
}/* end of Read_Polygon() */

void Read_Filename(char *FileName)
{ char str[20];
  do
  { printf("\n Enter File Name : ");
	gets(str);
	if(strlen(str)>20)
	  printf("\n \n Error : File name can not contain more than 20 characters!\n");
	else if(strlen(str)==0)
			 printf("\n \n Error : File name can not be empty!\n");
  } while(strlen(str)==0&&strlen(str)>20);
  sprintf(FileName,"%s",str);
}/* end of Read_Filename() */

void tempmain(char *fileName)
{ /*int gdriver = DETECT, gmode, errorcode;
  //struct point poly[10];*/
  struct point *poly;
  int max,i;
  float angle1,angle2;

  printf("\n File Name : %s \n",fileName);

  Read_Polygon(fileName,&poly,&max);

/*  Init_Graph();*/

  Display_Polygon(poly,max);

/*  DrawInteriorLines();*/

  FindIntersectsinInteriorLines(max);


  AddVerticesToKER(poly,max);

  /*MyGetch();


//  DrawKER();

  //MyGetch();*/

  FindVisibilityListOfKER(poly,max);

  /*MyGetch();

//  Display_Polygon_Segments(poly,max);

  //setcolor(RED);*/

  FindVisibilityOfVertexList(poly, max);

  /*MyGetch();*/

  DefineSubPolygonList();

  FindSubPolygonList(poly,max);

  /*MyGetch();

//  DisplaySubPolygonList(poly,max);

  //MyGetch();*/

  Print_SubPolygonList();

  FindBaseTriangles(poly,max);

  /*MyGetch();

//  outtextxy(20,20,"DP Procedure");*/

  printf("\n STATUS : DP Procedure \n ");

  DPProcedure(poly,max);

  printf("\n STATUS : DP Procedure End \n ");

  /*MyGetch();

  //setcolor(MAGENTA);

//  DisplayPMatrix(P[max-1].RealMDList,poly,P[max-1].NumberOfRealList);

  //MyGetch();*/

  Print_KERList();

/*  DrawKER();*/

  Print_P(max);

  /*MyGetch();


//  closegraph(); */
  Handle_Decomposition(max);

  Print_Result(poly,max);

  printf("\n STATUS : Program End \n ");

  DeallocateInteriorLines();
  printf("\n Interior Lines are deallocated");
  DeallocateKER(max);
  printf("\n KER Lines are deallocated");
  DeallocatePolyVisibility();
  printf("\n Visibility  are deallocated");
  DeallocateSubPolyList();
  printf("\n Subpolygons are deallocated");
  DeallocatePMatrix();
  printf("\n P Matrix are deallocated");

  free(poly);

 }

void main(int argc, char *argv[])
{ 
  struct point *poly;
  int max,i;
  float angle1,angle2;
  char fileName[21];
  if(nproc==0)
  { if(argc>1)
   sprintf(fileName,"%s",argv[1]);
  else
	Read_Filename(fileName);

  fileName[20]=NULL;
  tempmain(fileName);
  }
  printf("\n Proc id : %d is out of here ");
}
