Space-efficient geometric algorithms and data structures By Ilya Katz and Hervé Brönnimann

cgl.hpp

Go to the documentation of this file.

#ifndef CGL_HPP
#define CGL_HPP

//add multi-dpoint, less_nth_object, trienble, point_in_triangle

#include <boost/array.hpp>



template <class NT, std::size_t N=2>
class cgl
{

public:

   typedef NT                                                   coord_type;
  typedef boost::array<coord_type,2>    point_type;
  typedef boost::array<point_type,2>    line_type;
  typedef boost::array<coord_type, N> multiD_point_type;
  typedef boost::array<point_type,4>    box_type;
  typedef boost::array<point_type,3> triangle_type;
    enum side {TOP, BOTTOM};
   typedef std::pair<boost::array<point_type,2>,side> halfplane_type;


   struct less_x_object_type
  {
    bool operator()(cgl::point_type p1, cgl::point_type p2){
      return p1[0]<p2[0];
    }
  };
  struct less_y_object_type
  {
    bool operator()(const cgl::point_type& p1, const cgl::point_type& p2){
      return p1[1]<p2[1];
    }

  };

  struct equals_xy_object_type
  {
    bool operator()(const cgl::point_type& p1, const cgl::point_type& p2){
      return p1[1]==p2[1] && p1[0]==p2[0];
    }

  };

  struct equals_lines_object_type
  {
    bool operator()(const line_type& l1, const line_type& l2){
      return    l1[1][1]==l2[1][1] && l1[0][0]==l2[0][0] &&
          l1[0][1]==l2[0][1] && l1[1][0]==l2[1][0];
    }

  };

  struct less_xy_object_type
  {
    bool operator()(cgl::point_type p1, cgl::point_type p2){
      return p1[0]<p2[0] ||      (!(p2[0]<p1[0]) && p1[1]<p2[1]);
    }

  };
  struct less_nth_object_type
  {
    private:
      std::size_t dimension;
    public:
      less_nth_object_type(std::size_t d):dimension(d){}
      bool operator()(multiD_point_type p1, multiD_point_type p2)
      {
        return p1[dimension-1]<p2[dimension-2];
      }
  };

  less_nth_object_type less_nth_object(std::size_t n)
  {
    return less_nth_object_type(n);
  }
  less_x_object_type less_x_object()
  {
    return less_x_object_type();
  }
  less_y_object_type less_y_object()
  {
    return less_y_object_type();
  }
  less_xy_object_type less_xy_object()
  {
    return less_xy_object_type();
  }
  equals_xy_object_type equals_xy_object()
  {
    return equals_xy_object_type();
  }

  equals_lines_object_type equals_lines_object()
  {
    return equals_lines_object_type();
  }


  //point related predicates and functions


  point_type make_point(coord_type x, coord_type y)
  {
    point_type p = {x,y};
    return p;
  }

  coord_type get_x_coordinate(point_type p)
  {
    return p[0];
  }

  coord_type get_y_coordinate(point_type p)
  {
    return p[1];
  }


  // box-related predicate and functions


  box_type make_empty_box()
  {
    box_type new_box;
    point_type p = {0,0};
    new_box[3] = new_box[2] = new_box[1] = new_box[0] = p;
  }


  box_type make_box(point_type ll, point_type ur)
  {
    if( ur[0]<ll[0] || ur[1]<ll[1] ||
     (!(ll[0] < ur[0]) && !(ur[0] < ll[0])) || //ll[0]==ur[0]
     (!(ll[0] < ur[0]) && !(ur[0] < ll[0])) )  //ll[1]==ur[1]
    {
      return make_empty_box();
    }

    return make_box (ll[0],ur[0],ur[1],ll[1]);
  }

  //returns a box given x coordinates of the top and bottom sides and y coordinates of the left and right sides
  box_type make_box(coord_type left, coord_type right,
        coord_type top, coord_type bottom)
  {

    box_type new_box;

    point_type ll = {left, bottom};
    point_type ul = {left, top};
    point_type ur = {right, top};
    point_type lr = {right, bottom};

    new_box[0] = ll;            //lower left
    new_box[1] = lr;            //lower right
    new_box[2] = ul;            //upper left
    new_box[3] = ur;            //upper right

    return new_box;

  }

  bool is_empty_box(box_type box)
  {
    return get_x_coordinate(box[0])== get_x_coordinate(box[1]) &&
         get_y_coordinate(box[0])== get_x_coordinate(box[1]) &&
         get_x_coordinate(box[2])== get_x_coordinate(box[3]) &&
         get_y_coordinate(box[2])== get_x_coordinate(box[3]) ;
  }

  coord_type get_left(box_type Q)
  {
    return lower_left(Q)[0];
  }

  coord_type get_right(box_type Q)
  {
    return upper_right(Q)[0];
  }

  coord_type get_top(box_type Q)
  {
    return upper_right(Q)[1];
  }

