/***************************************************************************
 *   Copyright (C) 2005 by Juergen Thies                                   *
 *   layout@juergenthies.de                                                *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#include "pointarray.h"
#include "element.h"
#define _USE_MATH_DEFINES
#include <math.h>
//#include <limits.h>

pointArray::pointArray()
 : QPolygon()
{
}


pointArray::~pointArray()
{
}

bool pointArray::add(pointArray *array){
if (array->size()==0) return false;
  if (element::pointInPolygon(*array,point(0))){
  	pointArray help=(*array);
	*array=*this;
	*this=help;
	}
  else if (!element::pointInPolygon(*this,array->point(0))) {  //printf("no insert\n");
  	return false;}
  //printf("insert\n");
  QPoint p=array->point(0);
  int index=0;
  for (int i=1; i<array->size()-1;i++){
  	if (array->point(i).x()>p.x()) {
		p=array->point(i);
		index=i;
		}
	}
  int pos=-1;
  QPoint pc,padd;
  for (int k=0;k<size()-1;k++) 
	  for (int i=0;i<array->size()-1;i++) {
		  if (element::onLine(point(k),point(k+1),array->point(i))){
			  if ((point(k).x()<point(k+1).x())&&(array->point(i+1).y()>array->point(i).y())){
						pos=int(k);
						index=i;
						p=array->point(i);
						padd=array->point(i);
					}
			  if ((point(k).x()>point(k+1).x())&&(array->point(i+1).y()<array->point(i).y())){
						pos=int(k);
						index=i;
						p=array->point(i);
						padd=array->point(i);
					}				

		  }
	  
	}
  //printf("padd: %d %d\n",padd.x(),padd.y());
  float dist=(float)(99999999.0);
  if (pos==-1)
  for (int k=0;k<size()-1;k++) {
  	if (element::cutPoint(point(k),point(k+1),p,QPoint((INT_MAX),p.y()),&pc)){
		if (element::distance(p,pc)<dist) {
                            dist=element::distance(p,pc);
                            pos=(int)k;
                            padd=pc;
                        }
		}
	}
  if (pos==-1) { //printf("error\n");
  	return false;}
  //printf("insert at %d\n",pos);
  uint neugross,altgross;
  //printf("pointarray: %d array: %d insert pos: %d\n",size(),array->size(),pos);
  altgross=size();
  neugross=size()+array->size()+4;
  resize(neugross);
              // printf("a: %d n: %d\n",altgross,neugross);
  for (int i=neugross;i>pos+array->size()+4;i--) {
  	setPoint(i-1,point(altgross-neugross+i-1));
                     //printf("3 %d %d\n",i-1,altgross-neugross+i-1);
                     //printf("p %d %d\n",point(altgross-neugross+i-1).x(),point(altgross-neugross+i-1).y());
        }
  //printf("3a pc %d \n",pos+array->size()+3);
  setPoint(pos+array->size()+3,padd);
  setPoint(pos+array->size()+4,padd);
  for (int i=index;i<array->size();i++) {
    	setPoint(pos+i-index+2,array->point(i));
                     //printf("4 %d %d\n",pos+i-index+2,i);
                     //printf("p %d %d\n",array->point(i).x(),array->point(i).y());
        }
  for (int i=0;i<=(int)index;i++) {
        setPoint(pos+array->size()-index+i+2,array->point(i));
                     //printf("5 %d %d\n",pos+array->size()-index+i+2,i);
                     //printf("p %d %d\n",array->point(i).x(),array->point(i).y());
        }
  //printf("3a pc %d \n",pos+1);
  setPoint(pos+1,padd);
  //printf("p %d %d\n",padd.x(),padd.y());
  //printf("end add\n");
  return true;
}

pointArray pointArray::cut(uint pos){
pointArray pa1,pa2;
uint siz=size();
if (pos>=siz) return pa1;
for (uint i=0;i<=pos;i++) pa1.attachPoint(point(i));
for (uint i=pos;i<siz;i++) pa2.attachPoint(point(i));
*this=pa1;
return pa2;
}


void pointArray::move(QPoint pos){
 translate(pos.x(),pos.y());
}


void pointArray::map(strans m){
 int i;
 QPoint p;
 for (i=0;i<size();i++){
  	p=point(i);
	p=m.matrix.map(p);
	setPoint(i,p);
	}
}


void pointArray::clean(){
QPoint p;
double a;
bool b;
//printf("start clean\n");
//for (uint i=0; i<size();i++){printf("c#%d x %d y %d\n",i,point(i).x(),point(i).y());}
if ( size()>2) 
	if ( point(0)!= point( size()-1)) 
		{
		addPoint( size()-1);
		 setPoint( size()-1, point(0));
		}
int anz=0;
for (a=0;((a<350)||(a>370))&&(anz<2);){
	a=0;
	//überflüssige Punkte entfernen
	for (int i=0;i<(int) size()-1;i++){
		if ( size()<4) return; //no area
		if ( point(i)== point(i+1)){
		  	deletePoint(i+1);
		  	if (((int) size())==(i+1)){ setPoint(0, point(i));}
			i--;}
		if (setup::defaultPolygonRemoveNotNeededPoints){
		if (i<(int) size()-2){
		if (element::nearlyParallel( point(i), point(i+1), point(i+1), point(i+2))){
			 deletePoint(i+1);
			 i=0;}}
		if ( size()>3){
		while ( ( size()>3)&&(element::parallel( point(0), point(1), point( size()-1),  point( size()-2)))){ deletePoint( size()-1);
						 setPoint(0, point( size()-1));}}
		}}
	//punkte sortieren
	for (int i=0; i< size()-2;i++){
 		a+=element::angle( point(i), point(i+1), point(i+2));}
	if ( size()>3){
		a+=element::angle( point( size()-2), point(0), point(1));}
	// Punkte linksdrehend
	if (a<-185) {
		for (int i=1; i<( size())/2;i++){
				p= point( size()-i-1);
				 setPoint( size()-i-1, point(i));
				 setPoint(i,p);
			}
		a=-a;
		}
	// entartete Polygone bereinigen (simple selfintersecting) mit schnittpunkt von zwei greaden

	if (setup::defaultPolygonFixSelfintersectingPolygons){
	if ((a>370)||((a<350)&&(a>-350))){
		for (int i=0; i< size()-1;i++){
			for (int j=i+2;j< size()-1;j++){
				b=element::cutPoint2( point(i), point(i+1), point(j), point(j+1),&p);
				if (b)if(!((i==0)&&(j== size()-2))){
					addPoint(j+1);
					j++;
					 setPoint(j,p);
					addPoint(i+1);
					i++;
					 setPoint(i,p);
					for (int k=i+1;k<=(i+j)/2;k++){
						p= point(j-k+i+1);
						 setPoint(j-k+i+1, point(k));
						 setPoint(k,p);	}	
					j= size();
					i= size();}
				}}}
	// remove selfintersection 
	if ( size()>=8){bool ende2=false;
	for (int i=0;i<(int) size()-1;i++){ bool ende1=false;
		for (int j=i+2;j<(int) size()-1;j++){
			//printf("0 i: %d j: %d\n",i,j);
			if (element::identical( point(i), point(i+1), point(j+1), point(j))){
				//two identical lines
				//printf("identical j-i %d %d\n",j,i);
				int h1,h2,h3,h4,h5,h6;
				bool side=true;
				bool change=false;
				bool doBreak=false;
				if ( point(j+1)== point(i)){
					change=true;
					h1 =i-1;if (h1==(-1)) h1= size()-2;
					h2=j+2; if (h2==(int) size()) h2=1; 
					//printf("1 %d %d\n",h1,i);
					double d1,d2;
					d1=180-element::angle( point(h1), point(i), point(i+1));
					d2=180-element::angle( point(h2), point(j+1), point(j));
					if (d1<0) d1+=360;
					if (d2<0) d2+=360;
					//printf("d1 %f d2 %f\n",d1,d2);
					if (d1<d2){side=false;}}
				else if (element::onLine2( point(i), point(i+1), point(j+1))){
					//printf("2\n");
					change=true;
					h2=j+2; if (h2==(int) size()) h2=1;
					if (element::distance( point(i), point(i+1), point(h2))<0){side=false;}}
				else if (element::onLine2( point(j), point(j+1), point(i))){
					change=true;
					//printf("3\n");
					h1=i-1; if (h1==-1) h1= size()-2;
					if (element::distance( point(j), point(j+1), point(h1))<0){side=false;}}
				else doBreak=true;
				if (!doBreak){
				//printf("1 i: %d j: %d\n",i,j);
				//printf("change %d\n",change);	
				//printf("side %d\n",side);	
				while ( point(j)== point(i+1)){j--;i++;
					if (j==(-1)) {j= size()-2;ende1=true;}
					if (i==(int) size()) {i=1;ende2=true;} }
				h2=i+1; if (h2==(int) size()) h2=1; 
				h3=h2+1; if (h3==(int) size()) h3=1; 
				h1=j-1; if (h1==-1) h1= size()-2; 
				h4=j+1; if (h4==(int) size()) h4=1; 
				h5=h4+1; if (h5==(int) size()) h5=1; 
				h6=i-1; if (h6==-1) h6= size()-2; 
				if (element::onLine2( point(i), point(h2), point(j))){
					//printf("4\n");
					if ((element::distance( point(i), point(h2), point(h1))<0)!=side){change=false;}}
				else if (element::onLine2( point(j), point(h4), point(h2))){
					//printf("5\n");
					if ((element::distance( point(j), point(h4), point(h3))<0)!=side){change=false;}}
				else {//printf("6\n");
					double d1,d2;
					d1=180-element::angle( point(h6), point(i), point(h2));
					d2=180-element::angle( point(h5), point(h4), point(j));
					if (d1<0) d1+=360;
					if (d2<0) d2+=360;
					//printf("d1 %f d2 %f\n",d1,d2);
					if ((d1<d2)!=side){change=false;}}
				if (change){
					for (uint k=(uint)i+1; k<(uint)(i+j+2)/2;k++){
						//printf(" tausche %d %d\n",j+i-k+1,k);
						p= point(j+i-k+1);
						 setPoint(j+i-k+1, point(k));
						 setPoint(k,p);}}
				}
				//printf("2 i: %d j: %d\n",i,j);
				//printf("change %d\n",change);	
			}
			else if (( point(i)== point(j+1))&&( point(i+1)!= point(j))&&(j!= size()-2)){
				//printf("check %d %d\n",i,j);
				// only one identical point and not parallel
				bool change=false;
				int h1,h2;
				h1 =i-1;if (h1==(-1)) h1= size()-2;
				h2=j+2; if (h2==(int) size()) h2=1; 
				double d1,d2,d3;
				d1=180-element::angle( point(h1), point(i), point(i+1));
				d2=180-element::angle( point(h1), point(i), point(j));
				d3=180-element::angle( point(h1), point(i), point(h2));
				//printf("1 %f 2 %f 3 %f\n",d1,d2,d3);
				if ((d2<d1)&&(d3>d1)){change=true;}
				if ((d2>d1)&&(d3<d1)){change=true;}
				if (change){
					for (uint k=(uint)i+1; k<(uint)(i+j+2)/2;k++){
						//printf(" tausche %d %d\n",j+i-k+1,k);
						p= point(j+i-k+1);
						 setPoint(j+i-k+1, point(k));
						 setPoint(k,p);}}
				}
			if (ende1||ende2) break;
		}
		if (ende2) break;}
	}}
	//printf("a: %f anz %d\n",a, size());
	anz++;
 }
 //printf("end clean\n");
 //for (uint i=0; i< size();i++){printf("c#%d x %d y %d\n",i, point(i).x(), point(i).y());}
}

void pointArray::cleanSimple(){
QPoint p;
double a;
//bool b;
//printf("start clean\n");
//for (uint i=0; i<size();i++){printf("c#%d x %d y %d\n",i,point(i).x(),point(i).y());}
if ( size()>2) 
	if ( point(0)!= point( size()-1)) 
		{
		addPoint( size()-1);
		 setPoint( size()-1, point(0));
		}

	a=0;
	//überflüssige Punkte entfernen
	for (int i=0;i<(int) size()-1;i++){
		if ( size()<4) return; //no area
		if ( point(i)== point(i+1)){
		  	deletePoint(i+1);
		  	if (((int) size())==(i+1)){ setPoint(0, point(i));}
			i--;}
		if (setup::defaultPolygonRemoveNotNeededPoints){
		if (i<(int) size()-2){
		if (element::nearlyParallel( point(i), point(i+1), point(i+1), point(i+2))){
			 deletePoint(i+1);
			 i=0;}}
		if ( size()>3){
		while ( ( size()>3)&&(element::parallel( point(0), point(1), point( size()-1),  point( size()-2)))){ deletePoint( size()-1);
						 setPoint(0, point( size()-1));}}
		}}
	//punkte sortieren
	for (int i=0; i< size()-2;i++){
 		a+=element::angle( point(i), point(i+1), point(i+2));}
	if ( size()>3){
		a+=element::angle( point( size()-2), point(0), point(1));}
	// Punkte linksdrehend
	if (a<-185) {
		for (int i=1; i<( size())/2;i++){
				p= point( size()-i-1);
				 setPoint( size()-i-1, point(i));
				 setPoint(i,p);
			}}
 
 //printf("end clean\n");
 //for (uint i=0; i< size();i++){printf("c#%d x %d y %d\n",i, point(i).x(), point(i).y());}
}

void pointArray::cleanUnneeded(){
QPoint p;
//double a;
//bool b;
//printf("start clean\n");
//for (uint i=0; i<size();i++){printf("c#%d x %d y %d\n",i,point(i).x(),point(i).y());}
if ( size()>2) 
	if ( point(0)!= point( size()-1)) 
		{
		addPoint( size()-1);
		 setPoint( size()-1, point(0));
		}
	//überflüssige Punkte entfernen
for (int i=0;i<(int) size()-1;i++){
		if ( size()<4) return; //no area
		if ( point(i)== point(i+1)){
		  	deletePoint(i+1);
		  	if (((int) size())==(i+1)){ setPoint(0, point(i));}
			i--;}
		if (setup::defaultPolygonRemoveNotNeededPoints){
		if (i<(int) size()-2){
		if (element::nearlyParallel( point(i), point(i+1), point(i+1), point(i+2))){
			 deletePoint(i+1);
			 i=0;}}
		if ( size()>3){
		while ( ( size()>3)&&(element::parallel( point(0), point(1), point( size()-1),  point( size()-2)))){ deletePoint( size()-1);
						 setPoint(0, point( size()-1));}}
		}}
}

void pointArray::resize(int i){
  if (i!=size()) QPolygon::resize(i);
}

void pointArray::deletePoint(uint pos){
for (int i=pos;i<size()-1;i++){
	setPoint(i,point(i+1));}
resize(size()-1);
}

void pointArray::addPoint(uint pos){
resize(size()+1);
for (uint i=size()-1;i>pos;i--){
	setPoint(i,point(i-1));}}

void pointArray::attachPoint(QPoint p){
(*this)<<p;
}

void pointArray::insert(uint i, QPoint p){
QPolygon::insert(i,p);
}

void pointArray::flip(){
pointArray p=*this;
for (int i=0;i<size();i++){
 setPoint(i,p.point(size()-i-1));
 }
}

double pointArray::area(){
  double a=0;
  for (int i=0; i<size()-1;i++){
  	a+=(double(point(i).y()+point(i+1).y())/2*(double(point(i).x()-point(i+1).x())));
  }
  if (a<0){a*=-1;}
  return a;
}

double pointArray::angle(){
	double a=0;
	for (int i=0; i< size()-2;i++){
 		a+=element::angle( point(i), point(i+1), point(i+2));}
	if ( size()>3){
		a+=element::angle( point( size()-2), point(0), point(1));}
	return a;
}

double pointArray::length(){
	double a=0;
	for (int i=0; i< size()-1;i++){
 		a+=element::distance( point(i), point(i+1));}
	return a;
}

void pointArray::sizeAdjust(int value){
	//printf("size\n");
	//for (int i=0; i<size();i++)
	//	printf("a: %d ; %d\n",point(i).x()  , point(i).y());
	
	int sig=1;
	if (angle()<0) sig=-1;
	//printf("size %d ; %d \n",minSize(),(-1*sig*2*value));
	if (minSize()<(-1*sig*2*value)) {
		resize(2);
		setPoint(1,point(0));
		//printf("delete\n");
		return;
	}
	pointArray array;
	array.resize(this->size());
	QMatrix matrix;
	QPoint p1,p2,p3,p4;
	for (int i=0; i<(int)this->size()-1;i++){
		matrix.setMatrix(1,0,0,1,0,0);
		double d=element::angle(this->point(i),this->point(i+1));
		matrix.rotate(d);
		matrix.translate(0,-value);
		matrix.rotate(-d);
		p1=matrix.map(this->point(i));
		p2=matrix.map(this->point(i+1));
		//printf("p1: %d %d\n",p1.x(),p1.y());
		//printf("p2: %d %d\n",p2.x(),p1.y());
		if (i>0) {
			bool b=element::cutPoint3(p1,p2,p4,array.point(i-1),&p3);
			if (!b) array.setPoint(i,p1);
			else 
				array.setPoint(i,p3);
			//printf("new: %d %d\n",array.point(i).x(),array.point(i).y());
			//if (b) printf("b\n");
		}
		else array.setPoint(0,p1);
		p4=p2;
		if (p4==array.point(i)) p4=p1;
		}
	bool b=element::cutPoint3(p1,p2,array.point(0),array.point(1),&p3);
	if (!b) array.setPoint(0,p1);
	else array.setPoint(0,p3);
	array.setPoint(array.size()-1,array.point(0));
	//printf("last/start: %d %d\n",array.point(0).x(),array.point(0).y());
	//if (b) printf("b\n");
	*this=array;
}

void pointArray::sizeAdjust(int valueX,int valueY){
	//printf("size\n");
	//for (int i=0; i<size();i++)
	//	printf("a: %d ; %d\n",point(i).x()  , point(i).y());
	
	int sig=1;
	if (angle()<0) sig=-1;
	
	int value=valueX;
	if (valueY<value) value=valueY;
	//printf("size %d ; %d \n",minSize(),(-1*sig*2*value));
	if (minSize()<(-1*sig*2*value)) {
		resize(2);
		setPoint(1,point(0));
		//printf("delete\n");
		return;
	}
	pointArray array;
	array.resize(this->size());
	QMatrix matrix;
	QPoint p1,p2,p3,p4;
	for (int i=0; i<(int)this->size()-1;i++){
		matrix.setMatrix(1,0,0,1,0,0);
		double d=element::angle(this->point(i),this->point(i+1));
		matrix.rotate(d);
		double dP=d;
		if (dP<0) dP=-dP;
		if (dP>90) dP=180-dP;
		//printf("%d %f\n",element::runden(dP),d);
		double dPi=90-dP;
		int move=element::runden(dP/90*valueX+dPi/90*valueY);
		matrix.translate(0,-move);
		matrix.rotate(-d);
		p1=matrix.map(this->point(i));
		p2=matrix.map(this->point(i+1));
		//printf("p1: %d %d\n",p1.x(),p1.y());
		//printf("p2: %d %d\n",p2.x(),p1.y());
		if (i>0) {
			bool b=element::cutPoint3(p1,p2,p4,array.point(i-1),&p3);
			if (!b) array.setPoint(i,p1);
			else 
				array.setPoint(i,p3);
			//printf("new: %d %d\n",array.point(i).x(),array.point(i).y());
			//if (b) printf("b\n");
		}
		else array.setPoint(0,p1);
		p4=p2;
		if (p4==array.point(i)) p4=p1;
		}
	bool b=element::cutPoint3(p1,p2,array.point(0),array.point(1),&p3);
	if (!b) array.setPoint(0,p1);
	else array.setPoint(0,p3);
	array.setPoint(array.size()-1,array.point(0));
	//printf("last/start: %d %d\n",array.point(0).x(),array.point(0).y());
	//if (b) printf("b\n");
	*this=array;
}

int pointArray::minSize(){
int i=1;
int xmin,ymin,xmax,ymax;
xmax=xmin=point(i).x();
ymax=ymin=point(i).y();
for (i=1;i<size();i++){
	if (point(i).x()>xmax) xmax=point(i).x();
	if (point(i).y()>ymax) ymax=point(i).y();
	if (point(i).x()<xmin) xmin=point(i).x();
	if (point(i).y()<ymin) ymin=point(i).y();
	}
int size_=xmax-xmin;
if (ymax-ymin<size_) size_=ymax-ymin;
return size_;
}

QList<pointArray> pointArray::seperate(){
QList<pointArray> l;
for (int i=0;i<(int) size()-1;i++){ 
		for (int j=i+2;j<(int) size()-1;j++){
			//printf("0 i: %d j: %d\n",i,j);
			if (element::identical( point(i), point(i+1), point(j+1), point(j))){
			  if (point(j+1)==point(i)){
				    pointArray p;
					for (int k=0;k<=i;k++) p.attachPoint(point(k));
					for (int k=j+2;k<size();k++) p.attachPoint(point(k));
					p.cleanUnneeded();
					l<<p.seperate();
					p.clear();
					for (int k=i+1;k<=j;k++) p.attachPoint(point(k));
					p.attachPoint(point(i+1));
					l<<p.seperate();
					//printf("split %d\n",l.size());
					//for (int k=0;k<l.size();k++) printf("%d\n",l[k].size());
					return l;
					}
			  else if (element::onLine2(point(i),point(i+1),point(j+1))){
				  	pointArray p;
					for (int k=0;k<=i;k++) p.attachPoint(point(k));
					for (int k=j+1;k<size();k++) p.attachPoint(point(k));
					l<<p.seperate();
					p.clear();
					for (int k=i+1;k<=j;k++) p.attachPoint(point(k));
					p.attachPoint(point(i+1));
					l<<p.seperate();
					//printf("split %d\n",l.size());
					//for (int k=0;k<l.size();k++) printf("%d\n",l[k].size());
					return l;
					}
			  else if (element::onLine2(point(j),point(j+1),point(i))){
				    pointArray p;
					for (int k=0;k<=i;k++) p.attachPoint(point(k));
					for (int k=j+1;k<size();k++) p.attachPoint(point(k));
					l<<p.seperate();
					p.clear();
					for (int k=i+1;k<=j;k++) p.attachPoint(point(k));
					p.attachPoint(point(i+1));
					l<<p.seperate();
					//printf("split %d\n",l.size());
					//for (int k=0;k<l.size();k++) printf("%d\n",l[k].size());
					return l;
					}
				//else {doit=false;}
			}
		}
}
pointArray p=(*this);
p.cleanUnneeded();
l<<p;
return l;	
}

pointArray pointArray::cutPoints(QPoint p1,QPoint p2){
pointArray cutpoint;
bool b;
QPoint pos;
for (int i=0; i<size()-1;i++){
	b=element::cutPoint(p1,p2,point(i),point(i+1),&pos);
	if (b){// printf("b %i\n",i);
			cutpoint.attachPoint(pos);
		}
	if (element::parallel(p1,p2,point(i),point(i+1))){
			if ((!element::onLine2(p1,p2,point(i)))&&(element::onLine2(p1,p2,point(i+1)))){
				cutpoint.attachPoint(point(i));
				}	
			}
		}
//printf("---\n");
return cutpoint;
}

bool pointArray::identical(const pointArray &pa){
/*for (int i=0; i<size();i++)
		printf(" %d ; %d\n",point(i).x()  , point(i).y());
printf("\n");
for (int i=0; i<size();i++)
		printf(" %d ; %d\n",pa.point(i).x()  , pa.point(i).y());
printf("\n");*/
if (size()!=pa.size()) return false;
for (int i=0;i<size();i++){
	int p1=0;
	int p2=i;
	while ((point(p1)==pa.point(p2))&&(p1<(pa.size()-1))){
		p1++;
		p2++;
		if (p2>=pa.size()) p2=1;
		if (p1>=size()) p1=1;
		}
	if ((p1==(size()-1))) return true;
	}
