1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
|
// Copyright (c) 2000 Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.2-branch/Partition_2/include/CGAL/partition_is_valid_2.h $
// $Id: partition_is_valid_2.h 28567 2006-02-16 14:30:13Z lsaboret $
//
//
// Author(s) : Susan Hert <hert@mpi-sb.mpg.de>
#ifndef CGAL_PARTITION_IS_VALID_2_H
#define CGAL_PARTITION_IS_VALID_2_H
#include <list>
#include <utility>
#include <iterator>
#include <CGAL/partition_assertions.h>
#include <CGAL/Partitioned_polygon_2.h>
#include <CGAL/Partition_vertex_map.h>
#include <CGAL/ch_selected_extreme_points_2.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/Partition_is_valid_traits_2.h>
#include <CGAL/Polygon_2.h>
// NOTE: this could possibly be checked using a planar map overlay, but
// then the traits class would have to require lots of other things
// and you have to do many overlaps, not just one so it is
// less efficient.
namespace CGAL {
template <class Circulator1, class Circulator2>
bool
polygons_w_steiner_are_equal(Circulator1 orig_first, Circulator2 new_first)
{
typedef typename Circulator1::value_type Point_2;
Circulator1 orig_circ;
Circulator2 new_circ;
// find the first (original) vertex in the list of vertices
for (new_circ = new_first;
*new_circ != *orig_first && ++new_circ != new_first;)
{}
if (new_circ == new_first)
{
#ifdef CGAL_PARTITION_CHECK_DEBUG
std::cout << "first vertex " << *orig_first << " not found "
<< std::endl;
#endif // CGAL_PARTITION_CHECK_DEBUG
return false;
}
// first becomes the first one you found; now look for the others
new_first = new_circ;
orig_circ = orig_first;
Point_2 prev_pt = *new_first;
// keep going until you find all the original vertices, or come back
// to the first new vertex
do
{
if (*new_circ == *orig_circ) // points correspond, so move both
{
prev_pt = *new_circ;
new_circ++;
orig_circ++;
}
else // points don't correspond
{
typedef typename Kernel_traits<Point_2>::Kernel K;
typename K::Collinear_2 collinear;
typename K::Collinear_are_ordered_along_line_2 collinear_are_ordered_along_line;
if (!collinear(prev_pt, *new_circ, *orig_circ))
{
#ifdef CGAL_PARTITION_CHECK_DEBUG
std::cout << *new_circ << " is not collinear with " << prev_pt
<< " and " << *orig_circ << std::endl;
#endif
return false;
}
if (!collinear_are_ordered_along_line(prev_pt, *new_circ, *orig_circ))
{
#ifdef CGAL_PARTITION_CHECK_DEBUG
std::cout << *new_circ << " doesn't belong betweene " << prev_pt
<< " and " << *orig_circ << std::endl;
#endif
return false;
}
prev_pt = *new_circ;
new_circ++;
}
}
while (orig_circ != orig_first && new_circ != new_first);
// if they didn't both come back to the beginning, then something is wrong
return (orig_circ == orig_first && new_circ == new_first);
}
template <class Circulator1, class Circulator2>
bool
polygons_are_equal(Circulator1 orig_first, Circulator2 new_first)
{
Circulator1 orig_circ = orig_first;
Circulator2 new_circ;
// find the first (original) vertex in the list of vertices
for (new_circ = new_first;
*new_circ != *orig_first && ++new_circ != new_first;)
{}
new_first = new_circ;
// now look through both lists until you find a vertex that is not
// the same or you reach the end of the vertices
do
{
#ifdef CGAL_PARTITION_CHECK_DEBUG
std::cout << *new_first << " is in the right place " << std::endl;
#endif
orig_circ++; new_circ++;
}
while (*orig_circ == *new_circ &&
orig_circ != orig_first && new_circ != new_first);
return (orig_circ == orig_first && new_circ == new_first);
}
template<class InputIterator, class ForwardIterator, class Traits>
bool
partition_is_valid_2 (InputIterator point_first, InputIterator point_last,
ForwardIterator poly_first, ForwardIterator poly_last,
const Traits& traits)
{
if (poly_first == poly_last) return (point_first == point_last);
typedef typename Traits::Polygon_2::Vertex_iterator
Poly_vtx_iterator;
typedef typename Traits::Point_2 Point_2;
typedef Partition_vertex_map<Traits> P_Vertex_map;
typedef typename Traits::Is_valid Is_valid;
Poly_vtx_iterator vtx_begin, vtx_end;
Is_valid is_valid = traits.is_valid_object(traits);
std::list<Point_2> orig_poly;
for (;point_first != point_last; point_first++)
orig_poly.push_back(*point_first);
CGAL_partition_precondition(orientation_2(orig_poly.begin(),orig_poly.end(),
traits) == COUNTERCLOCKWISE);
P_Vertex_map output_vertex_set(poly_first, poly_last);
if (output_vertex_set.polygons_overlap()) return false;
int poly_num = 0;
for (; poly_first != poly_last; poly_first++, poly_num++)
{
vtx_begin = (*poly_first).vertices_begin();
vtx_end = (*poly_first).vertices_end();
#ifdef CGAL_PARTITION_CHECK_DEBUG
std::cout << "Polygon " << poly_num << " is " << std::endl;
std::cout << *poly_first << std::endl;
#endif
CGAL_partition_assertion (
orientation_2(vtx_begin, vtx_end, traits) == COUNTERCLOCKWISE);
if (!is_valid(vtx_begin, vtx_end))
{
#ifdef CGAL_PARTITION_CHECK_DEBUG
std::cout << "It does NOT have the tested property." << std::endl;
#endif
return false;
}
}
std::list<Point_2> union_polygon;
output_vertex_set.union_vertices(std::back_inserter(union_polygon));
#ifdef CGAL_PARTITION_CHECK_DEBUG
typename std::list<Point_2>::iterator poly_iterator;
std::cout << "union polygon is " << std::endl;
for (poly_iterator = union_polygon.begin();
poly_iterator != union_polygon.end(); poly_iterator++)
{
std::cout << *poly_iterator << " ";
}
std::cout << std::endl;
#endif // CGAL_PARTITION_CHECK_DEBUG
typedef typename std::list<Point_2>::iterator I;
typedef Circulator_from_iterator<I> Circulator;
Circulator orig_poly_circ(orig_poly.begin(), orig_poly.end());
Circulator union_poly_circ(union_polygon.begin(), union_polygon.end());
if (orig_poly.size() == union_polygon.size())
return polygons_are_equal(orig_poly_circ, union_poly_circ);
else
return polygons_w_steiner_are_equal(orig_poly_circ, union_poly_circ);
}
template<class InputIterator, class FowardIterator>
bool
partition_is_valid_2 (InputIterator point_first, InputIterator point_last,
FowardIterator poly_first, FowardIterator poly_last)
{
typedef typename std::iterator_traits<InputIterator>::value_type Point_2;
typedef typename Kernel_traits<Point_2>::Kernel K;
typedef Partition_traits_2<K> Traits;
typedef Is_vacuously_valid<Traits> Is_valid;
Partition_is_valid_traits_2<Traits, Is_valid> validity_traits;
return partition_is_valid_2(point_first, point_last,
poly_first, poly_last, validity_traits);
}
template<class InputIterator, class ForwardIterator, class Traits>
bool
convex_partition_is_valid_2(InputIterator point_first,
InputIterator point_last,
ForwardIterator poly_first,
ForwardIterator poly_last,
const Traits& )
{
typedef typename Traits::Is_convex_2 Is_convex_2;
Partition_is_valid_traits_2<Traits, Is_convex_2> validity_traits;
return partition_is_valid_2(point_first, point_last, poly_first, poly_last,
validity_traits);
}
template<class InputIterator, class ForwardIterator>
bool
convex_partition_is_valid_2(InputIterator point_first,
InputIterator point_last,
ForwardIterator poly_first,
ForwardIterator poly_last)
{
typedef typename std::iterator_traits<InputIterator>::value_type Point_2;
typedef typename Kernel_traits<Point_2>::Kernel K;
return convex_partition_is_valid_2(point_first, point_last,
poly_first, poly_last,
Partition_traits_2<K>());
}
template<class InputIterator, class ForwardIterator, class Traits>
bool
y_monotone_partition_is_valid_2(InputIterator point_first,
InputIterator point_last,
ForwardIterator poly_first,
ForwardIterator poly_last,
const Traits& )
{
typedef typename Traits::Is_y_monotone_2 Is_y_monotone_2;
Partition_is_valid_traits_2<Traits, Is_y_monotone_2> validity_traits;
return partition_is_valid_2(point_first, point_last, poly_first, poly_last,
validity_traits);
}
template<class InputIterator, class ForwardIterator>
bool
y_monotone_partition_is_valid_2(InputIterator point_first,
InputIterator point_last,
ForwardIterator poly_first,
ForwardIterator poly_last)
{
typedef typename std::iterator_traits<InputIterator>::value_type Point_2;
typedef typename Kernel_traits<Point_2>::Kernel K;
return y_monotone_partition_is_valid_2(point_first, point_last,
poly_first, poly_last,
Partition_traits_2<K>());
}
}
#endif // CGAL_PARTITION_IS_VALID_2_H
|
