Polygon2D.cxx

Go to the documentation of this file.

#include "Polygon2D.h"

#include <iostream>
#include <math.h>

//------------------------------------------------
float FindSlope( const std::pair<float,float> &p1,
                 const std::pair<float,float> &p2 )
{
  float slope = (p2.second-p1.second)/(p2.first-p1.first);
  return slope;
}

//-------------------------------------------------------------------------
bool Clockwise(double Ax,double Ay,double Bx,double By,double Cx,double Cy)
{
  return (Cy-Ay)*(Bx-Ax) > (By-Ay)*(Cx-Ax);
}

//------------------------------------------------------------
bool SegmentOverlap(double Ax, double Ay, double Bx, double By,
                    double Cx, double Cy, double Dx, double Dy)
{

  bool overlap = ( (Clockwise(Ax,Ay,Cx,Cy,Dx,Dy) != Clockwise(Bx,By,Cx,Cy,Dx,Dy))
                   and (Clockwise(Ax,Ay,Bx,By,Cx,Cy) != Clockwise(Ax,Ay,Bx,By,Dx,Dy)) );
  return overlap;
}

//---------------------------------------------------------------------------------
std::pair<float, float> GetIntersection(double Ax, double Ay, double Bx, double By,
                                        double Cx, double Cy, double Dx, double Dy)
{

  //get equations for two lines
  // [Ax,Ay]<--->[Bx,By] : y = s1*x+c1
  // [Cx,Cy]<--->[Dx,Dy] : y = s2*x+c2
  double s1 = (By-Ay)/(Bx-Ax);
  double s2 = (Dy-Cy)/(Dx-Cx);
  double c1 = By-s1*Bx;
  double c2 = Dy-s2*Dx;

  double Xintersection = (c2-c1)/(s2-s1);
  double Yintersection = s1 * Xintersection + c1;
  std::pair<float,float> intersection;
  intersection = std::make_pair(Xintersection, Yintersection);

  return intersection;
}

//------------------------------------------------------------------
Polygon2D::Polygon2D(const Polygon2D &poly1, const Polygon2D &poly2)
{

  //figure out if the two polygons overlap at all
  if ( !(poly1.PolyOverlap(poly2)) ){
    std::vector< std::pair<float,float> > nullpoint;
    vertices = nullpoint;
    return;
  }

  //The overlap polygon is made up by:
  //1) all points of poly1 in poly2
  //2) all points of poly2 in poly1
  //3) all intersection points between segments

  //make a new set of points and add points
  //as listed above, if found.
  std::vector<std::pair<float,float> > IntersectionPoints;
  //1)
  for (unsigned int p1=0; p1 < poly1.Size(); p1++){
    if ( poly2.PointInside( poly1.Point(p1) ) ) { IntersectionPoints.push_back( poly1.Point(p1) ); }
  }
  //2)
  for (unsigned int p2=0; p2 < poly2.Size(); p2++){
    if ( poly1.PointInside( poly2.Point(p2) ) ) { IntersectionPoints.push_back( poly2.Point(p2) ); }
  }
  //3)
  //FIND SEGMENT INTERSECTIONS
  for (unsigned int i=0; i < poly1.Size(); i++){
    for (unsigned int j=0; j < poly2.Size(); j++){
      if (SegmentOverlap( poly1.Point(i).first, poly1.Point(i).second,
                          poly1.Point(i+1).first, poly1.Point(i+1).second,
                          poly2.Point(j).first, poly2.Point(j).second,
                          poly2.Point(j+1).first, poly2.Point(j+1).second) )
        //segments overlap...add intersection to list
        IntersectionPoints.push_back( GetIntersection( poly1.Point(i).first, poly1.Point(i).second,
                                                       poly1.Point(i+1).first, poly1.Point(i+1).second,
                                                       poly2.Point(j).first, poly2.Point(j).second,
                                                       poly2.Point(j+1).first, poly2.Point(j+1).second) );
    }//for all segments in poly2
  }//for all segments in poly1

  vertices = IntersectionPoints;
  return;
}