return false;
}

void pointArray::modifyCorners(double value1,double value2){
	if (size()<3) return;
	QList<double> angles;
	for (int i=0;i<size()-2;i++){
		double angle=element::angle(point(i),point(i+1),point(i+2));
		angles<<angle;
		//double deplace=1.0*value1*sqrt(angle/90)/sqrt(2*value2+tan(angle/2/180*M_PI));
		//printf("%f\n",angle);
	}
	double angle=element::angle(point(size()-2),point(0),point(1));
	angles<<angle;
	//printf("%f\n",angle);
	QPoint pNull;
	QPoint pLast;
	for (int i=size()-1;i>0;i--){
		angle=angles[i-1];
		double angleAbs=angle;
		if (angle<0)angleAbs= -angle;
		double wurzel=2*value2+tan(angleAbs/2/180*M_PI);
		if (wurzel<0)wurzel=0;
		double deplace=1.0*value1*sqrt(angleAbs/90)/sqrt(wurzel);
		//printf("deplace: %f %f %f %f\n",deplace,wurzel,angleAbs,sqrt(wurzel));
		if ((deplace*angle*value1) <0) deplace = -deplace;
		double length=deplace*value2;
		if (length<0) length= -length;
		double lengthafter=length;
		double lengthbefore=length;
		QPoint plus;
		if (i!=size()-1) plus=pLast;
		else plus=point(1);
		double l2=element::distance(plus,point(i));
		double l1=element::distance(point(i-1),point(i));
		if (l2/2<lengthafter)lengthafter=l2/2;
		if (l1/2<lengthbefore)lengthbefore=l1/2;
		double difX=plus.x()-point(i).x();
		double difY=plus.y()-point(i).y();
		//printf("dif: %f %f \n",difX,difY);
		//printf("l2: %f %f %f\n",l2,tan(angle/2/180*M_PI)*deplace,tan(angle/2/180*M_PI)*deplace*difX);
		QPoint p1=QPoint(element::runden(point(i).x()+lengthafter/l2*difX), element::runden(point(i).y()+lengthafter/l2*difY));
		QPoint p2=p1+QPoint(element::runden(difY*deplace/l2), -element::runden(difX*deplace/l2));
		QPoint p3=point(i)+p2-p1- QPoint(element::runden(tan(angle/2/180*M_PI)*deplace*difX/l2), element::runden(tan(angle/2/180*M_PI)*deplace*difY/l2));
		difX=point(i-1).x()-point(i).x();
		difY=point(i-1).y()-point(i).y();
		QPoint p5=QPoint(element::runden(point(i).x()+lengthbefore/l1*difX), element::runden(point(i).y()+lengthbefore/l1*difY));
		QPoint p4=p5-QPoint(element::runden(deplace/l1*difY), -element::runden(deplace/l1*difX));
		/*printf("%f %f\n",angle,deplace);
		printf("x: %d->%d y:%d->%d\n",point(i).x(),p3.x(),point(i).y(),p3.y());
		printf("p1: %d / %d\n",p1.x(),p1.y());
		printf("p2: %d / %d\n",p2.x(),p2.y());
		printf("p4: %d / %d\n",p4.x(),p4.y());
		printf("p5: %d / %d\n",p5.x(),p5.y());*/
		pLast=point(i);
		setPoint(i,p3);
		if (i!=size()-1) {
			insert(i+1,p1);
			insert(i+1,p2);
		}
		else {
			pNull=p1;
			*this<<p2;
			*this<<p1;
		}
		insert(i,p4);
		insert(i,p5);
	}
	setPoint (0,pNull);
	//double area=deplace*2*length+deplace*tan(angle/2/180*M_PI)*deplace
	//value1*sqrt(angle/90)=deplace*sqrt(2*value2+tan(angle/2/180*M_PI));
	//double deplace=1.0*value1*sqrt(angle/90)/sqrt(2*value2+tan(angle/2/180*M_PI));
	
}

