PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 171 of file alpha_driver.cpp.

References alpha_edges(), find_next_edge(), and pgr_alloc().

Referenced by compute_alpha_shape().

172  {
173  try {
174  std::list<Point> points;
175  {
176  std::vector<Point> pv;
177 
178  for (std::size_t j = 0; j < count; ++j) {
179  Point p(vertices[j].x, vertices[j].y);
180  pv.push_back(p);
181  }
182 
183  std::sort(pv.begin(), pv.end(),
184  [](const Point &e1, const Point &e2)->bool {
185  return e2.y() < e1.y();
186  });
187  std::stable_sort(pv.begin(), pv.end(),
188  [](const Point &e1, const Point &e2)->bool {
189  return e2.x() < e1.x();
190  });
191  pv.erase(std::unique(pv.begin(), pv.end()), pv.end());
192  if (pv.size() != count && pv.size() < 3) {
193  *err_msg = strdup("After eliminating duplicated points, less than 3 points remain!!. Alpha shape calculation needs at least 3 vertices.");
194  return -1;
195  }
196  points.insert(points.begin(), pv.begin(), pv.end());
197  }
198 
199  Alpha_shape_2 A(points.begin(), points.end(),
200  coord_type(10000),
201  Alpha_shape_2::REGULARIZED);
202 
203  std::vector<Segment> segments;
204  // std::vector<Segment> result;
205 
206  // Alpha_shape_2::Alpha_shape_vertices_iterator vit;
207  // Alpha_shape_2::Vertex_handle vertex;
208  // Alpha_shape_2::Alpha_shape_edges_iterator eit;
209  // Alpha_shape_2::Edge edge;
210  // Alpha_shape_2::Face_iterator fit;
211  // Alpha_shape_2::Face_handle face;
212 
213  if (alpha <= 0.0) {
214  alpha = *A.find_optimal_alpha(1);
215  }
216  A.set_alpha(alpha);
217 
218  alpha_edges(A, std::back_inserter(segments));
219 
220  // Segment s = segments.at(0);
221  // find_next_edge(s, segments, result);
222  if (segments.empty()) {
223  *res = NULL;
224  *res_count = 0;
225  } else {
226  std::set<int> unusedIndexes;
227  for (unsigned int i = 0; i < segments.size(); i++) {
228  unusedIndexes.insert(i);
229  }
230 
231  std::vector<Polygon_2> rings;
232  Polygon_2 ring;
233  ring.push_back(segments.at(0).source());
234  rings.push_back(ring);
235  unusedIndexes.erase(0);
236  find_next_edge(segments.at(0), segments, unusedIndexes, rings);
237 
238  size_t result_count = 0;
239  for (unsigned int i = 0; i < rings.size(); i++) {
240  Polygon_2 ring = rings.at(i);
241  result_count += ring.size();
242  }
243  result_count += rings.size() - 1;
244  *res = pgr_alloc(result_count, (*res));
245  *res_count = result_count;
246 
247  int idx = 0;
248  for (unsigned int i = 0; i < rings.size(); i++) {
249  if (i > 0) {
250  (*res)[idx].x = DBL_MAX;
251  (*res)[idx].y = DBL_MAX;
252  idx++;
253  }
254  Polygon_2 ring = rings.at(i);
255  for (unsigned int j = 0; j < ring.size(); j++) {
256  Point point = ring.vertex(j);
257  (*res)[idx].x = point.x();
258  (*res)[idx].y = point.y();
259  idx++;
260  }
261  }
262  }
263  *err_msg = NULL;
264 
265  return EXIT_SUCCESS;
266  } catch ( ... ) {
267  *err_msg = strdup("Caught unknown exception!");
268  }
269  return -1;
270 }
K::Point_2 Point
void alpha_edges(const Alpha_shape_2 &A, OutputIterator out)
CGAL::Alpha_shape_2< Ht > Alpha_shape_2
double coord_type
CGAL::Polygon_2< K > Polygon_2
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:64
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: