Polygon.cpp

Go to the documentation of this file.

#include <Polygon.h>

Polygon::Polygon() {x.resize(0);}
Polygon::Polygon(const Polygon& poly) {x=poly.x;}
Polygon::~Polygon() {destroy();}


Polygon::Polygon(const V_3D& x0,const V_3D& x1,const V_3D& x2)
{destroy();x.push_back(x0);x.push_back(x1);x.push_back(x2);}
Polygon::Polygon(const V_3D& x0,const V_3D& x1,const V_3D& x2,const V_3D& x3)
{destroy();x.push_back(x0);x.push_back(x1);x.push_back(x2);x.push_back(x3);}
Polygon::Polygon(const std::vector <V_3D>& v)
{set_polygon(v);}

int Polygon::destroy() {x.resize(0);return 0;}
int Polygon::size() const {return x.size();}


V_3D Polygon::operator()(int index) const
{
  if(index<0 || index>size()){printf("Error in Polygon(%d) size of polygon=%d\n",index,size());exit(-1);}
  return x[index];
}
V_3D& Polygon::operator()(int index)
{
  if(index<0 || index>size()){printf("Error in Polygon(%d) size of polygon=%d\n",index,size());exit(-1);}
  return x[index];
}
V_3D Polygon::operator[](int index) const
{
  if(index<0 || index>size()){printf("Error in Polygon[%d] size of polygon=%d\n",index,size());exit(-1);}
  return x[index];
}
V_3D& Polygon::operator[](int index)
{
  if(index<0 || index>size()){printf("Error in Polygon[%d] size of polygon=%d\n",index,size());exit(-1);}
  return x[index];
}

int Polygon::set_polygon(const std::vector <V_3D>& v)
{
  if(v.size()<=2)
    {printf("Error in set_polygon in Polygon, size of given polygon=%d < 3\n",v.size());exit(-1);}

  //copy the vector
  x=v;

  return 0;
}
int Polygon::set_polygon(const V_3D& x0,const V_3D& x1,const V_3D& x2)
{
  destroy();
  x.push_back(x0);
  x.push_back(x1);
  x.push_back(x2);
  return 0;
}

int Polygon::add_vertex(const V_3D& v)
{x.push_back(v);return 0;}
int Polygon::add_vertex(double x0,double x1,double x2)
{V_3D temp(x0,x1,x2);x.push_back(temp);return 0;}
int Polygon::add_vertex(const std::vector <V_3D>& v)
{
  for(unsigned int k=0;k<v.size();k++)
    x.push_back(v[k]);
  return 0;
}

std::vector <Polygon> Polygon::triangulate() const
{
  int N_triangle=size()-2;
  std::vector <Polygon> vector_triangle(N_triangle);

  if(N_triangle<=0)
    {printf("Error in triangulate in Polygon, size of current polygon (%d) is not enough\n",size());exit(-1);}

  for(int k_tri=0;k_tri<N_triangle;k_tri++)
    {
      vector_triangle[k_tri].add_vertex(x[0]);
      vector_triangle[k_tri].add_vertex(x[k_tri+1]);
      vector_triangle[k_tri].add_vertex(x[k_tri+2]);
    }
  return vector_triangle;
}
std::vector <Triangle> Polygon::get_triangulation() const
{
  std::vector <Polygon> polygon_set=triangulate();

  // convert polygon to triangles
  std::vector <Triangle> triangle_set;
  for(unsigned int k=0;k<polygon_set.size();k++)
    triangle_set.push_back(polygon_set[k].to_triangle());
  return triangle_set;
}

ostream& operator<<(ostream& stream,const Polygon& poly)
{
  int N_vertex=poly.size();
  for(int k_vertex=0;k_vertex<N_vertex;k_vertex++)
    stream<<poly[k_vertex]<<endl;
  return stream;
}

Polygon& Polygon::operator=(const Polygon& poly)
{
  x = poly.x;
  return *this;
}

V_3D Polygon::normal() const
{
  if(size()<=2){printf("Error in normal() in Polygon, Polygon size is not ok [%d]\n",size());exit(-1);}
  V_3D n = ((x[1]-x[0]).vector_prod(x[2]-x[0])).normalized();
  return n;
}


Triangle Polygon::to_triangle() const
{
  if(size()!=3){printf("Error in to_triangle, in Polygon, size is != 3 (%d)\n",size());exit(-1);}
  Triangle t(x[0],x[1],x[2]);
  return t;
}


double Polygon::shortest_distance_to_point(const V_3D& _x) const
{V_3D y=closest_point(_x);return (y-_x).norm();}

