← 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_grid_generator.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_grid_generator.h
17
17
//
18
18
// Author(s)     : Idit Haran   <haranidi@post.tau.ac.il>
19
19
//                 Ron Wein     <wein@post.tau.ac.il>
20
 
#ifndef CGAL_ARR_LM_GRID_GENERATOR_H
21
 
#define CGAL_ARR_LM_GRID_GENERATOR_H
 
20
 
 
21
#ifndef CGAL_ARR_LANDMARKS_GRID_GENERATOR_H
 
22
#define CGAL_ARR_LANDMARKS_GRID_GENERATOR_H
22
23
 
23
24
/*! \file
24
25
* Definition of the Arr_grid_landmarks_generator<Arrangement> template.
73
74
  typedef Arr_traits_basic_adaptor_2<Geometry_traits_2> Traits_adaptor_2;
74
75
 
75
76
  // Data members:
76
 
  const Traits_adaptor_2*  m_traits;
77
 
  unsigned int             num_landmarks;
78
 
  Pairs_set                lm_pairs;
79
 
 
80
 
  ANT                      x_min, y_min;    // Bounding box for the
81
 
  ANT                      x_max, y_max;    // arrangement vertices.
82
 
  ANT                      step_x, step_y;  // Grid step sizes.
83
 
  unsigned int             sqrt_n;
84
 
 
85
 
  bool            fixed_number_of_lm; // indicates if the constructor got
86
 
                                      // number of landmarks as parameter
 
77
  const Traits_adaptor_2* m_traits;
 
78
  unsigned int num_landmarks;
 
79
  Pairs_set lm_pairs;
 
80
 
 
81
  ANT x_min, y_min;    // Bounding box for the
 
82
  ANT x_max, y_max;    // arrangement vertices.
 
83
  ANT step_x, step_y;  // Grid step sizes.
 
84
  unsigned int sqrt_n;
 
85
 
 
86
  bool fixed_number_of_lm; // indicates if the constructor got
 
87
                           // number of landmarks as parameter
87
88
 
88
89
private:
89
90
  /*! Copy constructor - not supported. */
93
94
  Self& operator=(const Self&);
94
95
 
95
96
public:
96
 
  /*! Constructor. */
 
97
  /*! Constructor from an arrangement.
 
98
   * \param arr (in) The arrangement.
 
99
   */
97
100
  Arr_grid_landmarks_generator(const Arrangement_2& arr) :
98
101
    Base(arr),
 
102
    m_traits(static_cast<const Traits_adaptor_2*>(arr.geometry_traits())),
99
103
    num_landmarks(0),
100
104
    fixed_number_of_lm(false)
101
105
  {
102
 
    m_traits = static_cast<const Traits_adaptor_2*>(arr.geometry_traits());
103
106
    build_landmark_set();//this->
104
107
  }
105
108
 
106
109
  Arr_grid_landmarks_generator(const Arrangement_2& arr,
107
110
                               unsigned int n_landmarks) :
108
111
    Base(arr),
 
112
    m_traits(static_cast<const Traits_adaptor_2*>(arr.geometry_traits())),
109
113
    num_landmarks(n_landmarks),
110
114
    fixed_number_of_lm(true)
111
115
  {
112
 
    m_traits = static_cast<const Traits_adaptor_2*>(arr.geometry_traits());
113
116
    build_landmark_set();//this->
114
117
  }
115
118
 
116
 
  /*!
117
 
   * Create the landmarks set (choosing the landmarks),
 
119
  /*! Create the landmarks set (choosing the landmarks),
118
120
   * and store them in the nearest neighbor search structure.
119
121
   */
120
122
  virtual void build_landmark_set()
121
123
  {
122
124
    // Create a set of points on a grid.
123
 
    Points_set    points;
 
125
    Points_set points;
124
126
    _create_points_set(points);
125
127
    // Locate the landmarks in the arrangement using batched point-location
126
128
    // global function. Note that the resulting pairs are returned sorted by
131
133
    this->updated = true;
132
134
  }
133
135
 
134
 
  /*!
135
 
   * Clear the set of landmarks.
 
136
  /*! Clear the set of landmarks.
136
137
   */
137
138
  virtual void clear_landmark_set()
138
139
  {
140
141
    this->updated = false;
141
142
  }
142
143
 
143
 
  /*!
144
 
   * Get the nearest neighbor (landmark) to the given point.
 
144
  /*! Obtain the nearest neighbor (landmark) to the given point.
145
145
   * \param q The query point.
146
 
   * \param obj Output: The location of the nearest landmark point in the
147
 
   *                    arrangement (a vertex, halfedge, or face handle).
 
146
   * \param obj (out) The location of the nearest landmark point in the
 
147
   *                  arrangement (a vertex, halfedge, or face handle).
148
148
   * \return The nearest landmark point.
149
149
   */
150
150
  virtual Point_2 closest_landmark(const Point_2& q, PL_result_type& obj)
152
152
    CGAL_assertion(this->updated);
153
153
 
154
154
    // Calculate the index of the nearest grid point point to q.
155
 
    const ANT     qx = m_traits->approximate_2_object()(q, 0);
156
 
    const ANT     qy = m_traits->approximate_2_object()(q, 1);
157
 
    unsigned int  i, j;
158
 
    unsigned int  index;
