← Back to branch summary

~ubuntu-branches/debian/stretch/cgal/stretch

« back to all changes in this revision

Viewing changes to include/CGAL/Arr_point_location/Arr_lm_generator_base.h

  • Committer: Package Import Robot
  • Author(s): Joachim Reichel
  • Date: 2014-04-05 10:56:43 UTC
  • mfrom: (1.2.4)
  • Revision ID: package-import@ubuntu.com-20140405105643-jgnrpu2thtx23zfs
Tags: 4.4-1
* New upstream release.
* Remove patches do-not-link-example-with-qt4-support-library.patch and
  fix_jet_fitting_3.patch (applied upstream).

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/CGAL/Arr_point_location/Arr_lm_generator_base.h
18
18
// Author(s)     : Idit Haran   <haranidi@post.tau.ac.il>
19
19
//                 Ron Wein     <wein@post.tau.ac.il>
20
20
 
21
 
#ifndef CGAL_ARR_LANDMARKS_GENERATOR_H
22
 
#define CGAL_ARR_LANDMARKS_GENERATOR_H
 
21
#ifndef CGAL_ARR_LANDMARKS_GENERATOR_BASE_H
 
22
#define CGAL_ARR_LANDMARKS_GENERATOR_BASE_H
23
23
 
24
24
/*! \file
25
25
* Definition of the Arr_landmarks_generator_base<Arrangement> template.
87
87
  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2> Traits_adaptor_2;
88
88
 
89
89
  // Data members:
90
 
  const Traits_adaptor_2  *m_traits;  // The associated traits object.
91
 
  Nearest_neighbor         nn;      // The associated nearest neighbor object.
92
 
  bool                     ignore_notifications;
93
 
  bool                     updated;
94
 
  int                      num_small_not_updated_changes;
 
90
  const Traits_adaptor_2* m_traits;  // The associated traits object.
 
91
  Nearest_neighbor nn;      // The associated nearest neighbor object.
 
92
  bool m_ignore_notifications;
 
93
  bool m_ignore_remove_edge;
 
94
  bool updated;
 
95
  int num_small_not_updated_changes;
95
96
 
96
97
  template<typename T>
97
98
  PL_result_type pl_make_result(T t) { return PL_result::make_result(t); }
98
 
  inline PL_result_type pl_default_result() { return PL_result::default_result(); }
 
99
  inline PL_result_type pl_default_result()
 
100
  { return PL_result::default_result(); }
99
101
 
100
102
public:
101
103
  bool is_empty() const { return nn.is_empty(); }
102
104
 
103
105
private:
104
106
  /*! Copy constructor - not supported. */
105
 
  Arr_landmarks_generator_base (const Self& );
 
107
  Arr_landmarks_generator_base(const Self&);
106
108
 
107
109
  /*! Assignment operator - not supported. */
108
 
  Self& operator= (const Self& );
 
110
  Self& operator=(const Self& );
109
111
 
110
112
public:
111
 
  /*! Constructor. */
112
 
  Arr_landmarks_generator_base (const Arrangement_2& arr) :
 
113
  /*! Constructor from an arrangement.
 
114
   * \param arr (in) The arrangement.
 
115
   */
 
116
  Arr_landmarks_generator_base(const Arrangement_2& arr) :
113
117
    Arr_observer<Arrangement_2> (const_cast<Arrangement_2 &>(arr)),
114
 
    ignore_notifications (false),
115
 
    updated (false),
 
118
    m_traits(static_cast<const Traits_adaptor_2*>(arr.geometry_traits())),
 
119
    m_ignore_notifications(false),
 
120
    m_ignore_remove_edge(false),
 
121
    updated(false),
116
122
    num_small_not_updated_changes(0)
117
123
  {
118
 
    m_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());
119
124
    // One needs to call build_landmark_set() in the constructor of any
120
125
    // inherited class.
121
126
  }
122
127
 
123
 
  /*!
124
 
   * Creates the landmarks set (choosing the landmarks) ,
 
128
  /*! Create the landmarks set (choosing the landmarks) ,
125
129
   * and saving them in the nearest-neighbor search structure.
126
130
   */
127
 
  virtual void build_landmark_set ()
 
131
  virtual void build_landmark_set()