//---------------------------
float Polygon2D::Area() const
{
  //how? here:
  //http://www.mathsisfun.com/geometry/area-irregular-polygons.html
  float area = 0;
  for (unsigned int i=0; i<vertices.size(); i++){
    if ( i < (vertices.size()-1) )
      area += (((vertices.at(i)).second)+((vertices.at(i+1)).second))*(((vertices.at(i)).first)-((vertices.at(i+1)).first))*0.5;
    if ( i == (vertices.size()-1) )
      area += (((vertices.at(i)).second)+((vertices.at(0)).second))*(((vertices.at(i)).first)-((vertices.at(0)).first))*0.5;
  }
  if (area<0.0)
    area = -area;
  return area;
}

//--------------------------------
float Polygon2D::Perimeter() const
{

  float perimeter = 0.;

  for (unsigned int i=0; i<vertices.size(); i++){
    if ( i < (vertices.size()-1) )
      perimeter += ( (vertices.at(i).second-vertices.at(i+1).second)*
                     (vertices.at(i).second-vertices.at(i+1).second) +
                     (vertices.at(i).first-vertices.at(i+1).first)*
                     (vertices.at(i).first-vertices.at(i+1).first) );
    if ( i == (vertices.size()-1) )
      perimeter += ( (vertices.at(i).second-vertices.at(0).second)*
                     (vertices.at(i).second-vertices.at(0).second) +
                     (vertices.at(i).first-vertices.at(0).first)*
                     (vertices.at(i).first-vertices.at(0).first) );
  }

  return sqrt(perimeter);
}

//------------------------------------------------------------------
const std::pair<float,float>& Polygon2D::Point(unsigned int p) const
{
  //This function returns the vertex under consideration
  //as a std::pair<float,float> Returns vertex for argument
  //from 0 to N-1. For input N = number of sides then
  //the first vertex is returned
  if (p<vertices.size())
    return vertices.at(p);
  else if (p==vertices.size())
    return vertices.at(0);
  else{
    std::cout << "Out of bounds of Polygon!" <<std::endl;
    return vertices.at(0);
  }

}

//------------------------------------------------------------------------
std::pair<float,float> Polygon2D::Project(const std::pair<float,float> &p,
                                        float theta) const
{

  std::pair<float,float> range(10000,0);
  std::pair<float,float> ptmp;

  for (unsigned int i=0; i<vertices.size(); i++){
    //Translation
    //translating each vertex so that origin is on first vertex on polygon's edge being considered
    ptmp = std::make_pair(   (vertices.at(i)).first - p.first  ,   (vertices.at(i)).second - p.second   );
    //Rotation
    //instead of rotating each (x,y) edge (slow) just find nex x-position which gives us information
    //on the projection of that vertex on the line we are considering
    // +x direction is from vertex in consideration (vertex 'i' in loop) to next vertex
    //now find the x-coordinate of that vertex after it is rotated such that edge is now + x axis
    float xnew = (ptmp.first)*cos(theta) + (ptmp.second)*sin(theta);
    //finally calculate range of projection on x-axis: look at every x position and compare it to range
     if ( xnew < range.first )
      range.first = xnew;
    if ( xnew > range.second )
      range.second = xnew;
  }
  return range;
}

//---------------------------------------------------------------
bool Polygon2D::Overlap(float slope,
                      const Polygon2D &poly2,
                      const std::pair<float,float> &origin) const
{
  //translate and rotate both polygons
  float theta = tan(slope);
  //here we translate origin, rotate and find x-coordinates and find range of projection on edge line
  std::pair<float,float> range1 = this->Project(origin,theta);
  std::pair<float,float> range2 = poly2.Project(origin,theta);
  //std::cout << "range 1: " << range1.first << " " << range1.second << std::endl;
  //std::cout << "range 2: " << range2.first << " " << range2.second << std::endl;
  //if the two projections don't overlap --> no overlap!
  if ( ( ((range1.first <= range2.second) and ( range1.first >= range2.first )) or ((range1.second <= range2.second) and ( range1.second >= range2.first )) ) or ( ((range2.first <= range1.second) and ( range2.first >= range1.first )) or ((range2.second <= range1.second) and ( range2.second >= range1.first )) ) )
    return true;     //yes...they overlap
  else
    return false;    //no....they do not overlap
}

