Bentley-Otmann Algorithm 2.0
An implementation of Bentley-Ottmann algorithm in order to count the m,n-cubes
geometry.cpp
Go to the documentation of this file.
00001 
00009 #include "geometry.hpp"
00010 
00015 rat Point::get_abscissa() const {
00016   return x;
00017 }
00018 
00023 rat Point::get_ordinate() const {
00024   return y;
00025 }
00026 
00031 void Point::assign(const rat& x, const rat& y) {
00032   this->x = x, this->y = y;
00033   return ;
00034 }
00035 
00041 void Slope::make(const rat& x0, const rat& y0, const rat& x1, const rat&y1) {
00042   if(x0 == x1)
00043     type = infty;
00044   else {
00045     type = rational;
00046     value = (y0 - y1) / (x0 - x1) ;
00047   }
00048 
00049   return;
00050 }
00051 
00061 bool Slope::operator<(const Slope& s) const {
00062   if(type == infty)
00063     return false;
00064   else 
00065     return (s.type == infty || value < s.value);
00066 }
00067 
00072 Point Segment::get_left() const {
00073   return left;
00074 }
00075 
00080 Point Segment::get_right() const {
00081   return right;
00082 }
00083 
00093 bool Segment::intersect(const Segment& seg, Point& inter) const {
00094   // names
00095   Point s_left = seg.get_left(); Point s_right = seg.get_right();
00096   
00097   rat xa = left.get_abscissa(), ya = left.get_ordinate(),
00098     xb = right.get_abscissa(), yb = right.get_ordinate(),
00099     xc = s_left.get_abscissa(), yc = s_left.get_ordinate(),
00100     xd = s_right.get_abscissa(), yd = s_right.get_ordinate();
00101 
00102   static rat zero(I(0)), one(I(1));
00103 
00104   // determinant
00105   rat delta = (xb - xa)*(yc - yd) - (yb - ya)*(xc - xd);
00106 
00107   // Delta = 0 => no instersection
00108   if(delta == zero)
00109     return false;
00110 
00111   // computing r,s : Cramer's solutions
00112   rat r = (xc - xa)*(yc - yd) - (yc - ya)*(xc - xd); r /= delta;
00113   rat s = (yc - ya)*(xb - xa) - (xc - xa)*(yb - ya); s /= delta;
00114   
00115   // r, s in [0,1] else no intersection
00116   if(r<zero || r>one || s<zero || s>one)
00117     return false;
00118 
00119   rat xi = xa + r*(xb - xa), yi = ya + r*(yb - ya);
00120   inter.assign(xi, yi);
00121   
00122   return true;
00123 }
00124 
00141 rat Segment::high(const Point& p_sweep) const {
00142   static rat py, ly, ry;
00143   if(slope.type == infty) {
00144     py = p_sweep.get_ordinate(), ly = left.get_ordinate(),
00145       ry = right.get_ordinate();
00146     if(py < ly)
00147       return ly;
00148     else if(py > ry)
00149       return ry;
00150     else
00151       return py;
00152   }
00153   else {
00154     static rat xa, xb, ya, yb;
00155     xa = left.get_abscissa(), ya = left.get_ordinate(),
00156       xb = right.get_abscissa(), yb = right.get_ordinate();
00157     
00158     return (yb - ya)/(xb - xa)*(p_sweep.get_abscissa() - xa) + ya;
00159   }
00160 }
00161 
00172 bool Segment::less(const Segment& s, const Point& p_sweep) const {
00173    return (
00174            this->high(p_sweep) < s.high(p_sweep)
00175            || (
00176                this->high(p_sweep) == s.high(p_sweep)
00177                && this->slope < s.slope
00178                )
00179            );
00180 }
00181 
00187 bool Segment::is_rend(const Point& p) const {
00188   return (p.get_abscissa() == right.get_abscissa()
00189           && p.get_ordinate() == right.get_ordinate());
00190 }
00191 
00197 bool Segment::is_lend(const Point& p) const {
00198   return (p.get_abscissa() == left.get_abscissa()
00199           && p.get_ordinate() == left.get_ordinate());
00200 }
00201 
00207 bool Segment::is_in(const Point& p) const {
00208   //assuming p is on the segment
00209   return ((! is_rend(p)) && (! is_lend(p)));
00210 }
00211 
00212 // /**
00213 //  * \brief Pretty-printing for mpz_class
00214 //  * \param begin Ostream
00215 //  * \param z Integer to print
00216 //  * \return Ostream begin concatenated with the printing of z 
00217 //  */
00218 // std::ostream& operator<<(std::ostream& begin, const mpz_class& z) {
00219 //   begin << z.get_str();
00220 //   return begin;
00221 // }
00222 
00223 // /**
00224 //  * \brief Pretty-printing for mpq_class
00225 //  * \param begin Ostream
00226 //  * \param f Rational to print
00227 //  * \return Ostream begin concatenated with the printing of f 
00228 //  */
00229 // std::ostream& operator<<(std::ostream& begin, const mpq_class& f) {
00230 //   begin << f.get_num() << "/" << f.get_den();
00231 //   return begin;
00232 // }
00233 
00237 std::ostream& operator<<(std::ostream& begin, const Segment*& s) {
00238   begin << *s;
00239   return begin;
00240 }
00241 
00248 std::ostream& operator<<(std::ostream& begin, const Point& p) {
00249   begin << "(" << p.get_abscissa()
00250         << "," << p.get_ordinate()
00251         << ")";
00252   return begin;
00253 }
00254 
00261 std::ostream& operator<<(std::ostream& begin, const Event& e) {
00262   begin << e.get_point() ;
00263   return begin;
00264 }
00265 
00272 std::ostream& operator<<(std::ostream& begin, const Segment& s) {
00273   begin << "[(" << s.get_left().get_abscissa()
00274         << "," << s.get_left().get_ordinate()
00275         << "),(" << s.get_right().get_abscissa()
00276         << "," << s.get_right().get_ordinate()
00277         << ")]";
00278   return begin;
00279 }
00280 
00289 bool Event::operator<(const Event& e) const {
00290   return (
00291           (point.get_abscissa() < e.point.get_abscissa())
00292           || (
00293               (point.get_abscissa() == e.point.get_abscissa())
00294               && (point.get_ordinate() < e.point.get_ordinate())
00295               )
00296           );
00297 }
00298 
00303 Point Event::get_point() const {
00304   return point;
00305 }
 All Classes Files Functions Variables Typedefs Enumerations