128
132
  {
129
133
    // Create the landmark points.
130
 
    NN_Points_set     nn_points;
131
 
 
 
134
    NN_Points_set nn_points;
132
135
    _create_nn_points_set(nn_points);
133
136
 
134
137
    // Update the search structure.
135
138
    nn.clear();
136
 
    nn.init (nn_points.begin(), nn_points.end());
 
139
    nn.init(nn_points.begin(), nn_points.end());
137
140
 
138
141
    num_small_not_updated_changes = 0;
139
142
    updated = true;
140
143
  }
141
144
 
142
 
  /*!
143
 
   * clear the set of landmarks.
 
145
  /*! clear the set of landmarks.
144
146
   */
145
 
  virtual void clear_landmark_set ()
 
147
  virtual void clear_landmark_set()
146
148
  {
147
149
    nn.clear();
148
150
    num_small_not_updated_changes = 0;
149
151
    updated = false;
150
152
  }
151
153
 
152
 
  /*!
153
 
   * Get the nearest neighbor (landmark) to the given point.
 
154
  /*! Obtain the nearest neighbor (landmark) to the given point.
154
155
   * \param p The query point.
155
156
   * \param obj Output: The location of the nearest landmark point in the
156
157
   *                    arrangement (a vertex, halfedge, or face handle).
170
171
   * arrangement.
171
172
   * \param arr The arrangement to be copied.
172
173
   */
173
 
  virtual void before_assign (const Arrangement_2& arr)
 
174
  virtual void before_assign(const Arrangement_2& arr)
174
175
  {
175
176
    this->clear_landmark_set();
176
 
    m_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());
177
 
    ignore_notifications = true;
 
177
    m_traits = static_cast<const Traits_adaptor_2*>(arr.geometry_traits());
 
178
    m_ignore_notifications = true;
178
179
  }
179
180
 
180
 
  /*!
181
 
   * Notification after the arrangement has been assigned with another
 
181
  /*! Notification after the arrangement has been assigned with another
182
182
   * arrangement.
183
183
   */
184
 
  virtual void after_assign ()
 
184
  virtual void after_assign()
185
185
  {
186
186
    this->build_landmark_set();
187
 
    ignore_notifications = false;
 
187
    m_ignore_notifications = false;
188
188
  }
189
189
 
190
 
  /*!
191
 
   * Notification before the observer is attached to an arrangement.
 
190
  /*! Notification before the observer is attached to an arrangement.
192
191
   * \param arr The arrangement we are about to attach the observer to.
193
192
   */
194
 
  virtual void before_attach (const Arrangement_2& arr)
 
193
  virtual void before_attach(const Arrangement_2& arr)
195
194
  {
196
195
    this->clear_landmark_set();
197
 
    m_traits = static_cast<const Traits_adaptor_2*> (arr.geometry_traits());
198
 
    ignore_notifications = true;
 
196
    m_traits = static_cast<const Traits_adaptor_2*>(arr.geometry_traits());
 
197
    m_ignore_notifications = true;
199
198
  }
200
199
 
201
 
  /*!
202
 
   * Notification after the observer has been attached to an arrangement.
 
200
  /*! Notification after the observer has been attached to an arrangement.
203
201
   */
204
 
  virtual void after_attach ()
 
202
  virtual void after_attach()
205
203
  {
206
204
    this->build_landmark_set();
207
 
    ignore_notifications = false;
 
205
    m_ignore_notifications = false;
208
206
  }
209
207
 
210
 
  /*!
211
 
   * Notification before the observer is detached from the arrangement.
 
208
  /*! Notification before the observer is detached from the arrangement.
212
209
   */
213
 
  virtual void before_detach ()
214
 
  {
215
 
    this->clear_landmark_set();
216
 
  }
 
210
  virtual void before_detach()
 
211
  { this->clear_landmark_set(); }
217
212
 
218
 
  /*!
219
 
   * Notification after the arrangement is cleared.
 
213
  /*! Notification after the arrangement is cleared.
220
214
   * \param u A handle to the unbounded face.
221
215
   */
222
 
  virtual void after_clear ()
223
 
  {
224
 
    this->clear_landmark_set();
225
 
    this->build_landmark_set();
226
 
  }
227
 
 
228
 
  /*! Notification before a global operation modifies the arrangement. */
229
 
  virtual void before_global_change ()
230
 
  {
231
 
    this->clear_landmark_set();
232
 
    ignore_notifications = true;
233
 
  }