V_3D Polygon::closest_point(const V_3D& _x) const
{int type=0;return closest_point(_x,&type);}

V_3D Polygon::closest_point(const V_3D& _x,int *type) const
{
  if(size()<=2){printf("Error in closest_polygon_point in Polygon, Polygon size is not ok [%d]\n",size());exit(-1);}

  double epsilon=0.00001;
  V_3D n = normal();

  // get the projection on the plane
  V_3D projection;
  projection = _x-((_x-x[0]).dot(n))*n;
  
  std::vector <Triangle> triangles=get_triangulation();
  
  // first, try to find if the projection is inside the polygon (in one of the triangle)
  for(unsigned int k=0;k<triangles.size();k++)
    {
      if(triangles[k].is_vertex_inside(projection)==1)
        {
          *type=0;
          return projection;
        }
    }
  
  // then, the projection is outside the polygon
  // find the closest edge
  V_3D x0,x1,closest;Segment s;double L=0.0,L_min=9999.9;
  int closest_edge=-1;
  for(int k=0;k<size();k++)
    {
      x0 = x[k];
      x1 = x[(k+1)%size()];
      s.set(x0,x1);
      
      L = s.distance_to_point(projection);
      if(L<L_min)
        {
          closest = s.closest_point(projection);
          closest_edge = k;
          L_min=L;
        }
    }


  *type = 1;
  //look if the closest point is inside an edge, or a vertex
  for(int k=0;k<size();k++)
    if( (closest-x[k]).norm() < epsilon) //then it is close to a vertex
      *type=2;
  return closest;
}

Segment Polygon::get_segment(int index) const
{
  if(index<0 || index>=size())
    {printf("Error in get_segment(%d) in Polygon, size=%d\n",index,size());exit(-1);}

  Segment s(x[index],x[(index+1)%size()]);
  return s;
}



std::vector <V_3D> Polygon::plane_intersection(const V_3D& n,const V_3D& x0,int *type) const
{std::vector <int> type_edge;return plane_intersection(n,x0,type,&type_edge);}

std::vector <V_3D> Polygon::plane_intersection(const V_3D& n,const V_3D& x0,int *type,std::vector <int> *type_edge) const
{

  std::vector <V_3D> intersections;

  // First, take every intersection with every segment

  std::vector <Segment> s;
  std::vector <V_3D> inter;
  type_edge->resize(size());
  for(int k=0;k<size();k++)
    {
      s.push_back(get_segment(k));
      inter.push_back(s[k].plane_intersection(n,x0,&((*type_edge)[k])));
    }

  
  // look if there is no intersection that all
  int is_intersection=0;
  for(int k=0;is_intersection==0 && k<size();k++)
    if((*type_edge)[k]!=0)
      is_intersection=1;
  if(is_intersection==0)//no intersection
    {*type=0;return intersections;}

  // look if there is a parralel edge
  for(int k=0;k<size();k++)
    if((*type_edge)[k]==3)
      {*type=3;intersections.push_back(s[k][0]);intersections.push_back(s[k][1]);return intersections;}

  // look if there is only one vertex in common
  int is_two_intersection=0;
  int k_vertex=-1;
  for(int k=0;is_two_intersection==0 && k<size();k++)
    {
      if( (*type_edge)[k]==1) is_two_intersection=1;
      if( (*type_edge)[k]==2) k_vertex=k;
    }
  if(is_two_intersection==0)
    {
      if(k_vertex==-1)
        {printf("Error in Polygon in plane_intersection, types are not corrects\n");exit(-1);}
      *type=2; intersections.push_back(x[k_vertex]); return intersections;
    }
  

  // there is two intersections
  int k_1=0,k_2=0;
  for(k_1=0;k_1<size();k_1++)
    for(k_2=k_1+1;k_2<size();k_2++)
      if( ((*type_edge)[k_1]==1||(*type_edge)[k_1]==2) && ((*type_edge)[k_2]==1||(*type_edge)[k_2]==2) )
        {*type=1;intersections.push_back(inter[k_1]);intersections.push_back(inter[k_2]);return intersections;}


  //else probleme
  cout<<"Error in plane_intersection("<<n<<","<<x0<<") ";
  printf("in Polygon, types are not correct: (");
  for(int k=0;k<size()-1;k++)
    printf("%d,",(*type_edge)[k]);
  printf("%d)\n",(*type_edge)[size()-1]);
  exit(-1);
}