pointArray pointArray::operator* ( double d ) const{
  pointArray pa;
  for (int i=0;i<size();i++){
    pa<<(at(i)*d);
  }
  return pa;
}


void pointArray::lineDistance(QPoint p1,QPoint p2, int *left,int *right){
}

QList<pointArray> pointArray::triangulate(){
}

bool triangulation::insideTriangle(QPoint p1, QPoint p2,QPoint p3,QPoint p4) 
{
  long long ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
  long long cCROSSap, bCROSScp, aCROSSbp;

  ax = p3.x() - p2.x();  ay = p3.y() - p2.y();
  bx = p1.x() - p3.x();  by = p1.y() - p3.y();
  cx = p2.x() - p1.x();  cy = p2.y() - p1.y();
  apx= p4.x() - p1.x();  apy= p4.y() - p1.y();
  bpx= p4.x() - p2.x();  bpy= p4.y() - p2.y();
  cpx= p4.x() - p3.x();  cpy= p4.y() - p3.y();

  aCROSSbp = ax*bpy - ay*bpx;
  cCROSSap = cx*apy - cy*apx;
  bCROSScp = bx*cpy - by*cpx;
  //printf("%f %f %f\n",(float)(aCROSSbp),(float)(cCROSSap),(float)(bCROSScp));
  return ((aCROSSbp < 0) && (bCROSScp < 0) && (cCROSSap < 0));
};

