PolygonSubdivider.h

Go to the documentation of this file.

/*  Copyright (C) 2008 National Institute For Space Research (INPE) - Brazil.

    This file is part of the TerraLib - a Framework for building GIS enabled applications.

    TerraLib 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.

    TerraLib 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.

    You should have received a copy of the GNU Lesser General Public License
    along with TerraLib. See COPYING. If not, write to
    TerraLib Team at <terralib-team@terralib.org>.
 */

 /*!
  \file PolygonSubdivider.h

  \brief Algorithm to subdivide polygons based on a cell tilling and merge them back to their original format

  \ingroup vp
  */

#ifndef __TERRALIB_VP_INTERNAL_POLYGONSUBDIVIDER_H
#define __TERRALIB_VP_INTERNAL_POLYGONSUBDIVIDER_H

// Terralib
#include "Config.h"

#include "../geometry/CommonDataStructures.h"
#include "../geometry/Enums.h"
#include "CommonDataStructures.h"

//STL include files
#include <map>
#include <memory>
#include <set>
#include <vector>

namespace te
{
  namespace gm
  {
    class Envelope;
    class LineString;
  }

  namespace vp
  {
    class SubdividerTilling;

    /*!
      \class PolygonSubdivider

      \brief Algorithm to subdivide polygons based on a cell tilling and merge them back to their original format
    */
    class TEVPEXPORT PolygonSubdivider
    {
      public:

        using SetIndexes = std::set<std::size_t>;
        using GeometryAssociation = std::pair<std::size_t, std::size_t>;
        using GeometryAssociations = std::vector<GeometryAssociation>;
        using ClusterIndexes = std::vector<std::size_t>;
        using Clusters = std::vector<ClusterIndexes>;

        /*!
        * \brief Subdivides the given geometry using the given envelope. This has the same result as an intersection operation, but uses an optimized algorithm which considers an envelope
        *
        * \param geometry The input geometry to be clipped
        * \param envelope The envelope to be used as clipping area
        *
        * \return A geometry vector containing the clipping result
        */
        static te::gm::GeometryVector subdivide(const te::gm::Geometry* geometry, std::size_t maxCoordinates);

        /*!
        * \brief Subdivides the given geometry using the given envelope. This has the same result as an intersection operation, but uses an optimized algorithm which considers an envelope
        *
        * \param geometry The input geometry to be clipped
        * \param envelope The envelope to be used as clipping area
        *
        * \return A geometry vector containing the clipping result
        */
        static te::gm::GeometryVector subdivide(const te::gm::Geometry* geometry, const te::gm::Envelope& envelope, std::size_t maxCoordinates);

        /*!
        * \brief Subdivides the given geometry using the given envelope. This has the same result as an intersection operation, but uses an optimized algorithm which considers an envelope
        *
        * \param geometry The input geometry to be clipped
        * \param envelope The envelope to be used as clipping area
        *
        * \return A geometry vector containing the clipping result
        */
        static te::gm::GeometryVector subdivide(const te::gm::Geometry* geometry, const SubdividerTilling& tilling, std::size_t maxCoordinates);
        
        /*!
        * \brief Subdivides the given vecInputGeometries using the given envelope. This has the same result as an intersection operation, but uses an optimized algorithm which considers an envelope
        *
        * \param vecInputGeometries The input geometries to be clipped
        * \param envelope The envelope to be used as clipping area
        *
        * \return A geometry vector containing the clipping result
        */
        static te::gm::GeometryVector subdivide(const te::gm::GeometryVector& vecInputGeometries, std::size_t maxCoordinates, std::vector<std::size_t>& vecParentIndexes);
        static te::gm::GeometryVector subdivide(const te::gm::GeometryVector& vecInputGeometries, const te::gm::Envelope& envelope, std::size_t maxCoordinates);

        /*!
        * \brief Subdivides the given vecInputGeometries using the given envelope. This has the same result as an intersection operation, but uses an optimized algorithm which considers an envelope
        *
        * \param vecInputGeometries The input geometries to be clipped
        * \param envelope The envelope to be used as clipping area
        *
        * \return A geometry vector containing the clipping result
        */
        static te::gm::GeometryVector subdivide(const te::gm::GeometryVector& vecInputGeometries, const SubdividerTilling& tilling, std::size_t maxCoordinates);

