GDAL

polygonize_polygonizer.h
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
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
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 ArcStruct(unsigned nConnectionIn, bool bFollowRighthandIn)
66 : poArc(std::make_unique<Arc>()), nConnection(nConnectionIn),
67 bFollowRighthand(bFollowRighthandIn)
68 {
69 }
70 };
71
72 // arc object list
73 std::vector<ArcStruct> oArcs{};
74
75 RPolygon() = default;
76
77 RPolygon(const RPolygon &) = delete;
78
79 RPolygon &operator=(const RPolygon &) = delete;
80
84 IndexedArc newArc(bool bFollowRighthand);
85
89 void setArcConnection(const IndexedArc &oArc, const IndexedArc &oNextArc);
90
94 void updateBottomRightPos(IndexType iRow, IndexType iCol);
95};
96
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 PolygonReceiver() = default;
122
123 PolygonReceiver(const PolygonReceiver<DataType> &) = delete;
124
125 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
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 RPolygon *getTheOuterPolygon() const
170 {
171 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
183 template <typename DataType>
184 class OGRPolygonWriter : public PolygonReceiver<DataType>
185{
186 OGRLayer *poOutLayer_ = nullptr;
187 GDALDataset *poOutDS_ = nullptr;
188 const int iPixValField_;
189 const GDALGeoTransform gt_;
190 int nCommitInterval_ = 0;
191 GIntBig nFeaturesWrittenInTransaction_ = 0;
192 std::unique_ptr<OGRFeature> poFeature_{};
193 OGRPolygon *poPolygon_ =
194 nullptr; // = poFeature_->GetGeometryRef(), owned by poFeature
195
196 CPLErr eErr_{CE_None};
197
198 public:
199 OGRPolygonWriter(OGRLayerH hOutLayer, int iPixValField,
200 const GDALGeoTransform &gt, int nCommitInterval);
201 ~OGRPolygonWriter() override;
202
203 OGRPolygonWriter(const OGRPolygonWriter<DataType> &) = delete;
204
205 OGRPolygonWriter<DataType> &
206 operator=(const OGRPolygonWriter<DataType> &) = delete;
207
208 bool Finalize();
209
210 void receive(RPolygon *poPolygon, DataType nPolygonCellValue) override;
211
212 inline CPLErr getErr()
213 {
214 return eErr_;
215 }
216};
217
218} // namespace polygonizer
219} // namespace gdal
220
223#endif /* POLYGONIZE_POLYGONIZER_H_INCLUDED */
GDALDataset
A set of associated raster bands, usually from one file.
Definition gdal_dataset.h:76
GDALGeoTransform
Class that encapsulates a geotransform matrix.
Definition gdal_geotransform.h:42
OGRLayer
This class represents a layer of simple features, with access methods.
Definition ogrsf_frmts.h:61
OGRPolygon
Concrete class representing polygons.
Definition ogr_geometry.h:2635
cpl_error.h
CPL error handling services.
CPLErr
CPLErr
Error category.
Definition cpl_error.h:37
GIntBig
long long GIntBig
Large signed integer type (generally 64-bit integer type).
Definition cpl_port.h:205
OGRLayerH
void * OGRLayerH
Opaque type for a layer (OGRLayer)
Definition gdal_fwd.h:157
ogr_api.h
C API and defines for OGRFeature, OGRGeometry, and OGRDataSource related classes.
ogr_geometry.h
Simple feature geometry classes.
ogrsf_frmts.h
Classes related to registration of format support, and opening datasets.