#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;
}