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 * 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
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
45namespace gdal
46{
47namespace polygonizer
48{
49
50using IndexType = std::uint32_t;
51using Point = std::array<IndexType, 2>;
52using Arc = std::vector<Point>;
53
54struct IndexedArc
55{
56 Arc *poArc;
57 std::size_t iIndex;
58};
59
66struct 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 RPolygon() = default;
78
79 RPolygon(const RPolygon &) = delete;
80
81 RPolygon &operator=(const RPolygon &) = delete;
82
83 ~RPolygon();
84
88 IndexedArc newArc(bool bFollowRighthand);
89
93 void setArcConnection(const IndexedArc &oArc, const IndexedArc &oNextArc);
94
98 void updateBottomRightPos(IndexType iRow, IndexType iCol);
99};
100
104struct 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
122template <typename DataType> class PolygonReceiver
123{
124 public:
125 PolygonReceiver() = default;
126
127 PolygonReceiver(const PolygonReceiver<DataType> &) = delete;
128
129 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
140template <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 RPolygon *getTheOuterPolygon() const
174 {
175 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
187template <typename DataType>
188class 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 ~OGRPolygonWriter() = default;
203
204 OGRPolygonWriter<DataType> &
205 operator=(const OGRPolygonWriter<DataType> &) = delete;
206
207 void receive(RPolygon *poPolygon, DataType nPolygonCellValue) override;
208
209 inline CPLErr getErr()
210 {
211 return eErr_;
212 }
213};
214
215} // namespace polygonizer
216} // namespace gdal
217
220#endif /* POLYGONIZE_POLYGONIZER_H_INCLUDED */
cpl_error.h
CPL error handling services.
CPLErr
CPLErr
Error category.
Definition: cpl_error.h:53
ogr_api.h
C API and defines for OGRFeature, OGRGeometry, and OGRDataSource related classes.
OGRLayerH
void * OGRLayerH
Opaque type for a layer (OGRLayer)
Definition: ogr_api.h:688