Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
poly_utils.h
Go to the documentation of this file.
1 #ifndef POLYGON_H
2 #define POLYGON_H
3 
4 #include <data/types.h>
5 #include <poly/types.h>
6 #include <poly/triangulation.h>
7 
8 #include <iterator>
9 #include <boost/unordered_map.hpp>
10 
12 # define CGAL_HEADER_ONLY 1
13 # define CGAL_NO_GMP 1
15 //#define CGAL_NO_PRECONDITIONS 1
16 //#define CGAL_NO_POSTCONDITIONS 1
17 #include <CGAL/Polygon_2.h>
18 #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
19 #include <CGAL/partition_2.h>
20 
21 namespace frechet { namespace poly {
22 
25 typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
26 
43 class CgalPoint: public CGAL::Point_2<Kernel>
44 {
45 public:
46  typedef CGAL::Point_2<Kernel> super;
48  int i;
50  mutable bool erase;
51 
53  CgalPoint();
54 
61  CgalPoint(const QPointF& p, int i=-1);
62  //
70  CgalPoint(double x, double y, int i=-1);
71 
77  CgalPoint& operator= (const QPointF& p);
78 
82  operator QPointF() const;
83 };
84 
89 struct PolygonTraits: public Kernel {
92 };
93 
95 typedef CGAL::Polygon_2<PolygonTraits> CgalPolygon;
97 typedef std::list<CgalPolygon> CgalPolygonList;
98 
103 struct PartitionTraits: public CGAL::Partition_traits_2<PolygonTraits> {
108 };
109 
122 {
123 private:
128 public:
136  };
137 public:
146  PolygonUtilities(const Curve& p);
147 
153  //bool is_closed() const;
158  bool is_simple() const;
162  bool is_convex() const;
167  bool is_counter_clockwise();
168 
169  //int vertexes() const;
170  //int edges() const;
171 
172  //void revert();
173 
176  // @return numer of convex parts
184  int decompose(DecompositionAlgorithm algo, bool verify);
185 
193  int partition(Partition& partition) const;
194 
202  int simplify();
203 
211  void findReflexVertices(Polygon& poly, double tolerance=0.0);
212 
213  // erstellt ein Fan-Triangulierung mehrerer (konvexer!) Polygone
221  void fanTriangulate(Triangulation& tri) const;
222 
223 
224 private:
229  bool assertStrictlySorted(const CgalPolygon&);
238  static bool create1Diagonal(int u, int v, int n, Partition& partition);
239 
246  bool simplify(CgalPolygon& poly);
252  void fanTriangulate(const CgalPolygon& poly, Triangulation& tri) const;
260  static bool is_reflex_vertex(const CgalPolygon::Vertex_circulator& p, double precision=0.0);
261 };
262 
264 std::ostream& operator<< (std::ostream& out, const frechet::poly::CgalPolygon& poly);
266 std::ostream& operator<< (std::ostream& out, const frechet::poly::CgalPolygonList& polys);
267 
268 
269 }} // namespace frechet::poly
270 
271 
272 #endif // POLYGON_H
CgalPolygon cgp
the polygon under examination
Definition: poly_utils.h:125
Greene's approximation algorithm.
Definition: poly_utils.h:133
int decompose(DecompositionAlgorithm algo, bool verify)
compute a convex decomposition of the polygon. Store results in the member variable 'convex'.
Definition: poly_utils.cpp:58
int partition(Partition &partition) const
compute a list of sub-polygons, one for each convex part. This is mainly copying data to a more conve...
Definition: poly_utils.cpp:107
frechet::poly::CgalPoint Point_2
replace Point_2 with our custom type
Definition: poly_utils.h:91
static bool create1Diagonal(int u, int v, int n, Partition &partition)
create a diagonal in a convex partition
Definition: poly_utils.cpp:136
void findReflexVertices(Polygon &poly, double tolerance=0.0)
find all reflex (concave) vertices.
Definition: poly_utils.cpp:279
global definitions for all algorithms.
PolygonUtilities()
empty constructor
Definition: poly_utils.cpp:9
frechet::poly::CgalPoint Point_2
replace Point_2 with our custom type
Definition: poly_utils.h:105
bool assertStrictlySorted(const CgalPolygon &)
debug assertion
Definition: poly_utils.cpp:146
bool erase
used by PolgonUtilities::simplify to mark vertexes for deletion
Definition: poly_utils.h:50
Hertel and Mehlhorn's approximation algorithm.
Definition: poly_utils.h:134
CgalPolygonList convex
list of convex parts. created by decompose().
Definition: poly_utils.h:127
int i
index of polygon vertex (-1 if not available)
Definition: poly_utils.h:48
int simplify()
Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges....
Definition: poly_utils.cpp:163
std::list< CgalPolygon > CgalPolygonList
a list of CgalPolygons
Definition: poly_utils.h:97
CGAL::Exact_predicates_inexact_constructions_kernel Kernel
Definition: poly_utils.h:25
CGAL::Point_2< Kernel > super
Definition: poly_utils.h:46
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
Definition: types.h:20
std::list< Polygon > Partition
a partitioning of a polygon, that is a list of sub-sets
Definition: types.h:117
void fanTriangulate(Triangulation &tri) const
compute a fan-triangulation from a list of convex parts. Each convex sub-polygon is triangulated usin...
Definition: poly_utils.cpp:254
CgalPoint & operator=(const QPointF &p)
assignment operator from QPointF
Definition: poly_utils.cpp:325
CGAL::Polygon_2< PolygonTraits > CgalPolygon
CGAL::Polygon_2 built upon custom type.
Definition: poly_utils.h:95
static bool is_reflex_vertex(const CgalPolygon::Vertex_circulator &p, double precision=0.0)
test whether a vertex is a reflex (concave) vertex
Definition: poly_utils.cpp:290
CgalPoint()
empty constructor
Definition: poly_utils.cpp:313
DecompositionAlgorithm
choice of decomposition algorithm
Definition: poly_utils.h:132
std::vector< int > Polygon
Polygon a sub-set of vertex indexes.
Definition: types.h:113
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
a helper class for polygon analysis.
Definition: poly_utils.h:121
type traits for CgalPolygon. Defines the type for Points.
Definition: poly_utils.h:89
frechet::poly::CgalPolygon Polygon_2
replace Polygon_2 with our custom type
Definition: poly_utils.h:107
a polygon vertex to be used with CGAL::Polygon_2. Derives from CGAL::Point_2 but is convertible to an...
Definition: poly_utils.h:43
type traits for a polygon partition Defines the type for Points and Polygons
Definition: poly_utils.h:103
std::ostream & operator<<(std::ostream &out, const frechet::poly::CgalPolygon &poly)
print operator (for debugging)
Definition: poly_utils.cpp:338