Pfthb

I tried implementing the Cyrus Beck algorithm for convex polygons. The problem that I was encountering was to find the direction of normal vectors as they must always point inside. For solving this I found the coordinates of the centroid, which always lie inside a convex polygon. This method seems to work in the cases I tested. Is this fool proof ? Are there any better alternatives ?

CyrusBeck.cpp

#include<iostream>
#include<cmath>
#include"graphics.hpp"

#define P pair<double, double>

vector<P> V, N;
P C;

double dot(P A, P B)
 return (A.first*B.first + A.second*B.second);


P operator - (const P &A, const P &B)
 return make_pair(A.first-B.first, A.second-B.second);


P operator + (const P &A, const P &B)
 return make_pair(A.first+B.first, A.second+B.second);


P operator * (const P &A, const double t)
 return make_pair(t*A.first, t*A.second);


void computeNormal(int n = V.size())
 double m;
 P prev = V[0];
 double x=-1, y;
 for(int i=1; i<n; ++i)
 m = -(V[i].first-prev.first)/(V[i].second-prev.second);
 P d = V[i]-prev;
 int lr=1, tb=1;
 if(V[i-1].first>C.first)
 lr = -1;
 if(V[i-1].second>C.second)
 tb=-1;
 N[i-1].first = lr*abs(cos(atan(m)));
 N[i-1].second = tb*abs(sin(atan(m)));
 prev = V[i];
 
 m = -(V[0].first-prev.first)/(V[0].second-prev.second);
 int lr=1, tb=1;
 if(V[n-1].first>C.first)
 lr = -1;
 if(V[n-1].second>C.second)
 tb=-1;
 N[n-1].first = lr*abs(cos(atan(m)));
 N[n-1].second = tb*abs(sin(atan(m)));


int check(P A, P B, int n)
 P p = B - V[0];
 double d1 = dot(p, N[0]);
 P q = A - V[0];
 double d2 = dot(q, N[0]);
 if(d1<0&&d2<0)
 return 0;
 if(d1>=0&&d2>=0)
 return 1;
 return -1;


void Clip(P A, P B, double &tE, double &tL, int n = V.size())
 tE = 0; tL = 1;
 for(int i=0; i<n; ++i)
 double d = dot((B-A), N[i]);
 if(d==0)
 continue;
 double t = dot((A-V[i]), N[i])/dot((A-B), N[i]);
 if(d>0&&t>tE)
 tE = t;
 else if(d<0&&t<tL)
 tL = t;
 


void display()
 cout<<"Enter the number of verticesn";
 int n; cin>>n;
 V.resize(n);
 N.resize(n);
 cout<<"Enter the coordinates of the vertices in ordern";
 for(int i=0; i<n; ++i)
 cin>>V[i].first>>V[i].second;
 C = C + V[i];
 
 C.first/=n; C.second/=n;
 drawPolygon(V, n, white);
 glutSwapBuffers();
 cout<<"Enter the co-ordinates of the line(4)n";
 P A, B;
 cin>>A.first>>A.second>>B.first>>B.second;
 drawLine(A.first, A.second, B.first, B.second, red);
 glutSwapBuffers();
 char c = '';
 while(c!='Y'&&c!='y')
 cout<<"Clip? (Y/N)n";
 cin>>c;
 
 computeNormal();
 int chk = check(A, B, n);
 glClearColor(0, 0, 0, 1);
 glClear(GL_COLOR_BUFFER_BIT);
 drawPolygon(V, n, white);
 if(chk==-1)
 double tE, tL;
 Clip(A, B, tE, tL);
 if(tE>tL)
 chk = 0;
 else
 P E = A + (B-A)*tE;
 P L = A + (B-A)*tL;
 drawLine(E.first, E.second, L.first, L.second, blue);
 
 
 if(chk==1)
 drawLine(A.first, A.second, B.first, B.second, blue);
 glutSwapBuffers();


int main(int argc, char *argv)
 init(&argc, argv);

graphics.hpp

#ifndef GRAPHICS_H
#define GRAPHICS_H

#include<GL/glut.h>
#include<vector>
using namespace std;

extern float red[3];
extern float green[3];
extern float blue[3];
extern float white[3];

int roundoff(double x);
void init(int* argc, char** argv);
void putpixel(float x, float y, float z, float a[3]);
void drawLine(double x1, double y1, double x2, double y2, float a[3]);
void drawRectangle(double x1, double y1, double x2, double y2, float a[3]);
void drawPolygon(vector<pair<double, double>> v, int n, float a[3]);
void MatrixMultiply(vector<vector<double>> &mat1, vector<vector<double>> &mat2, vector<vector<double>> &res,
 int n, int m, int r);
void display();

#endif

graphics.cpp

#include<iostream>
#include"graphics.hpp"

float red[3] = 1.0f, 0.0f, 0.0f ;
float green[3] = 0.0f, 1.0f, 0.0f ;
float blue[3] = 0.0f, 0.0f, 1.0f ;
float white[3] = 1.0f, 1.0f, 1.0f ;

int roundoff(double x)
 if (x < 0.0)
 return (int)(x - 0.5);
 else
 return (int)(x + 0.5);


void init(int *argc, char** argv)
 glutInit(argc, argv); // Initialize GLUT
 glutInitWindowSize(800, 800); // Set the window's initial width & height
 glutInitWindowPosition(0, 0); // Position the window's initial top-left corner
 glutCreateWindow("Graphics"); // Create a window with the given title
 gluOrtho2D(0, 800, 0, 800); // specifies the projection matrix
 glClearColor(0.0f, 0.0f, 0.0f, 1.0f); // Set background color to black and opaque
 glClear(GL_COLOR_BUFFER_BIT); // Clear the color buffer (background)
 glutDisplayFunc(display); // Register display callback handler for window re-paint
 glutMainLoop(); // Enter the event-processing loop


void putpixel(float x, float y, float z, float a[3])
 glPointSize(2);
 glBegin(GL_POINTS); // HERE THE POINTS SHOULD BE CREATED
 glColor3f(a[0], a[1], a[2]);
 glVertex3f(x, y, z); // Specify points in 3d plane
 std::cout<<x<<' '<<y<<' '<<z<<'n';
 glEnd();


void drawLine(double x1, double y1, double x2, double y2, float a[3])
 glLineWidth(2.5); 
 glColor3f(a[0], a[1], a[2]);
 glBegin(GL_LINES);
 glVertex2d(x1, y1);
 glVertex2d(x2, y2);
 glEnd();


void drawRectangle(double x1, double y1, double x2, double y2, float a[3])
 glColor3f(a[0], a[1], a[2]);
 glRectd(x1, y1, x2, y2);


void drawPolygon(vector<pair<double, double>> v, int n, float a[3])
 glColor3f(a[0], a[1], a[2]);
 glBegin(GL_POLYGON);
 for(int i=0; i<n; ++i)
 glVertex2d(v[i].first, v[i].second);
 glEnd();


void MatrixMultiply(vector<vector<double>> &mat1, vector<vector<double>> &mat2, vector<vector<double>> &res,
 int n, int m, int r) 
 int x, i, j; 
 for(i = 0; i < n; i++) 
 for (j = 0; j < r; j++) 
 res[i][j] = 0; 
 for (x = 0; x < m; x++)
 res[i][j] += mat1[i][x] * mat2[x][j];