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

functions.hpp

Go to the documentation of this file.

#ifndef FUNCTIONS_HPP
#define FUNCTIONS_HPP
/*
 * Copyright © Ilya Katz and Hervé Brönnimann, 2005.
 */
#include "data_node.hpp"
#include "cgl.hpp"
using namespace inplaceds;

typedef cgl<double>                                     Geometry;
typedef Geometry::line_type                     line_type;
typedef Geometry::point_type                    point_type;
typedef Geometry::coord_type                    coord_type;

#define slope(x1,y1,x2,y2) ( (y2-y1)/(x2-x1) )

#define ACCURACY_CUTTOFF 0.000000001



//WORK ON THIS!!!
/*
 Consider (14,29)(59,26) and (34,41)(96,52)
 Their intersection point is (34,41)

 */
template <class node>
struct event_compare
{
  bool operator()(const node& a, const node& b){
    //if two data_nodes have the same critical point (intersection)
    //priorities are given from left to right
    //LEFT_EVENT, INTERSECTION_EVENT , RIGHT_EVENT

    if( (geom.get_x_coordinate(a.point)-geom.get_x_coordinate(b.point))<ACCURACY_CUTTOFF
     && (geom.get_x_coordinate(b.point)-geom.get_x_coordinate(a.point))<ACCURACY_CUTTOFF)
    {
      if(a.myEvent==LEFT_EVENT)
      {
        return true;
      }
      else if(b.myEvent==LEFT_EVENT)
      {
        return false;
      }

      if(a.myEvent==INTERSECTION_EVENT)
      {
        return true;
      }
      else if(b.myEvent==INTERSECTION_EVENT)
      {
        return false;
      }
    }
    return geom.less_xy_object()(a.point,b.point);
  }

  Geometry geom;

};

template <class Node>
struct vertical_compare
{
                typedef cgl<double>    Geometry;
  typedef typename Node::line_type       line_type;
  typedef typename Node::coord_type     coord_type;
  typedef typename Node::point_type     point_type;


  vertical_compare(Geometry& g, coord_type& p):
      geom(g), m_p(p){}

  bool operator()(const Node& a, const Node& b){
    return operator()(a.line,b.line);
  }


   //* THE TEST IS DIFFERENT FROM HERVE'S
   //* CHECK IT!

  bool operator()(const line_type& l1, const line_type& l2){

    //two lines are equal
    if(l1[0][0]==l2[0][0] && l1[0][1]==l2[0][1] &&
      l1[1][0]==l2[1][0] && l1[1][1]==l2[1][1]){
        return false;
      }

    //else, need to check which line is has higher
    //y-coordinate at the current sweepline position
    coord_type m1 = slope(l1[0][0],l1[0][1], l1[1][0], l1[1][1]),
           m2 = slope(l2[0][0],l2[0][1], l2[1][0], l2[1][1]);

    coord_type b1 = l1[0][1]-m1*l1[0][0],
         b2 = l2[0][1]-m2*l2[0][0];

    coord_type currentY1 = m1*m_p + b1,
           currentY2 = m2*m_p + b2;

    return (currentY1-currentY2)<ACCURACY_CUTTOFF;

  }
  private:
    Geometry geom;
    coord_type& m_p;
};



std::pair<bool, point_type>
intersection(const line_type& l1, const line_type& l2){

  std::pair<bool, point_type> ret(false, point_type());

  coord_type m1 = slope(l1[0][0], l1[0][1], l1[1][0], l1[1][1]),
      m2 = slope(l2[0][0], l2[0][1], l2[1][0], l2[1][1]);

  if(m1 == m2){  //lines are parallel
    return ret;
  }

  coord_type b1 = l1[0][1]-m1*l1[0][0],
         b2 = l2[0][1]-m2*l2[0][0];

  coord_type x = (b2-b1)/(m1-m2);

  //originally, the left end point is at position [0]
  //but, beacuse of encoding intersection, these positions
  //may have changed
  if(x<std::min(l1[0][0],l1[1][0]) || x>std::max(l1[0][0],l1[1][0]) ||
     x<std::min(l2[0][0],l2[1][0]) || x>std::max(l2[0][0],l2[1][0])){
    return ret;
  }

  coord_type y1 = m1 * x + b1;
  coord_type y2 = m2 * x + b2;

  //if not equal, return false
  if(!((y1-y2)<ACCURACY_CUTTOFF)){
    return ret;
  }

  //special case: if left-end point of a line is the intersection
  //point, do not consider it
  if(((l1[0][0]-x)<ACCURACY_CUTTOFF && (l1[0][1]-y1)<ACCURACY_CUTTOFF) &&
      (x-l1[0][0])<ACCURACY_CUTTOFF && (y1-l1[0][1])<ACCURACY_CUTTOFF )
                  {
                        return ret;
                  }
  if(((l2[0][0]-x)<ACCURACY_CUTTOFF && (l2[0][1]-y1)<ACCURACY_CUTTOFF) &&
      (x-l2[0][0])<ACCURACY_CUTTOFF && (y1-l2[0][1])<ACCURACY_CUTTOFF )
                  {
                        return ret;
                  }
        if(((l1[1][0]-x)<ACCURACY_CUTTOFF && (l1[1][1]-y1)<ACCURACY_CUTTOFF) &&
      (x-l1[1][0])<ACCURACY_CUTTOFF && (y1-l1[1][1])<ACCURACY_CUTTOFF )
                  {
                        return ret;
                  }
  if(((l2[1][0]-x)<ACCURACY_CUTTOFF && (l2[1][1]-y1)<ACCURACY_CUTTOFF) &&
      (x-l2[1][0])<ACCURACY_CUTTOFF && (y1-l2[1][1])<ACCURACY_CUTTOFF )
                  {
                        return ret;
                  }
  ret.second[0]=x;
  ret.second[1]=y1;
  ret.first=true;

  return ret;
}


#endif

---

Code Documentation generated Using Doxygen

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