159
 
 
160
 
    if (CGAL::compare(qx, x_min) == SMALLER)
161
 
      i = 0;
162
 
    else if (CGAL::compare(qx, x_max) == LARGER)
163
 
      i = sqrt_n - 1;
164
 
    else
165
 
      i = static_cast<int>(((qx - x_min) / step_x) + 0.5);
166
 
 
167
 
    if (CGAL::compare(qy, y_min) == SMALLER)
168
 
      j = 0;
169
 
    else if (CGAL::compare(qy, y_max) == LARGER)
170
 
      j = sqrt_n - 1;
171
 
    else
172
 
      j = static_cast<int>(((qy - y_min) / step_y) + 0.5);
173
 
 
174
 
    index = sqrt_n * i + j;
 
155
    typename Geometry_traits_2::Approximate_2 approximate =
 
156
      m_traits->approximate_2_object();
 
157
    const ANT qx = approximate(q, 0);
 
158
    const ANT qy = approximate(q, 1);
 
159
    unsigned int i = (CGAL::compare(qx, x_min) == SMALLER) ? 0 :
 
160
      (CGAL::compare(qx, x_max) == LARGER) ? (sqrt_n - 1) :
 
161
      static_cast<int>(((qx - x_min) / step_x) + 0.5);
 
162
    unsigned int j = (CGAL::compare(qy, y_min) == SMALLER) ? 0 :
 
163
      (CGAL::compare(qy, y_max) == LARGER) ? (sqrt_n - 1) :
 
164
      static_cast<int>(((qy - y_min) / step_y) + 0.5);
 
165
    unsigned int index = sqrt_n * i + j;
175
166
 
176
167
    // Return the result.
177
168
    obj = lm_pairs[index].second;
179
170
  }
180
171
 
181
172
protected:
182
 
  /*!
183
 
   * Create a set of landmark points on a grid.
 
173
  /*! Create a set of landmark points on a grid.
184
174
   */
185
175
  virtual void _create_points_set(Points_set& points)
186
176
  {
203
193
      return;
204
194
    }
205
195
 
206
 
    ANT                      x, y;
207
 
    Vertex_const_iterator    left, right, top, bottom;
 
196
    ANT x, y;
 
197
    Vertex_const_iterator left, right, top, bottom;
208
198
 
209
199
    left = right = top = bottom = vit;
210
200
 
211
 
    for (++vit; vit != arr->vertices_end(); ++vit)
212
 
    {
 
201
    for (++vit; vit != arr->vertices_end(); ++vit) {
213
202
      x = m_traits->approximate_2_object()(vit->point(), 0);
214
203
      y = m_traits->approximate_2_object()(vit->point(), 1);
215
204
 
216
 
      if (CGAL::compare(x, x_min) == SMALLER)
217
 
      {
 
205
      if (CGAL::compare(x, x_min) == SMALLER) {
218
206
        x_min = x;
219
207
        left = vit;
220
208
      }
221
 
      else if (CGAL::compare(x, x_max) == LARGER)
222
 
      {
 
209
      else if (CGAL::compare(x, x_max) == LARGER) {
223
210
        x_max = x;
224
211
        right = vit;
225
212
      }
226
213
 
227
 
      if (CGAL::compare(y, y_min) == SMALLER)
228
 
      {
 
214
      if (CGAL::compare(y, y_min) == SMALLER) {
229
215
        y_min = y;
230
216
        bottom = vit;
231
217
      }
232
 
      else if (CGAL::compare(y, y_max) == LARGER)
233
 
      {
 
218
      else if (CGAL::compare(y, y_max) == LARGER) {
234
219
        y_max = y;
235
220
        top = vit;
236
221
      }
249
234
    CGAL_assertion(sqrt_n > 1);
250
235
 
251
236
    // Calculate the step sizes for the grid.
252
 
    ANT    delta_x = m_traits->approximate_2_object()(right->point(), 0) -
253
 
                     m_traits->approximate_2_object()(left->point(), 0);
254
 
    ANT    delta_y = m_traits->approximate_2_object()(top->point(), 1) -
255
 
                     m_traits->approximate_2_object()(bottom->point(), 1);
256
 
 
257
 
    if (CGAL::sign(delta_x) == CGAL::ZERO)
258
 
      delta_x = delta_y;
259
 
 
260
 
    if (CGAL::sign(delta_y) == CGAL::ZERO)
261
 
      delta_y = delta_x;
262
 
 
 
237
    ANT delta_x = m_traits->approximate_2_object()(right->point(), 0) -
 
238
      m_traits->approximate_2_object()(left->point(), 0);
 
239
    ANT delta_y = m_traits->approximate_2_object()(top->point(), 1) -
 
240
      m_traits->approximate_2_object()(bottom->point(), 1);
 
241
 
 
242
    if (CGAL::sign(delta_x) == CGAL::ZERO) delta_x = delta_y;
 
243
    if (CGAL::sign(delta_y) == CGAL::ZERO) delta_y = delta_x;
263
244
    CGAL_assertion((CGAL::sign(delta_x) == CGAL::POSITIVE) &&
264
245
                   (CGAL::sign(delta_y) == CGAL::POSITIVE));
265
 
 
266
246
    step_x = delta_x / (sqrt_n - 1);
267
247
    step_y = delta_y / (sqrt_n - 1);
268
248