Line data    Source code

       1             : /******************************************************************************
       2             :  * Project:  GDAL
       3             :  * Purpose:  Implements The Two-Arm Chains EdgeTracing Algorithm
       4             :  * Author:   kikitte.lee
       5             :  *
       6             :  ******************************************************************************
       7             :  * Copyright (c) 2023, kikitte.lee <kikitte.lee@gmail.com>
       8             :  *
       9             :  * Permission is hereby granted, free of charge, to any person obtaining a
      10             :  * copy of this software and associated documentation files (the "Software"),
      11             :  * to deal in the Software without restriction, including without limitation
      12             :  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
      13             :  * and/or sell copies of the Software, and to permit persons to whom the
      14             :  * Software is furnished to do so, subject to the following conditions:
      15             :  *
      16             :  * The above copyright notice and this permission notice shall be included
      17             :  * in all copies or substantial portions of the Software.
      18             :  *
      19             :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
      20             :  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      21             :  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
      22             :  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      23             :  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
      24             :  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
      25             :  * DEALINGS IN THE SOFTWARE.
      26             :  ****************************************************************************/
      27             : 
      28             : #ifndef POLYGONIZE_POLYGONIZER_H_INCLUDED
      29             : #define POLYGONIZE_POLYGONIZER_H_INCLUDED
      30             : 
      31             : /*! @cond Doxygen_Suppress */
      32             : 
      33             : // Implements Junhua Teng, Fahui Wang, Yu Liu: An Efficient Algorithm for
      34             : // Raster-to-Vector Data Conversion: https://doi.org/10.1080/10824000809480639
      35             : 
      36             : #include <array>
      37             : #include <cstdint>
      38             : #include <vector>
      39             : #include <limits>
      40             : #include <map>
      41             : 
      42             : #include "cpl_error.h"
      43             : #include "ogr_api.h"
      44             : 
      45             : namespace gdal
      46             : {
      47             : namespace polygonizer
      48             : {
      49             : 
      50             : using IndexType = std::uint32_t;
      51             : using Point = std::array<IndexType, 2>;
      52             : using Arc = std::vector<Point>;
      53             : 
      54             : struct IndexedArc
      55             : {
      56             :     Arc *poArc;
      57             :     std::size_t iIndex;
      58             : };
      59             : 
      60             : /**
      61             :  * A raster polygon(RPolygon) is formed by a list of arcs in order.
      62             :  * Each arc has two properties:
      63             :  *     1. does the arc follows the right-hand rule respect to the area it bounds
      64             :  *     2. the next arc of the current arc
      65             :  */
      66             : struct RPolygon
      67             : {
      68             :     IndexType iBottomRightRow{0};
      69             :     IndexType iBottomRightCol{0};
      70             :     // arc object list
      71             :     std::vector<Arc *> oArcs{};
      72             :     // does arc follows the right-hand rule with
      73             :     std::vector<bool> oArcRighthandFollow{};
      74             :     // each element is the next arc index of the current arc
      75             :     std::vector<std::size_t> oArcConnections{};
      76             : 
      77        3639 :     RPolygon() = default;
      78             : 
      79             :     RPolygon(const RPolygon &) = delete;
      80             : 
      81             :     RPolygon &operator=(const RPolygon &) = delete;
      82             : 
      83             :     ~RPolygon();
      84             : 
      85             :     /**
      86             :      * create a new arc object
      87             :      */
      88             :     IndexedArc newArc(bool bFollowRighthand);
      89             : 
      90             :     /**
      91             :      * set the next arc index of the current arc
      92             :      */
      93             :     void setArcConnection(const IndexedArc &oArc, const IndexedArc &oNextArc);
      94             : 
      95             :     /**
      96             :      * update the bottom-right most cell index of the current polygon
      97             :      */
      98             :     void updateBottomRightPos(IndexType iRow, IndexType iCol);
      99             : };
     100             : 
     101             : /**
     102             :  * Arm class is used to record the tracings of both arcs and polygons.
     103             :  */
     104             : struct TwoArm
     105             : {
     106             :     IndexType iRow{0};
     107             :     IndexType iCol{0};
     108             : 
     109             :     RPolygon *poPolyInside{nullptr};
     110             :     RPolygon *poPolyAbove{nullptr};
     111             :     RPolygon *poPolyLeft{nullptr};
     112             : 
     113             :     IndexedArc oArcHorOuter{};
     114             :     IndexedArc oArcHorInner{};
     115             :     IndexedArc oArcVerInner{};
     116             :     IndexedArc oArcVerOuter{};
     117             : 
     118             :     bool bSolidHorizontal{false};
     119             :     bool bSolidVertical{false};
     120             : };
     121             : 
     122             : template <typename DataType> class PolygonReceiver
     123             : {
     124             :   public:
     125          52 :     PolygonReceiver() = default;
     126             : 
     127             :     PolygonReceiver(const PolygonReceiver<DataType> &) = delete;
     128             : 
     129          52 :     virtual ~PolygonReceiver() = default;
     130             : 
     131             :     PolygonReceiver<DataType> &
     132             :     operator=(const PolygonReceiver<DataType> &) = delete;
     133             : 
     134             :     virtual void receive(RPolygon *poPolygon, DataType nPolygonCellValue) = 0;
     135             : };
     136             : 
     137             : /**
     138             :  * Polygonizer is used to manage polygon memory and do the edge tracing process
     139             :  */
     140             : template <typename PolyIdType, typename DataType> class Polygonizer
     141             : {
     142             :   public:
     143             :     static constexpr PolyIdType THE_OUTER_POLYGON_ID =
     144             :         std::numeric_limits<PolyIdType>::max();
     145             : 
     146             :   private:
     147             :     using PolygonMap = std::map<PolyIdType, RPolygon *>;
     148             :     using PolygonMapEntry = typename PolygonMap::value_type;
     149             : 
     150             :     PolyIdType nInvalidPolyId_;
     151             :     RPolygon *poTheOuterPolygon_{nullptr};
     152             :     PolygonMap oPolygonMap_{};
     153             : 
     154             :     PolygonReceiver<DataType> *poPolygonReceiver_;
     155             : 
     156             :     RPolygon *getPolygon(PolyIdType nPolygonId);
     157             : 
     158             :     RPolygon *createPolygon(PolyIdType nPolygonId);
     159             : 
     160             :     void destroyPolygon(PolyIdType nPolygonId);
     161             : 
     162             :   public:
     163             :     explicit Polygonizer(PolyIdType nInvalidPolyId,
     164             :                          PolygonReceiver<DataType> *poPolygonReceiver);
     165             : 
     166             :     Polygonizer(const Polygonizer<PolyIdType, DataType> &) = delete;
     167             : 
     168             :     ~Polygonizer();
     169             : 
     170             :     Polygonizer<PolyIdType, DataType> &
     171             :     operator=(const Polygonizer<PolyIdType, DataType> &) = delete;
     172             : 
     173        1200 :     RPolygon *getTheOuterPolygon() const
     174             :     {
     175        1200 :         return poTheOuterPolygon_;
     176             :     }
     177             : 
     178             :     void processLine(const PolyIdType *panThisLineId,
     179             :                      const DataType *panLastLineVal, TwoArm *poThisLineArm,
     180             :                      TwoArm *poLastLineArm, IndexType nCurrentRow,
     181             :                      IndexType nCols);
     182             : };
     183             : 
     184             : /**
     185             :  * Write raster polygon object to OGR layer.
     186             :  */
     187             : template <typename DataType>
     188             : class OGRPolygonWriter : public PolygonReceiver<DataType>
     189             : {
     190             :     OGRLayerH hOutLayer_;
     191             :     int iPixValField_;
     192             :     double *padfGeoTransform_;
     193             : 
     194             :     CPLErr eErr_{CE_None};
     195             : 
     196             :   public:
     197             :     OGRPolygonWriter(OGRLayerH hOutLayer, int iPixValField,
     198             :                      double *padfGeoTransform);
     199             : 
     200             :     OGRPolygonWriter(const OGRPolygonWriter<DataType> &) = delete;
     201             : 
     202          52 :     ~OGRPolygonWriter() = default;
     203             : 
     204             :     OGRPolygonWriter<DataType> &
     205             :     operator=(const OGRPolygonWriter<DataType> &) = delete;
     206             : 
     207             :     void receive(RPolygon *poPolygon, DataType nPolygonCellValue) override;
     208             : 
     209        1490 :     inline CPLErr getErr()
     210             :     {
     211        1490 :         return eErr_;
     212             :     }
     213             : };
     214             : 
     215             : }  // namespace polygonizer
     216             : }  // namespace gdal
     217             : 
     218             : /*! @endcond */
     219             : 
     220             : #endif /* POLYGONIZE_POLYGONIZER_H_INCLUDED */