234
 
 
235
 
  /*! Notification after a global operation is completed. */
236
 
  virtual void after_global_change ()
237
 
  {
238
 
    this->build_landmark_set();
239
 
    ignore_notifications = false;
 
216
  virtual void after_clear()
 
217
  {
 
218
    this->clear_landmark_set();
 
219
    this->build_landmark_set();
 
220
  }
 
221
 
 
222
  /*! Notification before a global operation modifies the arrangement.
 
223
   */
 
224
  virtual void before_global_change()
 
225
  {
 
226
    this->clear_landmark_set();
 
227
    m_ignore_notifications = true;
 
228
  }
 
229
 
 
230
  /*! Notification after a global operation is completed.
 
231
   */
 
232
  virtual void after_global_change()
 
233
  {
 
234
    this->build_landmark_set();
 
235
    m_ignore_notifications = false;
240
236
  }
241
237
  //@}
242
238
 
243
239
  /// \name Overloaded observer functions on local changes.
244
240
  //@{
245
241
 
 
242
  /*! Notification before the removal of an edge.
 
243
   * \param e (in) A handle to one of the twin halfedges to be removed.
 
244
   */
 
245
  virtual void before_remove_edge(Halfedge_handle /* e */)
 
246
  { m_ignore_remove_edge = true; }
 
247
 
246
248
  /*! Notification after the creation of a new vertex. */
247
 
  virtual void after_create_vertex (Vertex_handle )
 
249
  virtual void after_create_vertex(Vertex_handle)
248
250
  {
249
 
    this->_handle_local_change_notification();
 
251
    if (! m_ignore_notifications) {
 
252
      clear_landmark_set();
 
253
      build_landmark_set();
 
254
    }
250
255
  }
251
256
 
252
257
  /*! Notification after the creation of a new edge. */
253
 
  virtual void after_create_edge (Halfedge_handle )
254
 
  { this->_handle_local_change_notification(); }
 
258
  virtual void after_create_edge(Halfedge_handle)
 
259
  {
 
260
    if (! m_ignore_notifications) {
 
261
      clear_landmark_set();
 
262
      build_landmark_set();
 
263
    }
 
264
  }
255
265
 
256
266
  /*! Notification after an edge was split. */
257
267
  virtual void after_split_edge(Halfedge_handle, Halfedge_handle)
258
 
  { this->_handle_local_change_notification(); }
 
268
  {
 
269
    if (! m_ignore_notifications) {
 
270
      clear_landmark_set();
 
271
      build_landmark_set();
 
272
    }
 
273
  }
259
274
 
260
275
  /*! Notification after a face was split. */
261
276
  virtual void after_split_face(Face_handle, Face_handle, bool)
262
 
  { this->_handle_local_change_notification(); }
 
277
  {
 
278
    if (! m_ignore_notifications) {
 
279
      clear_landmark_set();
 
280
      build_landmark_set();
 
281
    }
 
282
  }
263
283
 
264
284
  /*! Notification after an outer CCB was split.*/
265
 
  virtual void after_split_outer_ccb (Face_handle ,
266
 
                                      Ccb_halfedge_circulator ,
267
 
                                      Ccb_halfedge_circulator )
268
 
  { this->_handle_local_change_notification(); }
 
285
  virtual void after_split_outer_ccb(Face_handle,
 
286
                                     Ccb_halfedge_circulator,
 
287
                                     Ccb_halfedge_circulator)
 
288
  {
 
289
    if (! m_ignore_notifications) {
 
290
      clear_landmark_set();
 
291
      build_landmark_set();
 
292
    }
 
293
  }
269
294
 
270
295
  /*! Notification after an inner CCB was split. */
271
 
  virtual void after_split_inner_ccb (Face_handle ,
272
 
                                      Ccb_halfedge_circulator ,
273
 
                                      Ccb_halfedge_circulator )
274
 
  { this->_handle_local_change_notification(); }
 
296
  virtual void after_split_inner_ccb(Face_handle,
 
297
                                     Ccb_halfedge_circulator,
 
298
                                     Ccb_halfedge_circulator)
 
299
  {
 
300
    if (! m_ignore_notifications) {
 
301
      clear_landmark_set();
 
302
      build_landmark_set();
 
303
    }
 
304
  }
275
305
 
276
306
  /*! Notification after an outer CCB was added to a face. */
277
 
  virtual void after_add_outer_ccb (Ccb_halfedge_circulator )
 
307
  virtual void after_add_outer_ccb(Ccb_halfedge_circulator)
278
308
  {
279
 
    this->_handle_local_change_notification();
 
309
    if (! m_ignore_notifications) {
 
310
      clear_landmark_set();
 
311
      build_landmark_set();
 
312
    }
280
313
  }
281
314
 
282
315
  /*! Notification after an inner CCB was created inside a face. */
283
 
  virtual void after_add_inner_ccb (Ccb_halfedge_circulator )
284
 
  { this->_handle_local_change_notification(); }
 
316
  virtual void after_add_inner_ccb(Ccb_halfedge_circulator)
 
317
  {
 
318
    if (! m_ignore_notifications) {
 
319
      clear_landmark_set();
 
320
      build_landmark_set();
 
321
    }
 
322
  }
285
323
 
286
324
  /*! Notification after an isolated vertex was created inside a face. */
287
 
  virtual void after_add_isolated_vertex (Vertex_handle )
288
 
  { this->_handle_local_change_notification(); }
 
325
  virtual void after_add_isolated_vertex(Vertex_handle)
 
326
  {
 
327
    if (! m_ignore_notifications) {
 
328
      clear_landmark_set();
 
329
      build_landmark_set();
 
330
    }
 
331
  }
289
332
 
290
333
  /*! Notification after an edge was merged. */
291
 
  virtual void after_merge_edge (Halfedge_handle )
292
 
  { this->_handle_local_change_notification(); }
 
334
  virtual void after_merge_edge(Halfedge_handle)
 
335
  {
 
336
    if (! m_ignore_notifications) {
 
337
      clear_landmark_set();
 
338
      build_landmark_set();
 
339
    }
 
340
  }
293
341
 
294
342
  /*! Notification after a face was merged. */
295
 
  virtual void after_merge_face (Face_handle )
296
 
  { this->_handle_local_change_notification(); }
 
343
  virtual void after_merge_face(Face_handle)
 
344
  {
 
345
    if (! m_ignore_notifications && ! m_ignore_remove_edge) {
 
346
      clear_landmark_set();
 
347
      build_landmark_set();
 
348
    }
 
349
  }
297
350
 
298
351
  /*! Notification after an outer CCB was merged. */
299
352
  virtual void after_merge_outer_ccb(Face_handle, Ccb_halfedge_circulator)
300
 
  { this->_handle_local_change_notification(); }
 
353
  {
 
354
    if (! m_ignore_notifications) {
 
355
      clear_landmark_set();
 
356
      build_landmark_set();
 
357
    }
 
358
  }
301
359
 
302
360
  /*! Notification after an inner CCB was merged. */
303
361
  virtual void after_merge_inner_ccb(Face_handle, Ccb_halfedge_circulator)
304
 
  { this->_handle_local_change_notification(); }
 
362
  {
 
363
    if (! m_ignore_notifications) {
 
364
      clear_landmark_set();
 
365
      build_landmark_set();
 
366
    }
 
367
  }
305
368
 
306
369
  /*! Notification after an outer CCB is moved from one face to another. */
307
 
  virtual void after_move_outer_ccb (Ccb_halfedge_circulator )
308
 
  { this->_handle_local_change_notification(); }
 
370
  virtual void after_move_outer_ccb(Ccb_halfedge_circulator )
 
371
  {
 
372
    if (! m_ignore_notifications) {
 
373
      clear_landmark_set();
 
374
      build_landmark_set();
 
375
    }
 
376
  }
309
377
 
310
378
  /*! Notification after an inner CCB is moved from one face to another. */
311
 
  virtual void after_move_inner_ccb (Ccb_halfedge_circulator )
312
 
  { this->_handle_local_change_notification(); }
 
379
  virtual void after_move_inner_ccb(Ccb_halfedge_circulator )
 
380
  {
 
381
    if (! m_ignore_notifications) {
 
382
      clear_landmark_set();
 
383
      build_landmark_set();
 
384
    }
 
385
  }
313
386
 
314
387
  /*! Notification after an isolated vertex is moved. */
315
 
  virtual void after_move_isolated_vertex (Vertex_handle )
316
 
  { this->_handle_local_change_notification(); }
 
388
  virtual void after_move_isolated_vertex(Vertex_handle )
 
389
  {
 
390
    if (! m_ignore_notifications) {
 
391
      clear_landmark_set();
 
392
      build_landmark_set();
 
393
    }
 
394
  }
317
395
 
318
396
  /*! Notificaion after the removal of a vertex. */
319
 
  virtual void after_remove_vertex ()
320
 
  { this->_handle_local_change_notification(); }
 
397
  virtual void after_remove_vertex()
 
398
  {
 
399
    if (! m_ignore_notifications && ! m_ignore_remove_edge) {
 
400
      clear_landmark_set();
 
401
      build_landmark_set();
 
402
    }
 
403
  }
321
404
 
322
405
  /*! Notification after the removal of an edge. */
323
 
  virtual void after_remove_edge ()
324
 
  { this->_handle_local_change_notification(); }
 
406
  virtual void after_remove_edge()
 
407
  {
 
408
    if (! m_ignore_notifications) {
 
409
      clear_landmark_set();
 
410
      build_landmark_set();
 
411
    }
 
412
    m_ignore_remove_edge = false;
 
413
  }
325
414
 
326
415
  /*! Notificaion after the removal of an outer CCB. */
327
 
  virtual void after_remove_outer_ccb (Face_handle )
328
 
  { this->_handle_local_change_notification(); }
 
416
  virtual void after_remove_outer_ccb(Face_handle)
 
417
  {
 
418
    if (! m_ignore_notifications && ! m_ignore_remove_edge) {
 
419
      clear_landmark_set();
 
420
      build_landmark_set();
 
421
    }
 
422
  }
329
423
 
330
424
  /*! Notificaion after the removal of an inner CCB. */
331
 
  virtual void after_remove_inner_ccb (Face_handle )
332
 
  { this->_handle_local_change_notification(); }
333
 
  //@}
334
 
 
335
 
protected:
336
 
  /*! Handle a change notification. */
337
 
  void _handle_local_change_notification ()
 
425
  virtual void after_remove_inner_ccb(Face_handle)
338
426
  {
339
 
    if (! ignore_notifications) {
 
427
    if (! m_ignore_notifications && ! m_ignore_remove_edge) {
340
428
      clear_landmark_set();
341
429
      build_landmark_set();
342
430
    }
343
431
  }
 
432
  //@}
344
433
 
345
 
  /*!
346
 
   * This function creates the list of landmarks with their location.
 
434
protected:
 
435
  /*! Create the list of landmarks with their location.
347
436
   * This is a pure virtual function, and the class that inherites from
348
437
   * this generator must implement it.
349
438
   */
350
 
  virtual void _create_points_set (Points_set &) = 0;
 
439
  virtual void _create_points_set(Points_set&) = 0;
351
440
 
352
 
  virtual void _create_nn_points_set (NN_Points_set &nn_points)
 
441
  virtual void _create_nn_points_set(NN_Points_set& nn_points)
353
442
  {
354
 
    Points_set           points;
355
 
    Pairs_set            pairs;
 
443
    Points_set points;
 
444
    Pairs_set pairs;
356
445
 
357
446
    // Create the set of landmark points.
358
447
    _create_points_set(points);
359
448
 
360
449
    // Locate the landmarks in the arrangement using batched point-location
361
450
    // global function.
362
 
    locate (*(this->arrangement()), points.begin(), points.end(),
363
 
            std::back_inserter(pairs));
 
451
    locate(*(this->arrangement()), points.begin(), points.end(),
 
452
           std::back_inserter(pairs));
364
453
 
365
454
    // Apply a random shuffle on the points, since the batched point-location
366
455
    // returns them sorted.
367
 
    std::random_shuffle (pairs.begin(), pairs.end());
 
456
    std::random_shuffle(pairs.begin(), pairs.end());
368
457
 
369
458
    // Insert all landmarks (paired with their current location in the
370
459
    // arrangement) into the nearest-neighbor search structure.
371
 
    Pairs_iterator   itr;
372
 
 
 
460
    Pairs_iterator itr;
373
461
    for (itr = pairs.begin(); itr != pairs.end(); ++itr) {
374
 
      NN_Point_2  np(itr->first, itr->second);
 
462
      NN_Point_2 np(itr->first, itr->second);
375
463
      nn_points.push_back(np);
376
464
    }
377
465
  }