pgrouting::alphashape::Pgr_alphaShape Class Reference

#include "pgr_alphaShape.h"

Inheritance diagram for pgrouting::alphashape::Pgr_alphaShape:

Collaboration diagram for pgrouting::alphashape::Pgr_alphaShape:

Classes
struct	EdgesFilter

Public Member Functions
	Pgr_alphaShape ()=delete
	Pgr_alphaShape (const std::vector< Pgr_edge_xy_t > &edges)
void	clear ()
	clear More...
std::string	get_error () const
	get_error More...
std::string	get_log () const
	get_log More...
std::string	get_notice () const
	get_notice More...
bool	has_error () const
	get_error More...
std::vector< Bpoly >	operator() (double alpha) const

Public Attributes
std::ostringstream	error
	Stores the error information. More...
std::ostringstream	log
	Stores the hint information. More...
std::ostringstream	notice
	Stores the notice information. More...

Private Member Functions
std::vector< Bpoly >	build_best_alpha () const
bool	faceBelongs (const Triangle face, double alpha) const
void	make_triangles ()
double	radius (const Triangle t) const
void	recursive_build (const Triangle face, std::set< Triangle > &used, std::set< E > &border_edges, double alpha) const

Private Attributes
G	graph
	sides graph More...
std::map< Triangle, std::set< Triangle > >	m_adjacent_triangles
	t -> {adj_t} More...

Friends
std::ostream &	operator<< (std::ostream &, const Pgr_alphaShape &)

Detailed Description

Definition at line 63 of file pgr_alphaShape.h.

Constructor & Destructor Documentation

Pgr_alphaShape() [1/2]

pgrouting::alphashape::Pgr_alphaShape::Pgr_alphaShape ( )

delete

Pgr_alphaShape() [2/2]

pgrouting::alphashape::Pgr_alphaShape::Pgr_alphaShape ( const std::vector< Pgr_edge_xy_t > &  edges )

explicit

Definition at line 167 of file pgr_alphaShape.cpp.

                                                                    :
graph(UNDIRECTED) {
    graph.insert_edges(edges);
    make_triangles();
}

References graph, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::insert_edges(), and make_triangles().

Member Function Documentation

build_best_alpha()

std::vector< Bpoly > pgrouting::alphashape::Pgr_alphaShape::build_best_alpha ( ) const

private

Definition at line 248 of file pgr_alphaShape.cpp.

                                       {
    std::map<Triangle, double> border_triangles;
    std::map<Triangle, double> inner_triangles;
 
    size_t i(0);
    for (const auto &t : m_adjacent_triangles) {
        if (t.second.size() == 2) {
            border_triangles[t.first] = radius(t.first);
        } else  {
            inner_triangles[t.first] = radius(t.first);
        }
        ++i;
    }
    pgassert(border_triangles.size() + inner_triangles.size() == i);
 
    auto max_border_triangle = *std::min_element(border_triangles.begin(), border_triangles.end(), CompareRadius());
    auto max_inner_triangle = *std::min_element(inner_triangles.begin(), inner_triangles.end(), CompareRadius());
 
    double max_border_radius = max_border_triangle.second;
    double max_inner_radius = max_inner_triangle.second;
 
 
    auto count = border_triangles.size() + inner_triangles.size();
    while (max_border_radius >= max_inner_radius) {
        auto max_border_triangle = *std::min_element(border_triangles.begin(), border_triangles.end(), CompareRadius());
        auto max_inner_triangle = *std::min_element(inner_triangles.begin(), inner_triangles.end(), CompareRadius());
        /*
         * Removing largest border triangle
         */
        border_triangles.erase(max_border_triangle.first);
 
        /*
         * Adjacent triangles of a border triangle
         *  - are no longer inner triangles
         *  - are now border triangles
         */
        for (const auto &t : m_adjacent_triangles.at(max_border_triangle.first)) {
            if (inner_triangles.find(t) != inner_triangles.end()) {
                inner_triangles.erase(t);
                border_triangles[t] = radius(t);
            }
        }
 
        auto new_max_border_triangle = *std::min_element(
                border_triangles.begin(), border_triangles.end(), CompareRadius());
        auto new_max_inner_triangle = *std::min_element(
                inner_triangles.begin(), inner_triangles.end(), CompareRadius());
 
        if (new_max_border_triangle.second < new_max_inner_triangle.second) {
            /*
             * Roll back and exit loop
             */
             for (const auto &t : m_adjacent_triangles.at(max_border_triangle.first)) {
                 border_triangles.erase(t);
                 inner_triangles[t] = radius(t);
             }
            border_triangles[max_border_triangle.first] = max_border_triangle.second;
            break;
        }
        max_border_radius = new_max_border_triangle.second;
        max_inner_radius = new_max_inner_triangle.second;
        pgassert(count > (border_triangles.size() + inner_triangles.size()));
        count = border_triangles.size() + inner_triangles.size();;
    }
 
    pgassert(max_border_radius > 0);
    log << "Using Alpha:" << max_border_radius * max_border_radius;
    return this->operator()(max_border_radius);
}

References pgrouting::Pgr_messages::log, m_adjacent_triangles, operator()(), pgassert, and radius().

Referenced by operator()().

clear()

void pgrouting::Pgr_messages::clear ( )

inherited

clear

Clears All the messages

Definition at line 59 of file pgr_messages.cpp.

                    {
    log.str("");
    log.clear();
 
    notice.str("");
    notice.clear();
 
    error.str("");
    error.clear();
}

References pgrouting::Pgr_messages::error, pgrouting::Pgr_messages::log, and pgrouting::Pgr_messages::notice.

Referenced by do_pgr_pickDeliver().

faceBelongs()

bool pgrouting::alphashape::Pgr_alphaShape::faceBelongs ( const Triangle  face, double  alpha  ) const

private

Definition at line 243 of file pgr_alphaShape.cpp.

                                                                {
        return radius(t) <= alpha;
}

References radius().

Referenced by recursive_build().

get_error()

std::string pgrouting::Pgr_messages::get_error ( ) const

inherited

get_error

Returns

the current contents of the log and clears the log

Definition at line 53 of file pgr_messages.cpp.

                              {
    auto str = error.str();
    return str;
}

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

get_log()

std::string pgrouting::Pgr_messages::get_log ( ) const

inherited

get_log

Returns

the current contents of the log and clears the log

Definition at line 36 of file pgr_messages.cpp.

                            {
    auto str = log.str();
    return str;
}

References pgrouting::Pgr_messages::log.

Referenced by do_pgr_bipartite(), do_pgr_boyerMyrvold(), do_pgr_LTDTree(), do_pgr_makeConnected(), do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), pgr_bellman_ford(), pgr_dijkstraTR(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

get_notice()

std::string pgrouting::Pgr_messages::get_notice ( ) const

inherited

get_notice

Returns

the current contents of the log and clears the log

Definition at line 42 of file pgr_messages.cpp.

                               {
    auto str = notice.str();
    return str;
}

References pgrouting::Pgr_messages::notice.

has_error()

bool pgrouting::Pgr_messages::has_error ( ) const

inherited

get_error

Returns

the current contents of the log and clears the log

Definition at line 48 of file pgr_messages.cpp.

                              {
    return  !error.str().empty();
}

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

make_triangles()

void pgrouting::alphashape::Pgr_alphaShape::make_triangles ( )

private

Definition at line 174 of file pgr_alphaShape.cpp.

                               {
    /*
     * triangle sides:
     * a_r, b, c  edge descriptor
     */
    BGL_FORALL_EDGES(c, graph.graph, BG) {
        /*
         * triangle vertices:
         * u, v, w vertex descriptor
         */
        auto u = graph.source(c);
        auto v = graph.target(c);
 
        std::vector<Triangle> adjacent_to_side;
 
        size_t i = 0;
        BGL_FORALL_OUTEDGES(u, b, graph.graph, BG) {
            ++i;
            auto w = graph.adjacent(u, b);
            if (w == v) {
                pgassert(b == c);
                continue;
            }
 
            auto a_r = boost::edge(v, w, graph.graph);
            if (!a_r.second) continue;
 
            Triangle face{{a_r.first, b, c}};
            adjacent_to_side.push_back(face);
        }
 
        /*
         * All vertices must have at least 2 edges
         * So cycle above must have passed at least twice
         */
        pgassert(i > 1);
 
        if (adjacent_to_side.size() == 2) {
            m_adjacent_triangles[adjacent_to_side[0]].insert(adjacent_to_side[1]);
            m_adjacent_triangles[adjacent_to_side[1]].insert(adjacent_to_side[0]);
        } else {
            if (m_adjacent_triangles.find(adjacent_to_side[0]) == m_adjacent_triangles.end()) {
                m_adjacent_triangles[adjacent_to_side[0]].clear();
            }
        }
    }
}

References pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::adjacent(), graph, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, m_adjacent_triangles, pgassert, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::source(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target().

Referenced by Pgr_alphaShape().

operator()()

std::vector< Bpoly > pgrouting::alphashape::Pgr_alphaShape::operator()

(

double

alpha

)

const

Definition at line 368 of file pgr_alphaShape.cpp.

                                              {
    std::vector<Bpoly> shape;
 
    if (alpha <= 0) return build_best_alpha();
 
    std::set<Triangle> used;
    using Subgraph = boost::filtered_graph<BG, EdgesFilter, boost::keep_all>;
 
    for (const auto &t : m_adjacent_triangles) {
        EdgesFilter border_edges;
        /*
         * Recurse through the triangles to get the border sides
         */
        recursive_build(t.first, used, border_edges.edges, alpha);
        /*
         * triangle was already processed
         * or is not part of the shape
         */
        if (border_edges.edges.empty()) continue;
 
        std::vector<Bpoly> polys;
        Bpoly polygon;
        double area = 0;
        while (!border_edges.edges.empty()) {
            auto first_edge = *border_edges.edges.begin();
            border_edges.edges.erase(first_edge);
 
            Subgraph subg(graph.graph, border_edges, {});
 
            auto source = boost::source(first_edge, subg);
            auto target = boost::target(first_edge, subg);
 
 
            auto predecessors = get_predecessors(source, target, subg);
            std::set<E> edges_used;
            auto poly = get_polygon(source, target, predecessors, subg, edges_used);
 
            for (const auto &e : edges_used) {
                border_edges.edges.erase(e);
            }
 
            pgassert(bg::num_points(poly) >= 3 || bg::num_points(poly) == 0);
 
            if (bg::num_points(poly) == 0) continue;
 
            /*
             * A polygon must have at least 3 vertices
             */
            if (bg::num_points(poly) >= 3) {
                if (area == 0) {
                    /*
                     * consider the first polygon as the outer polygon
                     */
                    polygon = poly;
                    area = bg::area(poly);
                } else {
                    auto new_area = bg::area(poly);
                    if (new_area > area) {
                        /*
                         * if new poly is larger than the current outer polygon
                         * - save current outer polygon as inner ring
                         * - save new poly as outer polygon
                         */
                        polys.push_back(polygon);
                        area = new_area;
                        polygon = poly;
                    } else {
                        /*
                         * New poly is inner ring
                         */
                        polys.push_back(poly);
                    }
                }
            }
        }
 
        /*
         * Add inner rings to the polygon
         */
        if (!polys.empty()) {
            polygon.inners().resize(polys.size());
            size_t i(0);
            for (const auto &inner_ring : polys) {
                bg::assign(polygon.inners()[i++], inner_ring);
            }
        }
 
        /*
         * Add the polygon to the alpha shape
         */
        shape.push_back(polygon);
    }
 
    return shape;
}

References build_best_alpha(), pgrouting::alphashape::Pgr_alphaShape::EdgesFilter::edges, pgrouting::alphashape::anonymous_namespace{pgr_alphaShape.cpp}::get_polygon(), pgrouting::alphashape::anonymous_namespace{pgr_alphaShape.cpp}::get_predecessors(), graph, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::graph, m_adjacent_triangles, pgassert, and recursive_build().

Referenced by build_best_alpha().

radius()

double pgrouting::alphashape::Pgr_alphaShape::radius ( const Triangle  t ) const

private

Definition at line 227 of file pgr_alphaShape.cpp.

                                             {
        std::vector<E> edges(t.begin(), t.end());
        auto a = graph.source(edges[0]);
        auto b = graph.target(edges[0]);
        auto c = graph.source(edges[1]);
        c = (c == a || c == b)? graph.target(edges[1]) : c;
        pgassert(a != b && a != c && b!= c);
 
        auto center = circumcenter(graph[a].point, graph[b].point, graph[c].point);
        return bg::distance(center, graph[a].point);
}

References pgrouting::alphashape::anonymous_namespace{pgr_alphaShape.cpp}::circumcenter(), graph, pgassert, pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::source(), and pgrouting::graph::Pgr_base_graph< G, T_V, T_E >::target().

Referenced by build_best_alpha(), and faceBelongs().

recursive_build()

void pgrouting::alphashape::Pgr_alphaShape::recursive_build ( const Triangle  face, std::set< Triangle > &  used, std::set< E > &  border_edges, double  alpha  ) const

private

Definition at line 319 of file pgr_alphaShape.cpp.

                            {
    /*
     * Do nothing when the face does not belong to the polygon of the alphashape
     */
    if (!faceBelongs(face, alpha)) return;
 
    /*
     * Do nothing when the face has being processed before
     */
    auto original = used.size();
    used.insert(face);
    if (original == used.size())  return;
 
    std::set<E> common_sides;
    for (const auto &adj_t : m_adjacent_triangles.at(face)) {
        if (!faceBelongs(adj_t, alpha)) {
            /*
             * Adjacent face is not on shape
             * then side is on the border
             */
            std::set_intersection(
                    face.begin(), face.end(),
                    adj_t.begin(), adj_t.end(),
                    std::inserter(border_edges, border_edges.end()));
        }
        std::set_intersection(
                face.begin(), face.end(),
                adj_t.begin(), adj_t.end(),
                std::inserter(common_sides, common_sides.end()));
        recursive_build(adj_t, used, border_edges, alpha);
    }
 
    if (m_adjacent_triangles.at(face).size() == 2) {
        /*
         * Side without adjacent triangle (in convex hull)
         * is part of the border
         */
        std::set_difference(
                face.begin(), face.end(),
                common_sides.begin(), common_sides.end(),
                std::inserter(border_edges, border_edges.end()));
    }
}

References faceBelongs(), and m_adjacent_triangles.

Referenced by operator()().

Friends And Related Function Documentation

operator<<

std::ostream& operator<< ( std::ostream &  os, const Pgr_alphaShape &  d  )

friend

Definition at line 468 of file pgr_alphaShape.cpp.

                                                    {
    os << d.graph;
 
    return os;
}

Member Data Documentation

error

std::ostringstream pgrouting::Pgr_messages::error

mutableinherited

Stores the error information.

Definition at line 85 of file pgr_messages.h.

Referenced by pgrouting::vrp::Fleet::build_fleet(), pgrouting::Pg_points_graph::check_points(), pgrouting::Pgr_messages::clear(), pgrouting::Pg_points_graph::create_new_edges(), pgrouting::Pgr_messages::get_error(), pgrouting::Pgr_messages::has_error(), pgrouting::vrp::Fleet::is_fleet_ok(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

graph

G pgrouting::alphashape::Pgr_alphaShape::graph

private

sides graph

Definition at line 93 of file pgr_alphaShape.h.

Referenced by make_triangles(), operator()(), pgrouting::alphashape::operator<<(), Pgr_alphaShape(), and radius().

log

std::ostringstream pgrouting::Pgr_messages::log

mutableinherited

Stores the hint information.

Definition at line 81 of file pgr_messages.h.

Referenced by pgrouting::vrp::Fleet::add_vehicle(), Pgr_bellman_ford< G >::bellman_ford(), Pgr_bellman_ford< G >::bellman_ford_1_to_1(), Pgr_bellman_ford< G >::bellman_ford_1_to_many(), build_best_alpha(), pgrouting::vrp::Fleet::build_fleet(), pgrouting::Pg_points_graph::check_points(), pgrouting::Pgr_messages::clear(), pgrouting::Pg_points_graph::create_new_edges(), pgrouting::vrp::Vehicle_pickDeliver::do_while_feasable(), pgrouting::vrp::Initial_solution::do_while_foo(), pgrouting::functions::Pgr_makeConnected< G >::generatemakeConnected(), pgrouting::Pgr_messages::get_log(), Pgr_bellman_ford< G >::get_paths(), pgrouting::vrp::Pgr_pickDeliver::get_postgres_result(), pgrouting::vrp::Vehicle::get_postgres_result(), pgrouting::vrp::Fleet::get_truck(), pgrouting::vrp::Optimize::inter_swap(), pgrouting::vrp::Fleet::is_fleet_ok(), pgrouting::vrp::Initial_solution::one_truck_all_orders(), pgrouting::vrp::Optimize::Optimize(), pgrouting::Pg_points_graph::Pg_points_graph(), pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver(), pgrouting::vrp::Optimize::save_if_best(), pgrouting::vrp::Solution::Solution(), pgrouting::vrp::Pgr_pickDeliver::solve(), and pgrouting::vrp::Vehicle::Vehicle().

m_adjacent_triangles

std::map<Triangle, std::set<Triangle> > pgrouting::alphashape::Pgr_alphaShape::m_adjacent_triangles

private

t -> {adj_t}

Definition at line 95 of file pgr_alphaShape.h.

Referenced by build_best_alpha(), make_triangles(), operator()(), and recursive_build().

notice

std::ostringstream pgrouting::Pgr_messages::notice

mutableinherited

Stores the notice information.

Definition at line 83 of file pgr_messages.h.

Referenced by pgrouting::Pgr_messages::clear(), and pgrouting::Pgr_messages::get_notice().

---

The documentation for this class was generated from the following files:

• pgr_alphaShape.h
• pgr_alphaShape.cpp