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

//
// Copyright (C) 2004 Tanguy Fautré.
// For conditions of distribution and use,
// see copyright notice in tri_stripper.h
//
//////////////////////////////////////////////////////////////////////
// SVN: $Id: connectivity_graph.cpp 86 2005-06-08 17:47:27Z gpsnoopy $
//////////////////////////////////////////////////////////////////////

#include "detail/connectivity_graph.h"

#include <algorithm>




namespace triangle_stripper {

        namespace detail {




namespace
{

        class tri_edge : public triangle_edge
        {
        public:
                tri_edge(index A, index B, size_t TriPos)
                        : triangle_edge(A, B), m_TriPos(TriPos) { }

                size_t TriPos() const { return m_TriPos; }

        private:
                size_t  m_TriPos;
        };


        class cmp_tri_edge_lt
        {
        public:
                bool operator() (const tri_edge & a, const tri_edge & b) const;
        };


        typedef std::vector<tri_edge> edge_map;


        void LinkNeighbours(graph_array<triangle> & Triangles, const edge_map & EdgeMap, const tri_edge Edge);

}




void make_connectivity_graph(graph_array<triangle> & Triangles, const indices & Indices)
{
        assert(Triangles.size() == (Indices.size() / 3));

        // Fill the triangle data
        for (size_t i = 0; i < Triangles.size(); ++i)
                Triangles[i] = triangle(Indices[i * 3 + 0], Indices[i * 3 + 1], Indices[i * 3 + 2]);

        // Build an edge lookup table
        edge_map EdgeMap;
        EdgeMap.reserve(Triangles.size() * 3);

        for (size_t i = 0; i < Triangles.size(); ++i) {

                const triangle & Tri = * Triangles[i];

                EdgeMap.push_back(tri_edge(Tri.A(), Tri.B(), i)); 
                EdgeMap.push_back(tri_edge(Tri.B(), Tri.C(), i)); 
                EdgeMap.push_back(tri_edge(Tri.C(), Tri.A(), i)); 
        }

        std::sort(EdgeMap.begin(), EdgeMap.end(), cmp_tri_edge_lt());

        // Link neighbour triangles together using the lookup table
        for (size_t i = 0; i < Triangles.size(); ++i) {

                const triangle & Tri = * Triangles[i];

                LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.B(), Tri.A(), i)); 
                LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.C(), Tri.B(), i)); 
                LinkNeighbours(Triangles, EdgeMap, tri_edge(Tri.A(), Tri.C(), i)); 
        }
}



namespace
{
        
        inline bool cmp_tri_edge_lt::operator() (const tri_edge & a, const tri_edge & b) const
        {
                const index A1 = a.A();
                const index B1 = a.B();
                const index A2 = b.A();
                const index B2 = b.B();

                if ((A1 < A2) || ((A1 == A2) && (B1 < B2)))
                        return true;
                else
                        return false;
        }


        void LinkNeighbours(graph_array<triangle> & Triangles, const edge_map & EdgeMap, const tri_edge Edge)
        {
                // Find the first edge equal to Edge
                edge_map::const_iterator it = std::lower_bound(EdgeMap.begin(), EdgeMap.end(), Edge, cmp_tri_edge_lt());

                // See if there are any other edges that are equal
                // (if so, it means that more than 2 triangles are sharing the same edge,
                //  which is unlikely but not impossible)
                for (; (it != EdgeMap.end()) && (Edge == (* it)); ++it)
                        Triangles.insert_arc(Edge.TriPos(), it->TriPos());

                // Note: degenerated triangles will also point themselves as neighbour triangles
        }

}




        } // namespace detail

} // namespace detail