Bentley-Otmann Algorithm 2.0
An implementation of Bentley-Ottmann algorithm in order to count the m,n-cubes
geometry.hpp
Go to the documentation of this file.
00001 
00015 #ifndef H_GEO
00016 #define H_GEO
00017 
00018 #include <vector>
00019 #include <iostream>
00020 #include <gmpxx.h>
00021 #include <boost/rational.hpp>
00022 #include "integer_type.hpp"
00023 
00037 #if USE_BIGINT
00038 
00039 typedef mpz_class I;
00040 typedef mpq_class rat;
00041 
00042 #else 
00043 
00044 typedef int I;
00045 typedef boost::rational<int> rat;
00046 
00047 #endif
00048 
00053 class Point {
00054 private:
00055   rat x; 
00056   rat y; 
00057 
00058 public:
00059  
00063   Point() : x(), y() {};
00064 
00069   Point(const Point& p) : x(p.x), y(p.y) {};
00070   
00075   Point(const rat& xx, const rat& yy) : x(xx), y(yy) {};
00076   rat get_abscissa() const;
00077   rat get_ordinate() const;
00078   void assign(const rat&,const rat&);
00079 };
00080 
00081 
00088 enum slope_t {undef, rational, infty};
00089 
00093 struct Slope {
00094   slope_t type; 
00095   rat value; 
00096   void make(const rat&,const rat&,const rat&,const rat&);
00097   bool operator<(const Slope&) const;
00098 };
00099 
00110 class Segment {
00111 private:
00112   Point left; 
00113   Point right; 
00114   Slope slope; 
00115 
00116 public:
00117 
00121   Segment() : left(), right() { slope.type = undef; };
00122 
00127   Segment(const Segment& seg) : left(seg.left), right(seg.right) {
00128     slope.type = seg.slope.type;
00129     if(slope.type == rational)
00130       slope.value = seg.slope.value;
00131   };
00132 
00137   Segment(const Point& a, const Point& b) : left(a), right(b) {
00138     slope.make(a.get_abscissa(), a.get_ordinate(), b.get_abscissa(), b.get_ordinate());
00139   };
00140 
00146   Segment(const rat& xa, const rat& ya, const rat& xb, const rat& yb)
00147     : left(xa, ya), right (xb, yb) {
00148     slope.make(xa,ya,xb,yb);
00149   };
00150   Point get_left() const;
00151   Point get_right() const;
00152   rat high(const Point&) const;
00153   bool less(const Segment&, const Point&) const;
00154   bool intersect(const Segment&, Point&) const;
00155   bool is_rend(const Point&) const;
00156   bool is_lend(const Point&) const;
00157   bool is_in(const Point&) const;
00158 };
00159 
00160 // Pretty-printing
00161 std::ostream& operator<<(std::ostream&, const Segment&);
00162 std::ostream& operator<<(std::ostream&, const Segment*&);
00163 std::ostream& operator<<(std::ostream&, const Point&);
00164 //std::ostream& operator<<(std::ostream&, const mpz_class&);
00165 //std::ostream& operator<<(std::ostream&, const mpq_class&);
00166 
00175 class Event {
00176 private:
00177   Point point; 
00178 public:
00180   Event() : point() {};
00181 
00183   Event(const Event& e) : point(e.point) {};
00184 
00186   Event(const Point& p) : point(p) {};
00187   Point get_point() const;
00188   bool operator<(const Event&) const;
00189 };
00190 
00191 #endif //H_GEO
 All Classes Files Functions Variables Typedefs Enumerations