bool triangulation::insideOrOnTriangle(QPoint p1, QPoint p2,QPoint p3,QPoint p4) 
{
  long long ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
  long long cCROSSap, bCROSScp, aCROSSbp;

  ax = p3.x() - p2.x();  ay = p3.y() - p2.y();
  bx = p1.x() - p3.x();  by = p1.y() - p3.y();
  cx = p2.x() - p1.x();  cy = p2.y() - p1.y();
  apx= p4.x() - p1.x();  apy= p4.y() - p1.y();
  bpx= p4.x() - p2.x();  bpy= p4.y() - p2.y();
  cpx= p4.x() - p3.x();  cpy= p4.y() - p3.y();

  aCROSSbp = ax*bpy - ay*bpx;
  cCROSSap = cx*apy - cy*apx;
  bCROSScp = bx*cpy - by*cpx;
  //printf("---> %f %f %f\n",(float)(aCROSSbp),(float)(cCROSSap),(float)(bCROSScp));
  return ((aCROSSbp <= 0) && (bCROSScp <= 0) && (cCROSSap <= 0));
};

bool triangulation::snip(pointArray contour,int u,int v,int w,int n,int *V)
{
  int p;
  long long Ax, Ay, Bx, By, Cx, Cy;
  //printf("test %d %d %d (%d %d %d)\n",u,v,w,V[v],contour.point(V[v]).x(),contour.point(V[v]).y());
  Ax = contour.point(V[u]).x();
  Ay = contour.point(V[u]).y();

  Bx = contour.point(V[v]).x();
  By = contour.point(V[v]).y();

  Cx = contour.point(V[w]).x();
  Cy = contour.point(V[w]).y();
  //printf("%d %d %d\n",(int)((Bx-Ax)*(By+Ay)),(int) ((Ay+Cy)*(Ax-Cx)),(int)((Cy+By)*(Cx-Bx)));
  if ( (long long)(0) > (((Bx-Ax)*(By+Ay)) + ((Ay+Cy)*(Ax-Cx))+((Cy+By)*(Cx-Bx))) ) return false;

  for (p=0;p<n;p++)
  {
    if( (p == u) || (p == v) || (p == w) ) continue;
//printf("check(%d) %d %d\n",V[p],contour.point(V[p]).x(),contour.point(V[p]).y());
    if ((p==u-1)||(w+1==p)||(p==0 && w==n-1)||(p==n-1 && u==0)){
	if (insideOrOnTriangle(contour.point(V[u]), contour.point(V[v]),contour.point(V[w]),contour.point(V[p]))) {
	//printf("---> inside\n");
	 return false;
	}
	}
    else if (insideTriangle(contour.point(V[u]), contour.point(V[v]),contour.point(V[w]),contour.point(V[p]))) {
	//printf("inside\n");
	 return false;
	}
  }
//printf("found %f\n",(float)(((Bx-Ax)*(By+Ay)) + ((Ay+Cy)*(Ax-Cx))+((Cy+By)*(Cx-Bx)))/2);
  return true;
}

