Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
poly_utils.cpp
Go to the documentation of this file.
1 
2 #include <poly_utils.h>
4 
5 
6 using namespace frechet;
7 using namespace poly;
8 
10  : cgp()
11 { }
12 
26  : cgp()
27 {
28  Q_ASSERT(p.isClosed());
29 
30  // we index vertices in ascending order; so we can detecte diagonals later
31  auto v = p.cbegin();
32  // with QPolygonF, the first vertex is duplicated as the last vertex
33  // with CGAL::Polygon_2 is IS NOT !
34  auto vend = p.cend()-1;
35 
36  for(int i=0; v!=vend; ++v,++i)
37  cgp.push_back(CgalPoint(*v,i));
38 
39  Q_ASSERT(assertStrictlySorted(cgp));
40  Q_ASSERT(cgp.size()+1 == p.size());
41 }
42 
44 {
45  return cgp.is_simple();
46 }
47 
49 {
50  return cgp.is_convex();
51 }
52 
54 {
55  return cgp.is_counterclockwise_oriented();
56 }
57 
59 {
60  convex.clear();
61  Q_ASSERT(assertStrictlySorted(cgp));
62 
63  try {
64  PartitionTraits traits;
65  switch(algo)
66  {
67  case APPROX_GREENE:
68  // Greene approximation, O(n log n) (approx. ratio 4, but rarely)
69  CGAL::greene_approx_convex_partition_2(
70  cgp.vertices_begin(), cgp.vertices_end(),
71  std::back_inserter(convex), traits);
72  break;
73  case APPROX_HERTEL:
74  // 4-approximation of Hertel and Mehlhorn
75  // time O(n)
76  CGAL::approx_convex_partition_2(
77  cgp.vertices_begin(), cgp.vertices_end(),
78  std::back_inserter(convex),
79  traits);
80  break;
81  case OPTIMAL_GREENE:
82  // optimal, Greene, O(n^4)
83  CGAL::optimal_convex_partition_2(
84  cgp.vertices_begin(), cgp.vertices_end(),
85  std::back_inserter(convex),
86  traits);
87  break;
88  }
89 
90  if (verify) {
91  bool ok = CGAL::convex_partition_is_valid_2(
92  cgp.vertices_begin(), cgp.vertices_end(),
93  convex.begin(), convex.end(),
94  traits);
95  //Q_ASSERT(ok);
96  if (!ok) return -1;
97  }
98  } catch (std::exception& error) {
99  std::cerr << error.what() << std::endl;
100  return -1;
101  }
102 
103  Q_ASSERT(assertStrictlySorted(cgp));
104  return convex.size();
105 }
106 
108 {
109  // assumes decompose has already been called
110  Q_ASSERT(! convex.empty());
111  partition.clear();
112 
113  int n = cgp.size();
114  // copy to partition
115  for(const auto& part : convex)
116  {
117  partition.push_back(Polygon());
118 
119  Q_ASSERT(! part.is_empty());
120  Q_ASSERT(part.size() >= 3);
121 
122  auto v1 = part.vertices_begin();
123  auto v2 = v1+1;
124  auto vend = part.vertices_end();
125 
126  for( ; v2!=vend; ++v1,++v2)
127  create1Diagonal(v1->i,v2->i, n, partition);
128 
129  v2 = part.vertices_begin();
130  create1Diagonal(v1->i,v2->i, n, partition);
131  }
132 
133  return (int) partition.size(); // ?
134 }
135 
136 bool PolygonUtilities::create1Diagonal(int u, int v, int n, Partition& partition)
137 {
138  Segment seg(u,v);
139  if (! seg.is_diagonal(n)) return false;
140 
141  partition.back().push_back(u);
142  partition.back().push_back(v);
143  return true;
144 }
145 
147 {
148  auto p = cgp.vertices_begin();
149  auto q = p+1;
150  auto end = cgp.vertices_end();
151 
152  int j=0;
153  for( ; q!=end; ++p,++q,++j) {
154  Q_ASSERT(p->i >= 0);
155  Q_ASSERT(q->i >= 0);
156  Q_ASSERT(p->i==j);
157  Q_ASSERT(p->i+1 == q->i);
158  }
159  return true;
160 }
161 
162 
164 {
165  Q_ASSERT(!convex.empty());
166  CgalPolygonList::iterator i = convex.begin();
167  CgalPolygonList::iterator iend = convex.end();
168 
169 // std::cout << convex << std::endl;
170 
171  while(i != iend) {
172  CgalPolygon& poly = *i;
173  if (! simplify(poly))
174  i = convex.erase(i);
175  else
176  ++i;
177  }
178  return convex.size();
179 // std::cout << convex << std::endl;
180 }
181 
183 {
184  if (poly.size() <= 2)
185  return false;
186 
187  // contract all "real" edges
188  int n = cgp.size();
189  CgalPolygon::Vertex_circulator pbegin = poly.vertices_circulator();
190  CgalPolygon::Vertex_circulator p = pbegin;
191 
192  // mark for erase
193  do {
194  if (Segment((p-1)->i, p->i).is_edge(n)
195  && Segment(p->i,(p+1)->i).is_edge(n))
196  p->erase=true;
197  } while(++p != pbegin);
198 
199  // do erase
200  auto q = poly.vertices_begin();
201  while(q != poly.vertices_end())
202  if (q->erase)
203  q = poly.erase(q);
204  else
205  ++q;
206 
207  return poly.size() > 2;
208 }
209 
210 static int distance(int a, int b, int n)
211 {
212  if (b < a) b += n;
213  return b-a;
214 }
215 
216 static bool is_edge(int a, int b, int n)
217 {
218  return distance(a,b,n) == 1;
219 }
220 
221 static bool is_diagonal(int a, int b, int n)
222 {
223  return distance(a,b,n) > 1;
224 }
225 
227 {
228  auto p0 = poly.vertices_begin();
229  auto p1 = p0+1;
230 
231  if (poly.size() < 3) {
232  // degenerated poly.
233  // Diagonals are actually outer edges and have no neighbor.
234  Q_ASSERT(false);
235 // if (poly.size()==2)
236 // tri.outerEdge(Segment(p0->i,p1->i));
237  return;
238  }
239 
240  // Faces erstellen
241  auto p2 = p0+2;
242  auto pend = poly.vertices_end();
243 
244  tri.createVertex((Point)*p0, p0->i);
245  tri.createVertex((Point)*p1, p1->i);
246 
247  for( ; p2!=pend; p1=p2++) {
248  tri.createVertex((Point)*p2, p2->i);
249  tri.createFace(p0->i,p1->i,p2->i);
250  }
251 }
252 
253 // erstellt ein Fan-Triangulierung mehrerer (konvexer!) Polygone
255 {
256  Q_ASSERT(!convex.empty());
257  for(const CgalPolygon& poly : convex)
258  fanTriangulate(poly,tri);
259 
260  tri.complement();
261  // all vertices must be defined
262  Q_ASSERT(tri.isComplete());
263  //Q_ASSERT(tri.size()==cgp.size());
264  //Q_ASSERT(tri.countFaces() > convex.size());
265  //Q_ASSERT(tri.countVertexes()>=0 && tri.countVertexes()<=cgp.size());
266 #ifdef QT_DEBUG
267  for (int i=0; i < cgp.size(); ++i)
268  {
269  Triangulation::Vertex_handle v = tri[i];
270  if (v==Triangulation::Vertex_handle()) continue;
271  Q_ASSERT(v->pindex == i);
272  Q_ASSERT(v->pindex == cgp[i].i);
273  Q_ASSERT(cgp[i].erase==false);
274  Q_ASSERT(((Point)*v)==((Point)cgp[i]));
275  }
276 #endif
277 }
278 
280 {
281  CgalPolygon::Vertex_circulator pbegin = cgp.vertices_circulator();
282  CgalPolygon::Vertex_circulator p = pbegin;
283 
284  do {
285  if (is_reflex_vertex(p,tolerance))
286  reflex.push_back(p->i);
287  } while(++p != pbegin);
288 }
289 
290 bool PolygonUtilities::is_reflex_vertex(const CgalPolygon::Vertex_circulator& v, double tolerance)
291 {
292  const CgalPoint& a = *(v-1);
293  const CgalPoint& b = *v;
294  const CgalPoint& p = *(v+1);
295 
306  // TODO code is duplicated from PolygonShortestPaths::halfplaneTest; not necessary
307  double A = (p.y()-a.y()) * (b.x()-a.x());
308  double B = (p.x()-a.x()) * (b.y()-a.y());
309  return A < B+tolerance;
310 }
311 
312 
313 CgalPoint::CgalPoint() : super(),i(-1),erase(false)
314 { }
315 
316 
317 CgalPoint::CgalPoint(const QPointF& p, int ai)
318 : CgalPoint(p.x(),-p.y(),ai)
319 { }
320 
321 CgalPoint::CgalPoint(double x, double y, int ai)
322 : super(x,y), i(ai), erase(false)
323 { }
324 
326 {
327  super::operator=(super(p.x(),-p.y()));
328  i = -1;
329  return *this;
330 }
331 
332 CgalPoint::operator QPointF() const
333 {
334  return QPointF(x(),-y());
335 }
336 
337 
338 std::ostream& frechet::poly::operator<< (std::ostream& out, const frechet::poly::CgalPolygon& poly)
339 {
340  out << "[";
341  auto pbegin = poly.vertices_begin();
342  auto pend = poly.vertices_end();
343  for(auto p=pbegin; p != pend; ++p)
344  {
345  if (p != pbegin) out <<",";
346  out << p->i;
347  }
348  return out << "]";
349 }
350 
351 std::ostream& frechet::poly::operator<< (std::ostream& out, const frechet::poly::CgalPolygonList& polys)
352 {
353  out << "{";
354  auto pbegin = polys.begin();
355  auto pend = polys.end();
356  for(auto p=pbegin; p != pend; ++p)
357  {
358  if (p != pbegin) out << ", ";
359  out << *p;
360  }
361  return out << "}";
362 }
Represents a polygon line segment from node i to j.
Definition: types.h:39
CgalPolygon cgp
the polygon under examination
Definition: poly_utils.h:125
void complement()
after all faces have been added, create the complementary "outer" edges (connected to the south-pole)...
Greene's approximation algorithm.
Definition: poly_utils.h:133
static int distance(int a, int b, int n)
Definition: poly_utils.cpp:210
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
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
bool is_edge(int n) const
Definition: types.h:76
bool assertStrictlySorted(const CgalPolygon &)
debug assertion
Definition: poly_utils.cpp:146
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
Vertex_handle createVertex(const Point &p, int i)
create a new triangulation vertex
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
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Definition: types.h:14
static bool is_edge(int a, int b, int n)
Definition: poly_utils.cpp:216
void createFace(int a, int b, int c)
insert a new face. Caller is responsible for keeping the triangulation in a consistent state....
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
bool is_diagonal(int n) const
Definition: types.h:69
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....
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
static bool is_diagonal(int a, int b, int n)
Definition: poly_utils.cpp:221
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