PGROUTING  3.2
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
6 
7 Copyright (c) 2018 Celia Virginia Vergara Castillo
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_
pgrouting::Pgr_messages
Definition: pgr_messages.h:39
pgrouting::XY_vertex
Definition: xy_vertex.h:40
pgr_base_graph.hpp
pgrouting::alphashape::Pgr_alphaShape::make_triangles
void make_triangles()
Definition: pgr_alphaShape.cpp:174
pgr_messages.h
pgrouting::alphashape::Pgr_alphaShape::faceBelongs
bool faceBelongs(const Triangle face, double alpha) const
Definition: pgr_alphaShape.cpp:243
pgrouting::alphashape::Triangle
std::set< E > Triangle
Definition: pgr_alphaShape.h:60
bline.hpp
pgr_edge_xy_t.h
pgrouting::Basic_edge
Definition: basic_edge.h:35
pgrouting::alphashape::Pgr_alphaShape::EdgesFilter::operator()
bool operator()(E e) const
Definition: pgr_alphaShape.h:87
pgrouting::alphashape::Pgr_alphaShape::Pgr_alphaShape
Pgr_alphaShape()=delete
pgrouting::alphashape::Pgr_alphaShape::graph
G graph
sides graph
Definition: pgr_alphaShape.h:93
pgrouting::alphashape::Pgr_alphaShape::build_best_alpha
std::vector< Bpoly > build_best_alpha() const
Definition: pgr_alphaShape.cpp:248
pgrouting::alphashape::E
boost::graph_traits< BG >::edge_descriptor E
Definition: pgr_alphaShape.h:57
pgrouting::alphashape::Pgr_alphaShape::m_adjacent_triangles
std::map< Triangle, std::set< Triangle > > m_adjacent_triangles
t -> {adj_t}
Definition: pgr_alphaShape.h:95
pgrouting::alphashape::Pgr_alphaShape::EdgesFilter::edges
std::set< E > edges
Definition: pgr_alphaShape.h:86
pgrouting::alphashape::BG
boost::adjacency_list< boost::setS, boost::vecS, boost::undirectedS, XY_vertex, Basic_edge > BG
Definition: pgr_alphaShape.h:55
pgrouting::alphashape::Pgr_alphaShape::EdgesFilter
Definition: pgr_alphaShape.h:85
pgrouting::alphashape::Pgr_alphaShape::EdgesFilter::clear
void clear()
Definition: pgr_alphaShape.h:88
pgrouting::alphashape::Pgr_alphaShape::radius
double radius(const Triangle t) const
Definition: pgr_alphaShape.cpp:227
pgrouting::graph::Pgr_base_graph< BG, XY_vertex, Basic_edge >
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58
pgrouting::alphashape::Pgr_alphaShape::operator()
std::vector< Bpoly > operator()(double alpha) const
Definition: pgr_alphaShape.cpp:368
pgrouting::alphashape::Pgr_alphaShape
Definition: pgr_alphaShape.h:63
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::alphashape::Pgr_alphaShape::recursive_build
void recursive_build(const Triangle face, std::set< Triangle > &used, std::set< E > &border_edges, double alpha) const
Definition: pgr_alphaShape.cpp:319
pgrouting::alphashape::Pgr_alphaShape::operator<<
friend std::ostream & operator<<(std::ostream &, const Pgr_alphaShape &)
Definition: pgr_alphaShape.cpp:468