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             :  * SPDX-License-Identifier: MIT
      10             :  ****************************************************************************/
      11             : 
      12             : #ifndef POLYGONIZE_POLYGONIZER_H_INCLUDED
      13             : #define POLYGONIZE_POLYGONIZER_H_INCLUDED
      14             : 
      15             : /*! @cond Doxygen_Suppress */
      16             : 
      17             : // Implements Junhua Teng, Fahui Wang, Yu Liu: An Efficient Algorithm for
      18             : // Raster-to-Vector Data Conversion: https://doi.org/10.1080/10824000809480639
      19             : 
      20             : #include <array>
      21             : #include <cstdint>
      22             : #include <vector>
      23             : #include <limits>
      24             : #include <map>
      25             : 
      26             : #include "cpl_error.h"
      27             : #include "ogr_api.h"
      28             : #include "ogr_geometry.h"
      29             : #include "ogrsf_frmts.h"
      30             : 
      31             : namespace gdal
      32             : {
      33             : namespace polygonizer
      34             : {
      35             : 
      36             : using IndexType = std::uint32_t;
      37             : using Point = std::array<IndexType, 2>;
      38             : using Arc = std::vector<Point>;
      39             : 
      40             : struct IndexedArc
      41             : {
      42             :     Arc *poArc;
      43             :     std::size_t iIndex;
      44             : };
      45             : 
      46             : /**
      47             :  * A raster polygon(RPolygon) is formed by a list of arcs in order.
      48             :  * Each arc has two properties:
      49             :  *     1. does the arc follows the right-hand rule respect to the area it bounds
      50             :  *     2. the next arc of the current arc
      51             :  */
      52             : struct RPolygon
      53             : {
      54             :     IndexType iBottomRightRow{0};
      55             :     IndexType iBottomRightCol{0};
      56             : 
      57             :     struct ArcStruct
      58             :     {
      59             :         std::unique_ptr<Arc> poArc{};
      60             :         // each element is the next arc index of the current arc
      61             :         unsigned nConnection = 0;
      62             :         // does arc follows the right-hand rule with
      63             :         bool bFollowRighthand = false;
      64             : 
      65       35990 :         ArcStruct(unsigned nConnectionIn, bool bFollowRighthandIn)
      66       35990 :             : poArc(std::make_unique<Arc>()), nConnection(nConnectionIn),
      67       35990 :               bFollowRighthand(bFollowRighthandIn)
      68             :         {
      69       35990 :         }
      70             :     };
      71             : 
      72             :     // arc object list
      73             :     std::vector<ArcStruct> oArcs{};
      74             : 
      75        3639 :     RPolygon() = default;
      76             : 
      77             :     RPolygon(const RPolygon &) = delete;
      78             : 
      79             :     RPolygon &operator=(const RPolygon &) = delete;
      80             : 
      81             :     /**
      82             :      * create a new arc object
      83             :      */
      84             :     IndexedArc newArc(bool bFollowRighthand);
      85             : 
      86             :     /**
      87             :      * set the next arc index of the current arc
      88             :      */
      89             :     void setArcConnection(const IndexedArc &oArc, const IndexedArc &oNextArc);
      90             : 
      91             :     /**
      92             :      * update the bottom-right most cell index of the current polygon
      93             :      */
      94             :     void updateBottomRightPos(IndexType iRow, IndexType iCol);
      95             : };
      96             : 
      97             : /**
      98             :  * Arm class is used to record the tracings of both arcs and polygons.
      99             :  */
     100             : struct TwoArm
     101             : {
     102             :     IndexType iRow{0};
     103             :     IndexType iCol{0};
     104             : 
     105             :     RPolygon *poPolyInside{nullptr};
     106             :     RPolygon *poPolyAbove{nullptr};
     107             :     RPolygon *poPolyLeft{nullptr};
     108             : 
     109             :     IndexedArc oArcHorOuter{};
     110             :     IndexedArc oArcHorInner{};
     111             :     IndexedArc oArcVerInner{};
     112             :     IndexedArc oArcVerOuter{};
     113             : 
     114             :     bool bSolidHorizontal{false};
     115             :     bool bSolidVertical{false};
     116             : };
     117             : 
     118             : template <typename DataType> class PolygonReceiver
     119             : {
     120             :   public:
     121          52 :     PolygonReceiver() = default;
     122             : 
     123             :     PolygonReceiver(const PolygonReceiver<DataType> &) = delete;
     124             : 
     125          52 :     virtual ~PolygonReceiver() = default;
     126             : 
     127             :     PolygonReceiver<DataType> &
     128             :     operator=(const PolygonReceiver<DataType> &) = delete;
     129             : 
     130             :     virtual void receive(RPolygon *poPolygon, DataType nPolygonCellValue) = 0;
     131             : };
     132             : 
     133             : /**
     134             :  * Polygonizer is used to manage polygon memory and do the edge tracing process
     135             :  */
     136             : template <typename PolyIdType, typename DataType> class Polygonizer
     137             : {
     138             :   public:
     139             :     static constexpr PolyIdType THE_OUTER_POLYGON_ID =
     140             :         std::numeric_limits<PolyIdType>::max();
     141             : 
     142             :   private:
     143             :     using PolygonMap = std::map<PolyIdType, RPolygon *>;
     144             :     using PolygonMapEntry = typename PolygonMap::value_type;
     145             : 
     146             :     PolyIdType nInvalidPolyId_;
     147             :     RPolygon *poTheOuterPolygon_{nullptr};
     148             :     PolygonMap oPolygonMap_{};
     149             : 
     150             :     PolygonReceiver<DataType> *poPolygonReceiver_;
     151             : 
     152             :     RPolygon *getPolygon(PolyIdType nPolygonId);
     153             : 
     154             :     RPolygon *createPolygon(PolyIdType nPolygonId);
     155             : 
     156             :     void destroyPolygon(PolyIdType nPolygonId);
     157             : 
     158             :   public:
     159             :     explicit Polygonizer(PolyIdType nInvalidPolyId,
     160             :                          PolygonReceiver<DataType> *poPolygonReceiver);
     161             : 
     162             :     Polygonizer(const Polygonizer<PolyIdType, DataType> &) = delete;
     163             : 
     164             :     ~Polygonizer();
     165             : 
     166             :     Polygonizer<PolyIdType, DataType> &
     167             :     operator=(const Polygonizer<PolyIdType, DataType> &) = delete;
     168             : 
     169        1200 :     RPolygon *getTheOuterPolygon() const
     170             :     {
     171        1200 :         return poTheOuterPolygon_;
     172             :     }
     173             : 
     174             :     bool processLine(const PolyIdType *panThisLineId,
     175             :                      const DataType *panLastLineVal, TwoArm *poThisLineArm,
     176             :                      TwoArm *poLastLineArm, IndexType nCurrentRow,
     177             :                      IndexType nCols);
     178             : };
     179             : 
     180             : /**
     181             :  * Write raster polygon object to OGR layer.
     182             :  */
     183             : template <typename DataType>
     184             : class OGRPolygonWriter : public PolygonReceiver<DataType>
     185             : {
     186             :     OGRLayer *poOutLayer_ = nullptr;
     187             :     int iPixValField_;
     188             :     double *padfGeoTransform_;
     189             :     std::unique_ptr<OGRFeature> poFeature_{};
     190             :     OGRPolygon *poPolygon_ =
     191             :         nullptr;  // = poFeature_->GetGeometryRef(), owned by poFeature
     192             : 
     193             :     CPLErr eErr_{CE_None};
     194             : 
     195             :   public:
     196             :     OGRPolygonWriter(OGRLayerH hOutLayer, int iPixValField,
     197             :                      double *padfGeoTransform);
     198             : 
     199             :     OGRPolygonWriter(const OGRPolygonWriter<DataType> &) = delete;
     200             : 
     201          52 :     ~OGRPolygonWriter() = default;
     202             : 
     203             :     OGRPolygonWriter<DataType> &
     204             :     operator=(const OGRPolygonWriter<DataType> &) = delete;
     205             : 
     206             :     void receive(RPolygon *poPolygon, DataType nPolygonCellValue) override;
     207             : 
     208        1490 :     inline CPLErr getErr()
     209             :     {
     210        1490 :         return eErr_;
     211             :     }
     212             : };
     213             : 
     214             : }  // namespace polygonizer
     215             : }  // namespace gdal
     216             : 
     217             : /*! @endcond */
     218             : 
     219             : #endif /* POLYGONIZE_POLYGONIZER_H_INCLUDED */