source: GTP/trunk/Lib/Geom/shared/GTGeometry/src/connectivity_graph.cpp @ 774

Revision 774, 3.1 KB checked in by gumbau, 19 years ago (diff)

GTGeometry and GeoTool? initial imports

Line 
1//
2// Copyright (C) 2004 Tanguy Fautré.
3// For conditions of distribution and use,
4// see copyright notice in tri_stripper.h
5//
6//////////////////////////////////////////////////////////////////////
7// SVN: $Id: connectivity_graph.cpp 86 2005-06-08 17:47:27Z gpsnoopy $
8//////////////////////////////////////////////////////////////////////
9
10#include "detail/connectivity_graph.h"
11
12#include <algorithm>
13
14
15
16
17namespace triangle_stripper {
18
19        namespace detail {
20
21
22
23
24namespace
25{
26
27        class tri_edge : public triangle_edge
28        {
29        public:
30                tri_edge(index A, index B, size_t TriPos)
31                        : triangle_edge(A, B), m_TriPos(TriPos) { }
32
33                size_t TriPos() const { return m_TriPos; }
34
35        private:
36                size_t  m_TriPos;
37        };
38
39
40        class cmp_tri_edge_lt
41        {
42        public:
43                bool operator() (const tri_edge & a, const tri_edge & b) const;
44        };
45
46
47        typedef std::vector<tri_edge> edge_map;
48
49
50        void LinkNeighbours(graph_array<triangle> & Triangles, const edge_map & EdgeMap, const tri_edge Edge);
51
52}
53
54
55
56
57void make_connectivity_graph(graph_array<triangle> & Triangles, const indices & Indices)
58{
59        assert(Triangles.size() == (Indices.size() / 3));
60
61        // Fill the triangle data
62        for (size_t i = 0; i < Triangles.size(); ++i)
63                Triangles[i] = triangle(Indices[i * 3 + 0], Indices[i * 3 + 1], Indices[i * 3 + 2]);
64
65        // Build an edge lookup table
66        edge_map EdgeMap;
67        EdgeMap.reserve(Triangles.size() * 3);
68
69        for (size_t i = 0; i < Triangles.size(); ++i) {
70
71                const triangle & Tri = * Triangles[i];
72
73                EdgeMap.push_back(tri_edge(Tri.A(), Tri.B(), i));
74                EdgeMap.push_back(tri_edge(Tri.B(), Tri.C(), i));
75                EdgeMap.push_back(tri_edge(Tri.C(), Tri.A(), i));
76        }
77
78        std::sort(EdgeMap.begin(), EdgeMap.end(), cmp_tri_edge_lt());
79
80        // Link neighbour triangles together using the lookup table
81        for (size_t i = 0; i < Triangles.size(); ++i) {
82
83                const triangle & Tri = * Triangles[i];
84
85                LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.B(), Tri.A(), i));
86                LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.C(), Tri.B(), i));
87                LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.A(), Tri.C(), i));
88        }
89}
90
91
92
93namespace
94{
95       
96        inline bool cmp_tri_edge_lt::operator() (const tri_edge & a, const tri_edge & b) const
97        {
98                const index A1 = a.A();
99                const index B1 = a.B();
100                const index A2 = b.A();
101                const index B2 = b.B();
102
103                if ((A1 < A2) || ((A1 == A2) && (B1 < B2)))
104                        return true;
105                else
106                        return false;
107        }
108
109
110        void LinkNeighbours(graph_array<triangle> & Triangles, const edge_map & EdgeMap, const tri_edge Edge)
111        {
112                // Find the first edge equal to Edge
113                edge_map::const_iterator it = std::lower_bound(EdgeMap.begin(), EdgeMap.end(), Edge, cmp_tri_edge_lt());
114
115                // See if there are any other edges that are equal
116                // (if so, it means that more than 2 triangles are sharing the same edge,
117                //  which is unlikely but not impossible)
118                for (; (it != EdgeMap.end()) && (Edge == (* it)); ++it)
119                        Triangles.insert_arc(Edge.TriPos(), it->TriPos());
120
121                // Note: degenerated triangles will also point themselves as neighbour triangles
122        }
123
124}
125
126
127
128
129        } // namespace detail
130
131} // namespace detail
132
Note: See TracBrowser for help on using the repository browser.