//-------------------------------------------------------
bool Polygon2D::PolyOverlap(const Polygon2D &poly2) const
{

  //start from first pair in vector then check all edges.
  //edges are (0,1), (1,2), ..., (N,N-1) each pair a pair
  //of vertexes
  for (unsigned int i=0; i<this->Size(); i++){//loop over first polygon's vertices
    //find projection line's slope
    //line: y=ax+b --- slope is a variable
    float slope;
    slope = FindSlope( this->Point(i) , this->Point(i+1) );
    //if there is even one no-overlap
    //need to exit and return no overlap!
    if (! (this->Overlap( slope, poly2, this->Point(i) )) )
      return false;
  }//loop over first polygon vertices

  //do the exact same thing but reversing polygon role
  for (unsigned int i=0; i<poly2.Size(); i++){//loop over first polygon
    float slope;
    slope = FindSlope( poly2.Point(i) , poly2.Point(i+1) );
    if (!(poly2.Overlap( slope, *this, poly2.Point(i) )) )
      return false;
  }//loop over second polygon vertices
  return true;
}

//---------------------------------------------------------------
bool Polygon2D::PolyOverlapSegments(const Polygon2D &poly2) const
{
  //if contained in one another then they also overlap:
  if ( (this->Contained(poly2)) or (poly2.Contained(*this)) ){
    return true;
  }
  //loop over the two polygons checking wehther
  //two segments ever intersect
  for (unsigned int i=0; i<this->Size(); i++){
    for (unsigned int j=0; j<poly2.Size(); j++){
      if (SegmentOverlap( this->Point(i).first, this->Point(i).second,
                          this->Point(i+1).first, this->Point(i+1).second,
                          poly2.Point(j).first, poly2.Point(j).second,
                          poly2.Point(j+1).first, poly2.Point(j+1).second) ){
        return true;
      }
    }
  }
  return false;
}

//--------------------------------------------------------------------
bool Polygon2D::PointInside(const std::pair<float,float> &point) const
{

  //any ray originating at point will cross polygon
  //even number of times if point outside
  //odd number of times if point inside
  int intersections = 0;
  for (unsigned int i=0; i<this->Size(); i++){
    if ( SegmentOverlap( this->Point(i).first, this->Point(i).second,
                         this->Point(i+1).first, this->Point(i+1).second,
                         10000.0, 10000.0,
                         point.first, point.second) )
      intersections += 1;
  }
  if ( (intersections%2) == 0 )
    return false;
  else
    return true;

}

//-----------------------------------------------------
bool Polygon2D::Contained(const Polygon2D &poly2) const
{

 //loop over poly2 checking wehther
  //points of poly2 all inside poly1
  for (unsigned int i=0; i<poly2.Size(); i++){
    if ( !(this->PointInside( poly2.Point(i)) ) )
      return false;
  }

  return true;

}

//-------------------------------
void Polygon2D::UntanglePolygon()
{

  //loop over edges
  for ( unsigned int i=0; i < vertices.size()-1; i++){
    double Ax = vertices.at(i).first;
    double Ay = vertices.at(i).second;
    double Bx = vertices.at(i+1).first;
    double By = vertices.at(i+1).second;
    //loop over edges that have not been checked yet
    for (unsigned int j=i+2; j < vertices.size()-1; j++){
      //avoid consecutive segments
      if ( vertices.at(i) == vertices.at(j+1) )
        continue;
      else{
        double Cx = vertices.at(j).first;
        double Cy = vertices.at(j).second;
        double Dx = vertices.at(j+1).first;
        double Dy = vertices.at(j+1).second;

        if ( SegmentOverlap( Ax, Ay, Bx, By, Cx, Cy, Dx, Dy ) ){
          std::pair<float, float> tmp = vertices.at(i+1);
          vertices.at(i+1) = vertices.at(j);
          vertices.at(j) = tmp;
          //swapped polygon, now do recursion to make sure
          this->UntanglePolygon();
        }//if crossing
      }
    }//second loop
  }//first loop

}