  coord_type get_bottom(box_type Q)
  {
    return lower_left(Q)[1];
  }

  point_type lower_left(box_type box)
  {
    return box[0];
  }

  point_type lower_right(box_type box)
  {
    return box[1];
  }

  point_type upper_left(box_type box)
  {
    return box[2];
  }

  point_type upper_right(box_type box)
  {
    return box[3];
  }

  bool disjoint(box_type b1, box_type b2)
  {
    return
    b2.upper_right()[0] < b1.upper_left() [0]  ||       //to the left
    b1.upper_right()[0] < b2.upper_left() [0]  ||       //to the right
    b2.upper_left() [1] < b1.lower_left() [1]  ||       //below
    b1.upper_left() [1] < b2.lower_left() [1]  ;        //above
  }


  //false otherwise
  //if box is empty, false is returned
  bool point_in_box(point_type p, box_type box)
  {
    if(is_empty_box(box))
    {
      return false;
    }

    return !(get_y_coordinate(p) < get_bottom(box)) && //get_bottom(box)<=get_y_coordinate(p)
         get_top(box)>get_y_coordinate(p) &&
         !(get_x_coordinate(p)< get_left(box)) &&   //get_left(box)<=get_x_coordinate(p)
         get_right(box)>get_x_coordinate(p);

  }

  //false otherwise
  //if box is empty, false is returned
  bool point_in_closed_box(point_type p, box_type box)
  {
    if(is_empty_box(box))
    {
      return false;
    }
    return !(get_y_coordinate(p) < get_bottom(box)) &&     //get_bottom(box)<=get_y_coordinate(p)
         !(get_top(box)<get_y_coordinate(p)) &&            //get_top(box)>=get_y_coordinate(p)
         !(get_x_coordinate(p)< get_left(box)) &&        //get_left(box)<=get_x_coordinate(p)
         !(get_right(box)<get_x_coordinate(p));            //get_right(box)>=get_x_coordinate(p)


  }

  //if both boxes are empty, false is returned
  //if either box is empty, but not both, true is returned
  bool contains(box_type inner, box_type outer)
  {
    if(is_empty_box(inner) && is_empty_box(outer))
    {
      return false;
    }
    else if(is_empty_box(inner))
    {
      return true;
    }
    else if(is_empty_box(outer))
    {
      return true;
    }

    return
    point_in_box(lower_left(inner),outer) &&
    point_in_box(upper_left(inner),outer) &&
    point_in_box(lower_right(inner),outer) &&
    point_in_box(upper_right(inner),outer);
  }


  box_type box_hull(box_type b1, box_type b2)
  {
    box_type new_box;
    point_type ll ={std::min (lower_left(b1)[0], lower_left(b2)[0]),
        std::min (lower_left(b1)[1], lower_left(b2)[1])
        };
    point_type ur ={std::max (upper_right(b1)[0], upper_right(b2)[0]),
        std::max (upper_right(b1)[0], upper_right(b2)[0])
        };

    return make_box(ll,ur);
  }


  box_type intersection(box_type b1, box_type b2)
  {
    if(disjoint(b1,b2))
    {
      return make_empty_box();
    }

    //else do the work
    point_type ll ={std::max(lower_left(b1)[0],lower_left(b2)[0]),
        std::max(lower_left(b1)[1],lower_left(b2)[1])
        };
    point_type ur ={std::min(upper_right(b1)[0],upper_right(b2)[0]),
        std::min(upper_right(b1)[1],upper_right(b1)[1])
        };
    return make_box(ll,ur);

  }

  /*
   * halfplane predicates and functions
   */

    halfplane_type make_halfplane(point_type a, point_type b, side which_one)
    {
      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      //\TODO what if they have the same x-value
      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


      //point with the smaller x-coordinate will always be in position 0
       boost::array<point_type,2> pp;
       pp[0]=std::min(a,b, less_x_object());
       pp[1]=std::max(a,b, less_x_object());

       halfplane_type halfplane(pp,which_one);

       return halfplane;
    }

    halfplane_type make_halfplane(point_type a, point_type b)
    {
      less_xy_object_type comparator;
      if(comparator(a,b))
      {
        return make_halfplane(a,b,TOP);
      }
      else
      {
        return make_halfplane(a,b,BOTTOM);
      }

    }

    //halfplane is considered to be empty if it is defined by two points
    //having the same coordinates
    halfplane_type empty_halfplane()
    {
      return make_plane(make_point(0,0),make_point(0,0),TOP);
    }

    bool
    is_empty_halfplane(halfplane_type halfplane)
    {
      return (halfplane.first)[0][0]==(halfplane.first)[0][1] &&
           (halfplane.first)[1][0]==(halfplane.first)[1][1] ;
    }

    boost::array<point_type,2> get_halfplane_points(halfplane_type halfplane)
    {
      return halfplane.first;
    }

    bool is_TOP(halfplane_type halfplane)
    {
      return halfplane.second == TOP;
    }