        /*!
          * \brief Creates a normalized match map containing only the indexes of geometries that have a border relation to each other. This analysis is recursive
          *
          * \param vecFragments The vector containing the geometry fragments to be analysed
          * \param splitLine The referente split line where the geomtry fragments must be analysed
          *
          * \return The normalized match map containing only the indexes of geometries that have a border relation to each other
          */
        static GeometryAssociations calculateGeometryAssociations(const te::gm::GeometryVector& vecFragments, const te::gm::LineString* splitLine);

        /*!
          * \brief Normalizes an match map ensuring that all the list of indexes is complete, that is, the list will containg the indexes of all fragments that have borders with the key index
          *
          * \param geometryMatchMap The match map to be normalized
          */
        static Clusters calculateGeometryClusters(const GeometryAssociations& geometryMatchMap);

        /*!
          * \brief Creates a non-normalized match map containing only the indexes of geometries that have a border relation to each other. This analysis is not recursive
          *
          * \param vecBorderSegments The vector containing the border segments to be analysed
          *
          * \return The non-normalized match map containing only the indexes of geometries that have a border relation to each other
          */
        static GeometryAssociations calculateGeometryAssociations(const std::vector<te::vp::SegmentInfo*>& vecBorderSegments, te::gm::Dimensionality dimensionality);

        /*!
         * \brief From the givem geometry, creates a list of all the segments that are exactly in the border of the given split reference line. It also returns the indexes of the geometries that doesnt overlap the given split reference line
         *
         * \param geometry The geometry to be analysed
         * \param geometryIndex The index of the geometry
         * \param splitLine The referente split line where the geomtry fragments must be analysed
         * \param vecSegmentsInBorder (Return parameter) A vector containing all the segments in the border of the given split reference line. f the vector is empty, the given geometry does not share borders with the given split line
         *
         * \return TRUE if at least one segment is in the border. 
         */
        static bool filterSegmentsInBorder(const te::gm::Geometry* geometry, std::size_t geometryIndex, const te::gm::LineString* splitLine, std::vector<te::vp::SegmentInfo*>& vecSegmentsInBorder);

        /*!
         * \brief From the givem geometry vector, creates a list of all the segments that are exactly in the border of the given split reference line. It also returns the indexes of the geometries that doesnt overlap the given split reference line
         *
         * \param vecFragments The vector containing the geometry fragments to be analysed
         * \param splitLine The referente split line where the geomtry fragments must be analysed
         * \param vecIndexesNotInBorder (Return parameter) A return value containing the indexes of the geometries that doesnt overlap the given split reference line
         *
         * \return A vector containing all the segments in the border of the given split reference line
         */
        static std::vector<te::vp::SegmentInfo*> filterSegmentsInBorder(const te::gm::GeometryVector& vecFragments, const te::gm::LineString* splitLine, std::vector<std::size_t>& vecIndexesNotInBorder);

        static bool checkForGeometrySubdivision(const te::gm::Envelope& currentTile, const te::gm::Geometry* geometry, std::size_t geometryIndex, std::vector<te::vp::SegmentInfo*>& vecSegmentsInBorder);

        /*!
          * \brief Dissolves all the geometries from the given fragments vector using the given match map as reference
          *
          * \param vecFragments A vector containing all the candidate fragments to be dissolved
          * \param geometryMatchMap The match map to be be used as reference
          *
          * \return The geometry vector containing the dissolved geometries
          */
        static te::gm::GeometryVector dissolveFragments(const te::gm::GeometryVector& vecFragments, const Clusters& clusters);

        /*!
          * \brief Dissolves all the geometries from the given fragments vector that have borders with the given split reference line
          *
          * \param vecFragments A vector containing all the candidate fragments to be dissolved
          * \param splitLine The split reference line
          *
          * \return The geometry vector containing the dissolved geometries
          */
        static te::gm::GeometryVector merge(const te::gm::GeometryVector& vecFragments, const te::gm::LineString* splitLine);

        /*!
          * \brief Dissolves all the geometries from the given fragments vector that have borders with the given split reference line
          *
          * \param vecFragments A vector containing all the candidate fragments to be dissolved
          * \param splitLine The split reference line
          *
          * \return The geometry vector containing the dissolved geometries
          */
        static te::gm::GeometryVector merge(const te::gm::GeometryVector& vecFragments, const SubdividerTilling& tilling);

        static SetIndexes getUniqueIndexes(const GeometryAssociations& geometryAssociations);
    };
  }
}

#endif //__TERRALIB_VP_INTERNAL_POLYGONSUBDIVIDER_H