graph_triangulation.hh 4.46 KB
Newer Older
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2006-2020 Tiago de Paula Peixoto <tiago@skewed.de>
4
//
5
6
7
8
// This program is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the Free
// Software Foundation; either version 3 of the License, or (at your option) any
// later version.
9
//
10
11
12
13
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
// details.
14
//
15
// You should have received a copy of the GNU Lesser General Public License
16
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

18
19
20
21
// As a special exception, you have permission to link this program
// with the CGAL library and distribute executables, as long as you
// follow the requirements of the GNU GPL in regard to all of the
// software in the executable aside from CGAL.
22
23
24
25
26

#ifndef GRAPH_TRIANGULATION_HH
#define GRAPH_TRIANGULATION_HH

#include "graph_util.hh"
27
#include "hash_map_wrap.hh"
28
29
30
31
32
33
34
35
36
37
38
39

namespace graph_tool
{
using namespace std;
using namespace boost;

struct hash_point
{
    template <class Vertex>
    std::size_t operator()(const Vertex& v) const
    {
        size_t seed = 42;
40
41
42
        _hash_combine(seed, v.point().x());
        _hash_combine(seed, v.point().y());
        _hash_combine(seed, v.point().z());
43
44
45
46
        return seed;
    }
};

47
template <class Triang, class IsPeriodic>
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct get_triangulation
{
    // this will insert edges in the graph
    template <class Graph, class VertexMap>
    class edge_inserter
    {
    public:
        typedef output_iterator_tag iterator_category;
        typedef typename graph_traits<Graph>::vertex_descriptor value_type;
        typedef size_t difference_type;
        typedef typename graph_traits<Graph>::vertex_descriptor* pointer;
        typedef typename graph_traits<Graph>::vertex_descriptor& reference;

        edge_inserter(Graph& g, const typename VertexMap::key_type& v,
62
63
                      VertexMap& vertex_map)
            : _g(g), _vertex_map(vertex_map), _source(vertex_map[v]) {}
64
65
66
67
68
69
70
71

        edge_inserter& operator++() { return *this; }
        edge_inserter& operator++(int) { return *this; }
        edge_inserter& operator*() { return *this; }

        template <class Vertex>
        edge_inserter& operator=(const Vertex& v)
        {
72
            auto iter = _vertex_map.find(*v);
73
74
            if (iter != _vertex_map.end())
            {
75
                auto target = iter->second;
76
                if (!is_adjacent(_source, target, _g) && _source != target)
77
78
79
80
81
82
83
                    add_edge(_source, target, _g);
            }
            return *this;
        }

    private:
        Graph& _g;
84
        VertexMap& _vertex_map;
85
86
87
        typename graph_traits<Graph>::vertex_descriptor _source;
    };

88
89
90
91
92
93
94
95
96
97
98
99
100

    template <class T, class VIter, class Vis>
    void incident_vertices(T& t, VIter& v_iter, Vis& vis, std::true_type) const
    {
        t.incident_vertices(v_iter, vis);
    }

    template <class T, class VIter, class Vis>
    void incident_vertices(T& t, VIter& v_iter, Vis& vis, std::false_type) const
    {
        t.finite_incident_vertices(v_iter, vis);
    }

101
102
103
    template <class Graph, class Points, class PosMap>
    void operator()(Graph& g, Points& points, PosMap pos) const
    {
104
105
106
        typedef std::unordered_map <typename Triang::Vertex,
                                    typename graph_traits<Graph>::vertex_descriptor,
                                    hash_point> vertex_map_t;
107
108
109
110
111
112
        vertex_map_t vertex_map;

        Triang T;
        for (size_t i = 0; i < points.shape()[0]; ++i)
        {
            typename Triang::Point p(points[i][0], points[i][1], points[i][2]);
113
            auto v = add_vertex(g);
114
115
116
117
118
119
            vertex_map[*T.insert(p)] = v;
            pos[v].resize(3);
            for (size_t j = 0; j < 3; ++j)
                pos[v][j] = points[i][j];
        }

120
121
122
        auto v_iter = T.finite_vertices_begin();
        auto v_end = T.finite_vertices_end();
        while (v_iter != v_end)
123
        {
124
125
126
127
128
129
130
            auto v = *v_iter;
            if (vertex_map.find(v) != vertex_map.end())
            {
                edge_inserter<Graph, vertex_map_t> insert(g, v, vertex_map);
                incident_vertices(T, v_iter, insert, IsPeriodic());
            }
            ++v_iter;
131
132
133
134
135
136
137
138
        }
    }

};

} // namespace graph_tool

#endif // GRAPH_TRIANGULATION_HH