PGROUTING  3.1
pgr_alphaShape.h
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 file: pgr_alphaShape.h
3 
4 Copyright (c) 2018 pgRouting developers
5 Mail: project@pgrouting.org
6 
7 Copyright (c) 2018 Celia Virginia Vergara Castillo
8 vicky_vergara@hotmail.com
9 
10 ------
11 
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version.
16 
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21 
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25 
26  ********************************************************************PGR-GNU*/
29 #ifndef INCLUDE_ALPHASHAPE_PGR_ALPHASHAPE_H_
30 #define INCLUDE_ALPHASHAPE_PGR_ALPHASHAPE_H_
31 #pragma once
32 
33 #ifndef __cplusplus
34 #error This is C++ header file
35 #endif
36 
37 #include <vector>
38 #include <map>
39 #include <set>
40 #include <iosfwd>
41 
42 #include "c_types/pgr_edge_xy_t.h"
44 
46 #include "cpp_common/bline.hpp"
47 
48 
49 namespace pgrouting {
50 namespace alphashape {
51 
52 using BG = boost::adjacency_list<
53  boost::setS, boost::vecS,
54  boost::undirectedS,
57 using E = boost::graph_traits<BG>::edge_descriptor;
58 using V = boost::graph_traits<BG>::vertex_descriptor;
59 
60 using Triangle = std::set<E>;
61 
62 
63 class Pgr_alphaShape : public Pgr_messages {
64  public:
65  Pgr_alphaShape() = delete;
66  explicit Pgr_alphaShape(const std::vector<Pgr_edge_xy_t> &edges);
67 
68  std::vector<Bpoly> operator() (double alpha) const;
69 
70  friend std::ostream& operator<<(std::ostream&, const Pgr_alphaShape&);
71 
72  private:
73  void make_triangles();
74  double radius(const Triangle t) const;
75  bool faceBelongs(
76  const Triangle face,
77  double alpha) const;
78  void recursive_build(
79  const Triangle face,
80  std::set<Triangle> &used,
81  std::set<E> &border_edges,
82  double alpha) const;
83  std::vector<Bpoly> build_best_alpha() const;
84 
85  struct EdgesFilter {
86  std::set<E> edges;
87  bool operator()(E e) const { return edges.count(e); }
88  void clear() { edges.clear(); }
89  };
90 
91  private:
95  std::map<Triangle, std::set<Triangle>> m_adjacent_triangles;
96 };
97 
98 
99 } // namespace alphashape
100 } // namespace pgrouting
101 
102 #endif // INCLUDE_ALPHASHAPE_PGR_ALPHASHAPE_H_
double radius(const Triangle t) const
std::vector< Bpoly > operator()(double alpha) const
std::vector< Bpoly > build_best_alpha() const
friend std::ostream & operator<<(std::ostream &, const Pgr_alphaShape &)
boost::graph_traits< BG >::vertex_descriptor V
boost::graph_traits< BG >::edge_descriptor E
std::set< E > Triangle
boost::adjacency_list< boost::setS, boost::vecS, boost::undirectedS, XY_vertex, Basic_edge > BG
void recursive_build(const Triangle face, std::set< Triangle > &used, std::set< E > &border_edges, double alpha) const
bool faceBelongs(const Triangle face, double alpha) const
Book keeping class for swapping orders between vehicles.
std::map< Triangle, std::set< Triangle > > m_adjacent_triangles
t -> {adj_t}