include stdafx include list using namespace std int s_height 600 s_wid

#include "stdafx.h"
#include <list>

using namespace std;

int s_height = 600, s_width = 800;
int F=0;

struct ver{
	int x, y,f;
	ver *b, *e;
};

struct vertex{
	ver m[2];
	int n;
};

list<ver> A,B;
list<list<ver>> R;


static void cursor_callback(GLFWwindow* window, double x, double y){

}

int index = 0;

static void mouse_callback(GLFWwindow* window, int button, int action, int mods){
	if (button == GLFW_MOUSE_BUTTON_RIGHT && action == GLFW_PRESS){

	}
	if (button == GLFW_MOUSE_BUTTON_LEFT && action == GLFW_PRESS){
		double x, y;
		ver t;
		glfwGetCursorPos(window, &x, &y);
		t.x = (int)x;
		t.y = (int)(s_height - y);
		t.b = NULL;
		t.e = NULL;
		if (!F){
			t.f = index;
			index++;
			A.push_back(t);
		}
		else {
			t.f = -1;
			B.push_back(t);
		}
	}
}

void test(ver t, ver w, ver v, int *ft){
	if ((w.x - t.x)*(v.y - t.y) - (v.x - t.x)*(w.y - t.y) < 0)
		*ft = 1;
}

int Det(int a11, int a12, int a21, int a22){
	return a11*a22-a12*a21;
}

void Saz_Hod(){
	list<ver> K;
	for (list<ver>::iterator v = B.begin(); v != B.end(); v++){
		list<ver>::iterator w = v;
		v++;
		if (v == B.end())
			v = B.begin();
		for (list<ver>::iterator y = A.begin(); y != A.end(); y++){
			list<ver>::iterator u = y;
			y++;
			if (y == A.end())
				y = A.begin();
			int fu = 0, fy = 0;
			test(*y,*w,*v, &fy);
			test(*u,*w,*v, &fu);
			if (!fu && !fy){
				y = u;
				continue;
			}
			if (fu && fy){
				K.push_back(*y);
				y = u;
				continue;
			}
			ver I;
			int x1 = (*u).x, y1 = (*u).y, x2 = (*y).x, y2 = (*y).y, x3 = (*v).x, y3 = (*v).y, x4 = (*w).x, y4 = (*w).y;
			int d = Det(y2-y1,x1-x2,y4-y3,x3-x4),k1=x1*y2-x2*y1,k2=x3*y4-x4*y3; 
			I.x = int(float(Det(k1, x1 - x2, k2, x3 - x4)) / float(d));
			I.y = int(float(Det(y2 - y1, k1, y4 - y3, k2)) / float(d));
			I.f = 0;
			I.b = &(*w);
			I.e = &(*v);
			if (fu && !fy){
				K.push_back(I);
				y = u;
				continue;
			}
			if (!fu && fy){
				K.push_back(I);
				K.push_back(*y);
			}
			y = u;
		}
		R.push_back(K);
		K.erase(K.begin(), K.end());
		v = w;
	}
}

int do_it = 1;

void to_vertexs();

static void keyboard_callback(GLFWwindow* window, int key, int scancode, int action, int mods){
	if (key == GLFW_KEY_ESCAPE && action == GLFW_PRESS)
		glfwSetWindowShouldClose(window, GL_TRUE);
	if (key == GLFW_KEY_ENTER && action == GLFW_PRESS){
		F++;
		if (F == 3 && do_it){
			Saz_Hod();
			to_vertexs();
			do_it = 0;
		}
	}
	if (key == GLFW_KEY_SPACE && action == GLFW_PRESS)
		if (F == 3)
			F = 2;
		else
			F=3;
}

static void resize_callback(GLFWwindow* window, int width, int height){
	glViewport(0, 0, width, height);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	glOrtho(-(GLdouble)0, (GLdouble)width, -(GLdouble)0, (GLdouble)height, -(GLdouble)1, (GLdouble)1);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
	s_width = width;
	s_height = height;
}

void draw(GLFWwindow* window,list<ver> D,int g){
	double x, y;
	if (g==0)
		glColor3f(1, 0, 1);
	else 
		glColor3f(1, 0, 0);
	glLineWidth(1);
	glBegin(GL_LINE_LOOP);
	for (list<ver>::iterator v = D.begin(); v != D.end(); v++)
		glVertex2i((*v).x, (*v).y);
	if (F==g){
		glfwGetCursorPos(window, &x, &y);
		glVertex2i((int)x, int(s_height - y));
	}
	glEnd();
}

int test_in(int x1, int y1, int x2, int y2, int x0, int y0){
	return (x2 - x0)*(x1 - x0) <= 0 && (y2 - y0)*(y1 - y0) <= 0;
}

list<vertex> W;

int dist(ver a, ver b){
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}

void bsort(ver *b, int n){
	for (int t = n - 1; t>0;){
		int bound = t;
		t = 0;
		for (int i=0;i<bound;i++)
			if (b[i + 1].f < b[i].f){
				ver c = b[i];
				b[i] = b[i + 1];
				b[i + 1] = c;
				t = i;
			}
	}
}

void to_vertexs(){
	list<vertex> V;
	for (list<list<ver>>::iterator L = R.begin(); L != R.end(); L++){
		list<ver> T;
		for (list<ver>::iterator y = (*L).begin(); y != (*L).end(); y++){
			list<ver>::iterator u = y;
			y++;
			if (y == (*L).end())
				y = (*L).begin();
			ver a = *u;
			ver b = *y;
			y = u;
			if (!a.b || !b.b){
				vertex x;
				x.m[0] = a;
				x.m[1] = b;
				if (!a.b)
					x.n = a.f;
				else
					x.n = b.f+1;
				if (x.n == -1)
					x.n = index - 1;
				if (!a.b && !b.b)
					x.n = -1;
				V.push_back(x);
			}
			if (!a.b)
				continue;
			int x1 = a.b->x, y1 = a.b->y, x2 = a.e->x, y2 = a.e->y, x3 = a.x, y3 = a.y;
			if (test_in(x1, y1, x2, y2, x3, y3)){
				T.push_back(a);
				continue;
			}
			int m1 = dist(a,*a.b);
			int m2 = dist(a,*a.e);
			ver g;
			if (m1 < m2)
				g=*a.b;
			else
				g=*a.e;
			g.b = a.b;
			g.e = a.e;
			T.push_back(g);
		}
		if (!T.size())
			continue;
		int n = T.size();
		ver *Z = new ver[n];
		int j = 0;
		for (list<ver>::iterator v = T.begin(); v != T.end(); v++){
			ver a = *v;
			a.f = dist(a, *a.e);
			Z[j] = a;
			j++;
		}
		bsort(Z, n);
		for (int i = 0; i < n - 1; i++){
			if (!(i % 2)){
				vertex x;
				x.m[0] = Z[i];
				x.m[1] = Z[i+1];
				x.n = -1;
				V.push_back(x);
			}
		}
		delete[] Z;
	}
	W = V;
}


void draw_W(){
	glColor3f(1, 0, 1);
	for (list<vertex>::iterator v = W.begin(); v != W.end(); v++){
		vertex u = *v;
		glBegin(GL_LINE_STRIP);
		glVertex2d(u.m[0].x, u.m[0].y);
		glVertex2d(u.m[1].x, u.m[1].y);
		glEnd();
	}
}

int main(int argc, _TCHAR* argv[]){
	if (!glfwInit()){
		printf("glfwInit failed\n");
		return -1;
	}
	GLFWwindow* window;
	window = glfwCreateWindow(s_width, s_height, "Test app", NULL, NULL);
	if (window == NULL){
		printf("glfwOpenWindow failed. Can your hardware handle OpenGL 3.2?\n");
		glfwTerminate();
		return -2;
	}
	glfwMakeContextCurrent(window);
	glfwSetKeyCallback(window, keyboard_callback);
	glfwSetFramebufferSizeCallback(window, resize_callback);
	glfwSetMouseButtonCallback(window, mouse_callback);
	glfwSetCursorPosCallback(window, cursor_callback);
	resize_callback(window, s_width, s_height);
	while (!glfwWindowShouldClose(window)){
		glClear(GL_COLOR_BUFFER_BIT);
		if (F>=0 && F<=2)
			draw(window, A,0);
		if (F>=1 && F<=2)
			draw(window, B,1);
		if (F > 2)
			draw_W();
		glfwSwapBuffers(window);
		glfwWaitEvents();
	}
	glfwDestroyWindow(window);
	glfwTerminate();
	return 0;
}