Skip to content

File connection.cpp

File List > algorithm > connection.cpp

Go to the documentation of this file

// Copyright (c) 2012-2013, IGN France.
// Copyright (c) 2012-2022, Oslandia.
// SPDX-License-Identifier: LGPL-2.0-or-later

#include "SFCGAL/algorithm/connection.h"

#include "SFCGAL/Coordinate.h"
#include "SFCGAL/LineString.h"
#include "SFCGAL/Polygon.h"
#include "SFCGAL/PolyhedralSurface.h"
#include "SFCGAL/Triangle.h"
#include "SFCGAL/TriangulatedSurface.h"

#include <limits>

namespace SFCGAL::algorithm {

const size_t SurfaceGraph::INVALID_INDEX = std::numeric_limits<size_t>::max();

void
SurfaceGraph::addRing(const LineString &ring, FaceIndex faceIndex)
{
  const size_t numSegments = ring.numSegments();

  for (size_t s = 0; s != numSegments; ++s) { // for each segment
    const Coordinate startCoord = ring.pointN(s).coordinate();
    const Coordinate endCoord =
        ring.pointN((s + 1) % numSegments).coordinate(); // possible
                                                         // optimization: store
                                                         // the index of ring
                                                         // start point instead
                                                         // of finding it
    const auto startFound = _coordinateMap.find(startCoord);
    const auto endFound   = _coordinateMap.find(endCoord);
    BOOST_ASSERT(s + 1 != numSegments ||
                 endFound != _coordinateMap.end()); // ring not closed

    if (startFound != _coordinateMap.end() &&
        endFound != _coordinateMap.end()) {
      // found both end, we look for the edge
      const VertexIndex                         startIndex = startFound->second;
      const VertexIndex                         endIndex   = endFound->second;
      const std::pair<VertexIndex, VertexIndex> edge(startIndex, endIndex);
      const auto foundEdgeWithBadOrientation = _edgeMap.find(edge);

      if (foundEdgeWithBadOrientation != _edgeMap.end()) {
        _isValid = Validity::invalid(
            (boost::format("inconsistent orientation of PolyhedralSurface "
                           "detected at edge %d (%d-%d) of polygon %d") %
             s % edge.first % edge.second % faceIndex)
                .str());
      }

      const std::pair<VertexIndex, VertexIndex> reversedEdge(endIndex,
                                                             startIndex);

      const auto foundEdge = _edgeMap.find(reversedEdge);

      if (foundEdge != _edgeMap.end()) {
        // edit edge
        foundEdge->second.second = faceIndex;
        // we have two faces connected, this is an edge of the graph
        boost::add_edge(foundEdge->second.first, foundEdge->second.second,
                        _graph);
        // std::cerr << "face " << foundEdge->second.first << "->" <<
        // foundEdge->second.second << "\n";
      } else {
        // create edge
        _edgeMap.insert(
            std::make_pair(edge, std::make_pair(faceIndex, INVALID_INDEX)));
        // std::cerr << "face " << faceIndex << " edge " << edge.first << "-" <<
        // edge.second << "\n";
      }
    } else {
      // one end at least is missing, create the edge
      VertexIndex startIndex = 0;

      if (startFound == _coordinateMap.end()) {
        _coordinateMap.insert(std::make_pair(startCoord, _numVertices));
        startIndex = _numVertices;
        ++_numVertices;
      } else {
        startIndex = startFound->second;
      }

      VertexIndex endIndex = 0;

      if (endFound == _coordinateMap.end()) {
        _coordinateMap.insert(std::make_pair(endCoord, _numVertices));
        endIndex = _numVertices;
        ++_numVertices;
      } else {
        endIndex = endFound->second;
      }

      const std::pair<VertexIndex, VertexIndex> edge(startIndex, endIndex);

      _edgeMap.insert(
          std::make_pair(edge, std::make_pair(faceIndex, INVALID_INDEX)));

      // std::cerr << "face " << faceIndex << " edge " << edge.first << "-" <<
      // edge.second << "\n";
    }
  }
}

SurfaceGraph::SurfaceGraph(const PolyhedralSurface &surf)
    : _numVertices(0), _isValid(Validity::valid())
{
  const size_t numPolygons = surf.numPolygons();

  for (size_t p = 0; p != numPolygons; ++p) { // for each polygon
    const FaceIndex idx = boost::add_vertex(_graph);
    BOOST_ASSERT(idx == p);
    (void)idx;
    const Polygon &polygon  = surf.polygonN(p);
    const size_t   numRings = polygon.numRings();

    for (size_t r = 0; r != numRings; ++r) { // for each ring
      addRing(polygon.ringN(r), p);
    }
  }
}

SurfaceGraph::SurfaceGraph(const TriangulatedSurface &tin)
    : _numVertices(0), _isValid(Validity::valid())
{
  const size_t numTriangles = tin.numTriangles();

  for (size_t t = 0; t != numTriangles; ++t) { // for each polygon
    const FaceIndex idx = boost::add_vertex(_graph);
    BOOST_ASSERT(idx == t);
    (void)idx;
    const Triangle &triangle = tin.triangleN(t);
    addRing(triangle.toPolygon().exteriorRing(), t);
  }
}

auto
isConnected(const SurfaceGraph &graph) -> bool
{
  std::vector<SurfaceGraph::FaceIndex> component(
      boost::num_vertices(graph.faceGraph()));
  const size_t numComponents =
      boost::connected_components(graph.faceGraph(), component.data());
  return 1 == numComponents;
}

auto
isClosed(const SurfaceGraph &graph) -> bool
{
  const auto end = graph.edgeMap().end();

  for (auto e = graph.edgeMap().begin(); e != end; ++e) {
    if (e->second.second == SurfaceGraph::INVALID_INDEX) {
      return false;
    }
  }

  return true;
}

} // namespace SFCGAL::algorithm