bool triangulation::process(pointArray contour, QList<pointArray> *result)
{
  /* allocate and initialize list of Vertices in polygon */

  int n = contour.size()-1;
  if ( n < 3 ) return false;

  int *V = new int[n];

  /* we want a counter-clockwise polygon in V */

  if ( false )
    for (int v=0; v<n; v++) V[v] = v;
  else
    for(int v=0; v<n; v++) V[v] = (n-1)-v;

  int nv = n;

  /*  remove nv-2 Vertices, creating 1 triangle every time */
  int count = 2*nv;   /* error detection */
//printf("%d \n",nv);
  for(int m=0, v=nv-1; nv>2; )
  {
    /* if we loop, it is probably a non-simple polygon */
    if (0 >= (count--))
    {
      //** Triangulate: ERROR - probable bad polygon!
//printf("error %d %d ->%d\n",n,contour.size()-1,result->size());
      return false;
    }

    /* three consecutive vertices in current polygon, <u,v,w> */
    int u = v  ; if (nv <= u) u = 0;     /* previous */
    v = u+1; if (nv <= v) v = 0;     /* new v    */
    int w = v+1; if (nv <= w) w = 0;     /* next     */

    if ( snip(contour,u,v,w,nv,V) )
    {
      int a,b,c;

      /* true names of the vertices */
      a = V[u]; b = V[v]; c = V[w];

      /* output Triangle */
      pointArray pa;
      pa<<contour.point(a);
      pa<<contour.point(b);
      pa<<contour.point(c);
      *result<<pa;

      m++;

      /* remove v from remaining polygon */
      for(int s=v;s<nv;s++) V[s] = V[s+1]; 
	nv--;
	//printf("nv %d\n",nv);
      /* resest error detection counter */
      count = 2*nv;
    }
  }

 //printf("%d %d ->%d\n",n,contour.size()-1,result->size());
  delete V;

  return true;
}


