include glut include iostream include cmath include locale include con

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include "glut.h"
#include <iostream>
#include <cmath>
#include <locale.h>
#include <conio.h>
#include <vector>
#include <time.h>
using namespace std;
int *x;
int *y;
vector <int> parts;
int n;
int point(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
{
parts.push_back(q);
next = q;
for (int i = n - 1; i >= 0; -- i)
if (x[i] != x[q] || y[i] != y[q]) {
sign = 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]);
if (next == q || sign > 0 || (sign == 0 && point(next, q, i)))
next = i;
}
q = next;
}
while(q!=first);
int d;
cout << endl << "Точки выпуклой оболочки:" << endl;
for (vector<int>::iterator it = parts.begin() ; it!=parts.end() ; ++it){
d=*it;
cout<<x[d]<<" "<<y[d];
cout<<endl;
}
cout << endl << "Количество точек выпуклой оболочки: " << parts.size() << endl << endl;
}
void show(){
glClear(GL_COLOR_BUFFER_BIT);
glBegin(GL_LINE_LOOP);
for (vector<int>::iterator it = parts.begin() ; it!= parts.end(); it++)
{
glColor3f(1, 0, 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 << "Алгоритм Джарвиса:" << endl;
cout << "Количество точек на плоскости: ";
cin >> n;
x = new int [n];
y = new int [n];
srand(time(NULL));
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(700, 500);
glutCreateWindow("Jarvis");
glClearColor(0,0,0,0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0, 600, 400, 0, -1, 1);
glutDisplayFunc(show);
glutMainLoop();
delete x;
delete y;
_getch();
return 0;
}