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
31namespace gdal
32{
33namespace polygonizer
34{
35
36using IndexType = std::uint32_t;
37using Point = std::array<IndexType, 2>;
38using Arc = std::vector<Point>;
39
40struct IndexedArc
41{
42 Arc *poArc;
43 std::size_t iIndex;
44};
45
52struct 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
100struct 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
118template <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
136template <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
183template <typename DataType>
184class 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 ~OGRPolygonWriter() = default;
202
203 OGRPolygonWriter<DataType> &
204 operator=(const OGRPolygonWriter<DataType> &) = delete;
205
206 void receive(RPolygon *poPolygon, DataType nPolygonCellValue) override;
207
208 inline CPLErr getErr()
209 {
210 return eErr_;
211 }
212};
213
214} // namespace polygonizer
215} // namespace gdal
216
219#endif /* POLYGONIZE_POLYGONIZER_H_INCLUDED */
This class represents a layer of simple features, with access methods.
Definition: ogrsf_frmts.h:58
Concrete class representing polygons.
Definition: ogr_geometry.h:2660
CPL error handling services.
CPLErr
Error category.
Definition: cpl_error.h:37
C API and defines for OGRFeature, OGRGeometry, and OGRDataSource related classes.
void * OGRLayerH
Opaque type for a layer (OGRLayer)
Definition: ogr_api.h:676
Simple feature geometry classes.
Classes related to registration of format support, and opening datasets.