    bool is_BOTTOM(halfplane_type halfplane)
    {
      return halfplane.second == BOTTOM;
    }



    bool point_in_halfplane(point_type point, halfplane_type halfplane)
    {
      //if the plane spans the bottom portion,
      //all that needs to be done is to check if the points
      //the define the plane and the point that is beeing checked
      //make a left turn
      if(is_empty_halfplane(halfplane))
      {
        return false;
      }
      if( is_TOP(halfplane))
      {
        return
        _point_position( (halfplane.first)[0],(halfplane.first)[1],point) == LEFT_TURN;
      }

      //otherwise, check if it makes a right turn
      else
      {
      return
        _point_position( (halfplane.first)[0],(halfplane.first)[1],point) == RIGHT_TURN;
      }
    }


  side top()
  {
    return TOP;
  }

  side bottom()
  {
    return BOTTOM;
  }


  /*
   * lines
   */

  line_type make_line(const point_type& a, const point_type& b)
  {
    line_type l = {std::min(a,b, less_x_object_type()),
            std::max(a,b, less_x_object_type())};
    return l;
  }



  /*
   * triangles
   */


  triangle_type make_trianlge(point_type a, point_type b, point_type c)
  {
    triangle_type new_t= {a,b,c};
    std::sort(new_t.begin(), new_t.end(), less_x_object());

  }

  //point is inside a convex polygon if all  p1,p2, p
  //make the same turn (left or right)
  bool point_in_open_triangle(point_type p, triangle_type t)
  {
    return _point_position(t[0], t[1], p)==
              _point_position(t[1], t[2], p) &&
              _point_position(t[1], t[2], p)==
              _point_position(t[2], t[0], p);
  }

  bool point_in_closed_triangle(point_type p, triangle_type t)
  {
    return      point_in_open_triangle(p, t) ||
        _point_position(t[0], t[1], p) == COLLINEAR ||
        _point_position(t[1], t[2], p) == COLLINEAR ||
        _point_position(t[2], t[0], p) == COLLINEAR;

  }

private:
  enum type {LEFT_TURN, COLLINEAR, RIGHT_TURN};

  /*
     * Given three points
     * 2 points that define a plane
     * 1 argument point
     *
     * the determinant of the matrix is
     *
     *        |a0 a1 1 |
     *    D = |b0 b1 1 | = (b0 - a0)(c1 - a1) - (b1 - a1)(c0 - a0)
     *        |c0 c1 1 |
     *
     * if D>0, than the points make a left turn
     * if D==0, then the points are collinear
     * else, points make a right turn
     */
    type
    _point_position(point_type plane_point1, point_type plane_point2, point_type point)
    {
      coord_type D =   (plane_point2[0] - plane_point1[0])
              *(point[1] - plane_point1[1])
              -(plane_point2[1] - plane_point1[1])
              *(point[0] - plane_point1[0]);

      if(0<D)
      {
        return LEFT_TURN;
      }
      else if (D<0)
      {
        return RIGHT_TURN;
      }
      else
      {
        return COLLINEAR;

      }
    }

}; //end cgl


#include <iostream>


std::ostream& operator<<(std::ostream& os, cgl<double>::line_type l)
{
  os<<"("<<l[0][0]<<","<<l[0][1]<<")-("
    <<l[1][0]<<","<<l[1][1]<<")";
  return os;
}

std::ostream& operator<<(std::ostream& os, cgl<int>::line_type l)
{
  os<<"("<<l[0][0]<<","<<l[0][1]<<")-("
    <<l[1][0]<<","<<l[1][1]<<")";
//os<<l[0][1];
  return os;
}


std::ostream& operator<<(std::ostream& os, cgl<double>::point_type l)
{
  os<<"("<<l[0]<<","<<l[1]<<")";
  return os;
}



std::ostream& operator<<(std::ostream& os, cgl<int>::point_type l)
{
  os<<"("<<l[0]<<","<<l[1]<<")";
  return os;
}
std::ostream& operator<<(std::ostream& os, cgl<float>::line_type l)
{
  os<<"("<<l[0][0]<<","<<l[0][1]<<")-("
    <<l[1][0]<<","<<l[1][1]<<")";
  return os;
}

std::ostream& operator<<(std::ostream& os, cgl<float>::line_type& l)
{
  os<<"("<<l[0][0]<<","<<l[0][1]<<")-("
    <<l[1][0]<<","<<l[1][1]<<")";
  return os;
}

std::ostream& operator<<(std::ostream& os, cgl<float>::point_type l)
{
  os<<"("<<l[0]<<","<<l[1]<<")";
  return os;
}


bool operator==(cgl<int>::line_type& a, cgl<int>::line_type& b)
{
        return (a[0][0]==b[0][0] &&
                a[0][1]==b[0][1] &&
                a[1][0]==b[1][0] &&
                a[1][1]==b[1][1]);
}

#endif

---

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.