PGROUTING  2.6-dev
alpha_driver.h File Reference
#include <stddef.h>
Include dependency graph for alpha_driver.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  vertex
 

Typedefs

typedef struct vertex vertex_t
 

Functions

int alpha_shape (vertex_t *vertices, size_t count, double alpha, vertex_t **res, size_t *res_count, char **err_msg)
 

Typedef Documentation

typedef struct vertex vertex_t

Function Documentation

int alpha_shape ( vertex_t vertices,
size_t  count,
double  alpha,
vertex_t **  res,
size_t *  res_count,
char **  err_msg 
)

Definition at line 174 of file alpha_driver.cpp.

References alpha_edges(), find_next_edge(), pgr_alloc(), pgr_free(), pgr_msg(), and AssertFailedException::what().

Referenced by compute_alpha_shape().

175  {
176  std::ostringstream err;
177 
178  try {
179  std::list<Point> points;
180  {
181  std::vector<Point> pv;
182 
183  for (std::size_t j = 0; j < count; ++j) {
184  Point p(vertices[j].x, vertices[j].y);
185  pv.push_back(p);
186  }
187 
188  std::sort(pv.begin(), pv.end(),
189  [](const Point &e1, const Point &e2)->bool {
190  return e2.y() < e1.y();
191  });
192  std::stable_sort(pv.begin(), pv.end(),
193  [](const Point &e1, const Point &e2)->bool {
194  return e2.x() < e1.x();
195  });
196  pv.erase(std::unique(pv.begin(), pv.end()), pv.end());
197  if (pv.size() != count && pv.size() < 3) {
198  err << "After eliminating duplicated points,"
199  " less than 3 points remain!!."
200  " Alpha shape calculation needs at least 3 vertices.";
201  *err_msg = pgr_msg(err.str().c_str());
202  return -1;
203  }
204  points.insert(points.begin(), pv.begin(), pv.end());
205  }
206 
207  Alpha_shape_2 A(points.begin(), points.end(),
208  coord_type(10000),
209  Alpha_shape_2::REGULARIZED);
210 
211  std::vector<Segment> segments;
212  // std::vector<Segment> result;
213 
214  // Alpha_shape_2::Alpha_shape_vertices_iterator vit;
215  // Alpha_shape_2::Vertex_handle vertex;
216  // Alpha_shape_2::Alpha_shape_edges_iterator eit;
217  // Alpha_shape_2::Edge edge;
218  // Alpha_shape_2::Face_iterator fit;
219  // Alpha_shape_2::Face_handle face;
220 
221  if (alpha <= 0.0) {
222  alpha = *A.find_optimal_alpha(1);
223  }
224  A.set_alpha(alpha);
225 
226  alpha_edges(A, std::back_inserter(segments));
227 
228  // Segment s = segments.at(0);
229  // find_next_edge(s, segments, result);
230  if (segments.empty()) {
231  *return_tuples = NULL;
232  *res_count = 0;
233  } else {
234  std::set<int> unusedIndexes;
235  for (unsigned int i = 0; i < segments.size(); i++) {
236  unusedIndexes.insert(i);
237  }
238 
239  std::vector<Polygon_2> rings;
240  Polygon_2 ring;
241  ring.push_back(segments.at(0).source());
242  rings.push_back(ring);
243  unusedIndexes.erase(0);
244  find_next_edge(segments.at(0), segments, unusedIndexes, rings);
245 
246  size_t result_count = 0;
247  for (unsigned int i = 0; i < rings.size(); i++) {
248  Polygon_2 ring = rings.at(i);
249  result_count += ring.size();
250  }
251  result_count += rings.size() - 1;
252  *return_tuples = pgr_alloc(result_count, (*return_tuples));
253  *res_count = result_count;
254 
255  int idx = 0;
256  for (unsigned int i = 0; i < rings.size(); i++) {
257  if (i > 0) {
258  (*return_tuples)[idx].x = DBL_MAX;
259  (*return_tuples)[idx].y = DBL_MAX;
260  idx++;
261  }
262  Polygon_2 ring = rings.at(i);
263  for (unsigned int j = 0; j < ring.size(); j++) {
264  Point point = ring.vertex(j);
265  (*return_tuples)[idx].x = point.x();
266  (*return_tuples)[idx].y = point.y();
267  idx++;
268  }
269  }
270  }
271  *err_msg = NULL;
272 
273  return EXIT_SUCCESS;
274  } catch (AssertFailedException &except) {
275  (*return_tuples) = pgr_free(*return_tuples);
276  (*res_count) = 0;
277  err << except.what();
278  *err_msg = pgr_msg(err.str().c_str());
279  } catch (std::exception &except) {
280  (*return_tuples) = pgr_free(*return_tuples);
281  (*res_count) = 0;
282  err << except.what();
283  *err_msg = pgr_msg(err.str().c_str());
284  } catch(...) {
285  (*return_tuples) = pgr_free(*return_tuples);
286  (*res_count) = 0;
287  err << "Caught unknown exception!";
288  *err_msg = pgr_msg(err.str().c_str());
289  }
290  return -1;
291 }
K::Point_2 Point
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:126
void alpha_edges(const Alpha_shape_2 &A, OutputIterator out)
T * pgr_free(T *ptr)
Definition: pgr_alloc.hpp:77
CGAL::Alpha_shape_2< Ht > Alpha_shape_2
double coord_type
CGAL::Polygon_2< K > Polygon_2
char * pgr_msg(const std::string &msg)
Definition: pgr_alloc.cpp:30
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:66
virtual const char * what() const
Definition: pgr_assert.cpp:53
void find_next_edge(Segment s, std::vector< Segment > &segments, std::set< int > &unusedIndexes, std::vector< Polygon_2 > &rings)

Here is the call graph for this function:

Here is the caller graph for this function: