Bentley-Otmann Algorithm 2.0
An implementation of Bentley-Ottmann algorithm in order to count the m,n-cubes
|
Definition of geometric objects. More...
#include <vector>
#include <iostream>
#include <gmpxx.h>
#include <boost/rational.hpp>
#include "integer_type.hpp"
Go to the source code of this file.
Classes | |
class | Point |
2D points with rational coordinates More... | |
struct | Slope |
Slope of a segment line. More... | |
class | Segment |
2D segment lines More... | |
class | Event |
Event for Bentley-Ottmann's algorithm. More... | |
Typedefs | |
typedef int | I |
Rational type. | |
typedef boost::rational< int > | rat |
Enumerations | |
enum | slope_t { undef, rational, infty } |
Kind of slope. More... | |
Functions | |
std::ostream & | operator<< (std::ostream &, const Segment &) |
Pretty-printing for Segment. | |
std::ostream & | operator<< (std::ostream &, const Segment *&) |
Pretty-printing for mpz_class. | |
std::ostream & | operator<< (std::ostream &, const Point &) |
Pretty-printing for Point. |
Definition of geometric objects.
Here are implemented classes for geometric objects. First, a simple class for 2D points. Next, a class for 2D segments with possibility of ordering. Last, a class for 'events', an ameloriated type of point used in Bentley-Ottmann algorithm.
Definition in file geometry.hpp.
typedef int I |
Rational type.
This type can be a rational type with arbitrary precision (if USE_BIGINT is true) using the GMP library. Otherwise, it just is a rational type with numerator and denominator of type int.
Another library can be use instead of GMP by changing only this two typedef (and of course the included header(s) of the library). The only requirement for a good behaviour are : I should have a constructor from the paramater type int.
Definition at line 44 of file geometry.hpp.
enum slope_t |
Kind of slope.
Defines a kind of slope for the slope structure. undef is only used in default construction.
Definition at line 88 of file geometry.hpp.
std::ostream& operator<< | ( | std::ostream & | begin, |
const Segment & | s | ||
) |
Pretty-printing for Segment.
begin | Ostream |
s | Segment to print |
Definition at line 272 of file geometry.cpp.
std::ostream& operator<< | ( | std::ostream & | begin, |
const Point & | p | ||
) |
Pretty-printing for Point.
begin | Ostream |
p | Point to print |
Definition at line 248 of file geometry.cpp.
std::ostream& operator<< | ( | std::ostream & | begin, |
const Segment *& | s | ||
) |
Pretty-printing for mpz_class.
begin | Ostream |
z | Integer to print |
begin | Ostream |
f | Rational to print |
Definition at line 237 of file geometry.cpp.