Polygon Polygon::half_space_intersection(const V_3D& n,const V_3D& x0,int *type)
{
  //first take the intersection of the polygon and the plane
  std::vector <V_3D> intersection;
  int type_edges;
  
  intersection = plane_intersection(n,x0,&type_edges);

  //check if we need to cut or not the polygon
  Polygon new_polygon;
  if(type_edges!=1) // no change or just destroy the polygon
    {
      if(((*this)[0]-x0).dot(n)<0)//check the orientation of the polygon to the plane
        {
          //negativ so there is no more polygons
          *type=2;
          new_polygon.add_vertex(V_3D(-1.0,-1.0,-1.0));
          return new_polygon;
        }
      else
        {
          // the polygon is unchanged
          *type=0;
          return *this;
        }
    }

  //else there is a modification to bring to the polygon

  *type=1;
  Segment s(intersection[0],intersection[1]);
  V_3D old_normal=normal();

  //first add every points in the correct half space
  //(just to be sure that we know the vertex before the line)

  //find the first vertex in half space
  int k=0;
  while(((*this)[k]-x0).dot(n)<0)
    k++;
  int k_2=k;

  int added_line=0;
  do
    {
      if( ((*this)[k_2]-x0).dot(n)>0 )
        new_polygon.add_vertex((*this)[k_2]);
      else if(added_line==0)
        {
          // check if the line is in the right sense (we are sure that (*this[k2-1] already exists))
          if( ((s[1]-s[0]).vector_prod(s[0]-(*this)[(k_2-1)<0?size()-1:k_2-1])).dot(old_normal)<0)
            {new_polygon.add_vertex(s[0]);new_polygon.add_vertex(s[1]);}     
          else{new_polygon.add_vertex(s[1]);new_polygon.add_vertex(s[0]);}
          added_line=1;
        }
      k_2=(k_2+1)%size();
    }while(k_2!=k);
  
  return new_polygon;
  
}

std::vector <Polygon> Polygon::subdivide_mid_edge() const
{
  // the new midpoints
  std::vector <V_3D> mid_points;
  // as much mid point as there is vertices in the polygon
  mid_points.resize(size());

  int k=0,N_mid_points=size();
  for(k=0;k<N_mid_points;k++)
    mid_points[k]=0.5*(x[k]+x[(k+1)%N_mid_points]);

  // the new polygons
  std::vector <Polygon> new_polygon;
  // size of new_polygon = (old)N_vertex + 1
  new_polygon.resize(N_mid_points+1);

  // all triangles excepted the last on linking the mid_points
  for(k=0;k<N_mid_points;k++)
    {
      new_polygon[k].add_vertex(x[k]);
      new_polygon[k].add_vertex(mid_points[k]);
      new_polygon[k].add_vertex(mid_points[k-1>=0?k-1:N_mid_points-1]);
    }
  //last one linking every mid_points
  for(k=0;k<N_mid_points;k++)
    new_polygon[N_mid_points].add_vertex(mid_points[k]);

  
  return new_polygon;
}


std::vector <Polygon> Polygon::subdivide_barycenter_mid_edge() const
{

  V_3D barycenter;

  // the new midpoints
  std::vector <V_3D> mid_points;

  // as much mid point as there is vertices in the polygon
  mid_points.resize(size());

  int k=0,N_mid_points=size();
  for(k=0;k<N_mid_points;k++)
    {
      mid_points[k]=0.5*(x[k]+x[(k+1)%N_mid_points]);
      barycenter+=x[k];
    }
  barycenter/=double(N_mid_points);

  std::vector <Polygon> new_polygon(N_mid_points);
  
    for(k=0;k<N_mid_points;k++)
    {
      new_polygon[k].add_vertex(x[k]);
      new_polygon[k].add_vertex(mid_points[k]);
      new_polygon[k].add_vertex(barycenter);
      new_polygon[k].add_vertex(mid_points[k-1>=0?k-1:N_mid_points-1]);
    }

    return new_polygon;
}

// V_3D Polygon::closest_segment_point(const Segment& s) const;
// {

//   V_3D n=normal();

//   // calculate the signed distance of the two extremities
//   double sign_d0=0.0;
//   double sign_d1=0.0;

//   double sign_0=0.0,sign_1=0.0;
//   if(s[0].dot(n)<0) sign_0=-1;
//   if(s[1].dot(n)<0) sign_1=-1;

//   sign_d0 = shortest_distance_to_point(s[0]) * sign_0;
//   sign_d1 = shortest_distance_to_point(s[1]) * sign_1;

  
  

// }