Ndtyjky

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]; 

      } 

    } 

  }

}