#include "stdafx.h"
#include <glut.h>
#include <iostream>
#include <cmath>
#include <locale.h>
#include <conio.h>
#include <vector>
using namespace std;
int *x;
int *y;
vector <int> dots;
int n;
double area_triangle (int q, int i, int next)
{
return 0.5 * (x[next] * y[q] + x[q] * y[i] + x[i] * y[next] - y[next] * x[q] - y[q] * x[i] - y[i] * x[next]);
}
int point_in_box (int next,int q,int i)
{
int a = sqrt((x[i]-x[q])*(x[i]-x[q])+(y[i]-y[q])*(y[i]-y[q]));
int b = sqrt((x[i]-x[next])*(x[i]-x[next])+(y[i]-y[next])*(y[i]-y[next]));
if(b<a) return 1;
else return 0;
}
void jarvis ()
{
int first,q,next;
double sign;
// находим самую нижнюю из самых левых точек
first = 0;
for(int i = 1; i < n-1; i++)
{
if (x[i] < x[first] || (x[i] == x[first] && y[i] < y[first]))
first = i;
}
q = first; // текущая точка
// добавляем точки в оболочку
do
{
dots. push_back(q);
next = q;
for (int i = n - 1; i >= 0; -- i)
if (x[i] != x[q] || y[i] != y[q])
{
sign = area_triangle (q, i, next);
if (next == q || sign > 0 || (sign == 0 && point_in_box (next, q, i)))
next = i;
}
q = next;
}
while(q!=first);
int d;
cout<<endl;
for (vector<int>::iterator it = dots.begin() ; it!=dots.end() ; ++it)
{
d=*it;
cout<<x[d]<<" "<<y[d];
cout<<endl;
}
}
void display()
{
glClear(GL_COLOR_BUFFER_BIT);
glBegin(GL_LINE_LOOP);
for (vector<int>::iterator it = dots.begin() ; it!= dots.end(); it++)
{
glColor3f(0, 1, 0);
glVertex2f(x[*it], y[*it]);
}
glEnd();
glColor3f(1, 1, 1);
for (int i = 0; i < n; i++)
{
glBegin(GL_TRIANGLE_FAN);
glVertex2f(x[i], y[i]);
float r = 5;
for (float phi = 0; phi <= 6.30; phi += 0.1)
{
float x0 = r * cos(phi);
float y0 = r * sin(phi);
glVertex2f(x0 + x[i], y0 + y[i]);
}
glEnd();
}
glutSwapBuffers();
}
int main(int argc, char **argv)
{
setlocale(LC_ALL,"Rus");
cout<<"Ведите количество точек на плоскости:";
cin>>n;
x = new int [n];
y = new int [n];
for(int i = 0; i < n; i++)
{
x[i]=rand()%550+30;
y[i]=rand()%350+30;
}
for(int i = 0; i < n; i++)
{
cout<<x[i]<<" ";
cout<<y[i]<<endl;
}
jarvis();
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
glutInitWindowSize(600, 400);
glutCreateWindow("Jarvis");
glClearColor(0,0,0, 0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0, 600, 400, 0, -1, 1);
glutDisplayFunc(display);
glutMainLoop();
delete x;
delete y;
_getch();
return 0;
}