30#include "polygonize_polygonizer.h"
41 for (
auto &arc : oArcs)
47IndexedArc RPolygon::newArc(
bool bFollowRighthand)
49 Arc *poArc =
new Arc();
50 std::size_t iArcIndex = oArcs.size();
51 oArcs.push_back(poArc);
52 oArcRighthandFollow.push_back(bFollowRighthand);
53 oArcConnections.push_back(iArcIndex);
54 return IndexedArc{poArc, iArcIndex};
57void RPolygon::setArcConnection(
const IndexedArc &oArc,
58 const IndexedArc &oNextArc)
60 oArcConnections[oArc.iIndex] = oNextArc.iIndex;
63void RPolygon::updateBottomRightPos(IndexType iRow, IndexType iCol)
65 iBottomRightRow = iRow;
66 iBottomRightCol = iCol;
72static void ProcessArmConnections(TwoArm *poCurrent, TwoArm *poAbove,
75 poCurrent->poPolyInside->updateBottomRightPos(poCurrent->iRow,
77 poCurrent->bSolidVertical = poCurrent->poPolyInside != poLeft->poPolyInside;
78 poCurrent->bSolidHorizontal =
79 poCurrent->poPolyInside != poAbove->poPolyInside;
80 poCurrent->poPolyAbove = poAbove->poPolyInside;
81 poCurrent->poPolyLeft = poLeft->poPolyInside;
83 constexpr int BIT_CUR_HORIZ = 0;
84 constexpr int BIT_CUR_VERT = 1;
85 constexpr int BIT_LEFT = 2;
86 constexpr int BIT_ABOVE = 3;
88 const int nArmConnectionType =
89 (
static_cast<int>(poAbove->bSolidVertical) << BIT_ABOVE) |
90 (
static_cast<int>(poLeft->bSolidHorizontal) << BIT_LEFT) |
91 (
static_cast<int>(poCurrent->bSolidVertical) << BIT_CUR_VERT) |
92 (
static_cast<int>(poCurrent->bSolidHorizontal) << BIT_CUR_HORIZ);
94 constexpr int VIRTUAL = 0;
95 constexpr int SOLID = 1;
97 constexpr int ABOVE_VIRTUAL = VIRTUAL << BIT_ABOVE;
98 constexpr int ABOVE_SOLID = SOLID << BIT_ABOVE;
100 constexpr int LEFT_VIRTUAL = VIRTUAL << BIT_LEFT;
101 constexpr int LEFT_SOLID = SOLID << BIT_LEFT;
103 constexpr int CUR_VERT_VIRTUAL = VIRTUAL << BIT_CUR_VERT;
104 constexpr int CUR_VERT_SOLID = SOLID << BIT_CUR_VERT;
106 constexpr int CUR_HORIZ_VIRTUAL = VIRTUAL << BIT_CUR_HORIZ;
107 constexpr int CUR_HORIZ_SOLID = SOLID << BIT_CUR_HORIZ;
135 switch (nArmConnectionType)
137 case ABOVE_VIRTUAL | LEFT_VIRTUAL | CUR_VERT_VIRTUAL |
142 case ABOVE_VIRTUAL | LEFT_VIRTUAL | CUR_VERT_SOLID |
145 poCurrent->oArcVerInner = poCurrent->poPolyInside->newArc(
true);
146 poCurrent->oArcHorInner = poCurrent->poPolyInside->newArc(
false);
147 poCurrent->poPolyInside->setArcConnection(poCurrent->oArcHorInner,
148 poCurrent->oArcVerInner);
149 poCurrent->oArcVerInner.poArc->emplace_back(
150 Point{poCurrent->iRow, poCurrent->iCol});
153 poCurrent->oArcHorOuter = poAbove->poPolyInside->newArc(
true);
154 poCurrent->oArcVerOuter = poAbove->poPolyInside->newArc(
false);
155 poAbove->poPolyInside->setArcConnection(poCurrent->oArcVerOuter,
156 poCurrent->oArcHorOuter);
157 poCurrent->oArcHorOuter.poArc->push_back(
158 Point{poCurrent->iRow, poCurrent->iCol});
161 case ABOVE_VIRTUAL | LEFT_SOLID | CUR_VERT_VIRTUAL |
164 poCurrent->oArcHorInner = poLeft->oArcHorInner;
165 poCurrent->oArcHorOuter = poLeft->oArcHorOuter;
168 case ABOVE_VIRTUAL | LEFT_SOLID | CUR_VERT_SOLID |
171 poCurrent->oArcVerInner = poLeft->oArcHorOuter;
172 poCurrent->oArcVerOuter = poLeft->oArcHorInner;
173 poCurrent->oArcVerInner.poArc->push_back(
174 Point{poCurrent->iRow, poCurrent->iCol});
175 poCurrent->oArcVerOuter.poArc->push_back(
176 Point{poCurrent->iRow, poCurrent->iCol});
179 case ABOVE_VIRTUAL | LEFT_SOLID | CUR_VERT_SOLID |
182 poCurrent->oArcHorOuter = poLeft->oArcHorOuter;
183 poCurrent->oArcVerOuter = poLeft->oArcHorInner;
184 poLeft->oArcHorInner.poArc->push_back(
185 Point{poCurrent->iRow, poCurrent->iCol});
188 poCurrent->oArcVerInner = poCurrent->poPolyInside->newArc(
true);
189 poCurrent->oArcHorInner = poCurrent->poPolyInside->newArc(
false);
190 poCurrent->poPolyInside->setArcConnection(poCurrent->oArcHorInner,
191 poCurrent->oArcVerInner);
192 poCurrent->oArcVerInner.poArc->push_back(
193 Point{poCurrent->iRow, poCurrent->iCol});
196 case ABOVE_SOLID | LEFT_VIRTUAL | CUR_VERT_VIRTUAL |
199 poCurrent->oArcHorOuter = poAbove->oArcVerInner;
200 poCurrent->oArcHorInner = poAbove->oArcVerOuter;
201 poCurrent->oArcHorOuter.poArc->push_back(
202 Point{poCurrent->iRow, poCurrent->iCol});
203 poCurrent->oArcHorInner.poArc->push_back(
204 Point{poCurrent->iRow, poCurrent->iCol});
207 case ABOVE_SOLID | LEFT_VIRTUAL | CUR_VERT_SOLID |
210 poCurrent->oArcVerInner = poAbove->oArcVerInner;
211 poCurrent->oArcVerOuter = poAbove->oArcVerOuter;
214 case ABOVE_SOLID | LEFT_VIRTUAL | CUR_VERT_SOLID |
217 poCurrent->oArcHorOuter = poAbove->oArcVerInner;
218 poCurrent->oArcVerOuter = poAbove->oArcVerOuter;
219 poCurrent->oArcHorOuter.poArc->push_back(
220 Point{poCurrent->iRow, poCurrent->iCol});
222 poCurrent->oArcVerInner = poCurrent->poPolyInside->newArc(
true);
223 poCurrent->oArcHorInner = poCurrent->poPolyInside->newArc(
false);
224 poCurrent->poPolyInside->setArcConnection(poCurrent->oArcHorInner,
225 poCurrent->oArcVerInner);
226 poCurrent->oArcVerInner.poArc->push_back(
227 Point{poCurrent->iRow, poCurrent->iCol});
230 case ABOVE_SOLID | LEFT_SOLID | CUR_VERT_VIRTUAL |
233 poLeft->oArcHorOuter.poArc->push_back(
234 Point{poCurrent->iRow, poCurrent->iCol});
235 poLeft->poPolyAbove->setArcConnection(poLeft->oArcHorOuter,
236 poAbove->oArcVerOuter);
238 poAbove->oArcVerInner.poArc->push_back(
239 Point{poCurrent->iRow, poCurrent->iCol});
240 poCurrent->poPolyInside->setArcConnection(poAbove->oArcVerInner,
241 poLeft->oArcHorInner);
244 case ABOVE_SOLID | LEFT_SOLID | CUR_VERT_VIRTUAL |
247 poLeft->oArcHorOuter.poArc->push_back(
248 Point{poCurrent->iRow, poCurrent->iCol});
249 poLeft->poPolyAbove->setArcConnection(poLeft->oArcHorOuter,
250 poAbove->oArcVerOuter);
252 poCurrent->oArcHorOuter = poAbove->oArcVerInner;
253 poCurrent->oArcHorInner = poLeft->oArcHorInner;
254 poCurrent->oArcHorOuter.poArc->push_back(
255 Point{poCurrent->iRow, poCurrent->iCol});
258 case ABOVE_SOLID | LEFT_SOLID | CUR_VERT_SOLID |
261 poLeft->oArcHorOuter.poArc->push_back(
262 Point{poCurrent->iRow, poCurrent->iCol});
263 poLeft->poPolyAbove->setArcConnection(poLeft->oArcHorOuter,
264 poAbove->oArcVerOuter);
266 poCurrent->oArcVerInner = poAbove->oArcVerInner;
267 poCurrent->oArcVerOuter = poLeft->oArcHorInner;
268 poCurrent->oArcVerOuter.poArc->push_back(
269 Point{poCurrent->iRow, poCurrent->iCol});
272 case ABOVE_SOLID | LEFT_SOLID | CUR_VERT_SOLID | CUR_HORIZ_SOLID:
274 if (poAbove->poPolyLeft == poCurrent->poPolyInside)
277 poCurrent->oArcVerInner = poLeft->oArcHorOuter;
278 poCurrent->oArcHorInner = poAbove->oArcVerOuter;
279 poCurrent->oArcVerInner.poArc->push_back(
280 Point{poCurrent->iRow, poCurrent->iCol});
281 poCurrent->oArcHorInner.poArc->push_back(
282 Point{poCurrent->iRow, poCurrent->iCol});
287 poLeft->oArcHorOuter.poArc->push_back(
288 Point{poCurrent->iRow, poCurrent->iCol});
289 poLeft->poPolyAbove->setArcConnection(poLeft->oArcHorOuter,
290 poAbove->oArcVerOuter);
292 poCurrent->oArcVerInner = poCurrent->poPolyInside->newArc(
true);
293 poCurrent->oArcHorInner =
294 poCurrent->poPolyInside->newArc(
false);
295 poCurrent->poPolyInside->setArcConnection(
296 poCurrent->oArcHorInner, poCurrent->oArcVerInner);
297 poCurrent->oArcVerInner.poArc->push_back(
298 Point{poCurrent->iRow, poCurrent->iCol});
302 if (poAbove->poPolyInside == poLeft->poPolyInside)
305 poAbove->poPolyInside->setArcConnection(poAbove->oArcVerInner,
306 poLeft->oArcHorInner);
307 poAbove->oArcVerInner.poArc->push_back(
308 Point{poCurrent->iRow, poCurrent->iCol});
310 poCurrent->oArcHorOuter = poAbove->poPolyInside->newArc(
true);
311 poCurrent->oArcVerOuter = poAbove->poPolyInside->newArc(
false);
312 poCurrent->oArcHorOuter.poArc->push_back(
313 Point{poCurrent->iRow, poCurrent->iCol});
314 poAbove->poPolyInside->setArcConnection(
315 poCurrent->oArcVerOuter, poCurrent->oArcHorOuter);
320 poCurrent->oArcHorOuter = poAbove->oArcVerInner;
321 poCurrent->oArcVerOuter = poLeft->oArcHorInner;
322 poCurrent->oArcHorOuter.poArc->push_back(
323 Point{poCurrent->iRow, poCurrent->iCol});
324 poCurrent->oArcVerOuter.poArc->push_back(
325 Point{poCurrent->iRow, poCurrent->iCol});
330 case ABOVE_VIRTUAL | LEFT_VIRTUAL | CUR_VERT_VIRTUAL |
332 case ABOVE_VIRTUAL | LEFT_VIRTUAL | CUR_VERT_SOLID |
334 case ABOVE_VIRTUAL | LEFT_SOLID | CUR_VERT_VIRTUAL |
343template <
typename PolyIdType,
typename DataType>
344Polygonizer<PolyIdType, DataType>::Polygonizer(
345 PolyIdType nInvalidPolyId, PolygonReceiver<DataType> *poPolygonReceiver)
346 : nInvalidPolyId_(nInvalidPolyId), poPolygonReceiver_(poPolygonReceiver)
348 poTheOuterPolygon_ = createPolygon(THE_OUTER_POLYGON_ID);
351template <
typename PolyIdType,
typename DataType>
352Polygonizer<PolyIdType, DataType>::~Polygonizer()
355 for (
auto &pair : oPolygonMap_)
361template <
typename PolyIdType,
typename DataType>
362RPolygon *Polygonizer<PolyIdType, DataType>::getPolygon(PolyIdType nPolygonId)
364 if (oPolygonMap_.count(nPolygonId) == 0)
366 return createPolygon(nPolygonId);
370 return oPolygonMap_[nPolygonId];
374template <
typename PolyIdType,
typename DataType>
376Polygonizer<PolyIdType, DataType>::createPolygon(PolyIdType nPolygonId)
378 auto polygon =
new RPolygon();
379 oPolygonMap_[nPolygonId] = polygon;
383template <
typename PolyIdType,
typename DataType>
384void Polygonizer<PolyIdType, DataType>::destroyPolygon(PolyIdType nPolygonId)
386 delete oPolygonMap_[nPolygonId];
387 oPolygonMap_.erase(nPolygonId);
390template <
typename PolyIdType,
typename DataType>
391void Polygonizer<PolyIdType, DataType>::processLine(
392 const PolyIdType *panThisLineId,
const DataType *panLastLineVal,
393 TwoArm *poThisLineArm, TwoArm *poLastLineArm,
const IndexType nCurrentRow,
394 const IndexType nCols)
396 TwoArm *poCurrent, *poAbove, *poLeft;
398 poCurrent = poThisLineArm + 1;
399 poCurrent->iRow = nCurrentRow;
401 poCurrent->poPolyInside = getPolygon(panThisLineId[0]);
402 poAbove = poLastLineArm + 1;
403 poLeft = poThisLineArm;
404 poLeft->poPolyInside = poTheOuterPolygon_;
405 ProcessArmConnections(poCurrent, poAbove, poLeft);
406 for (IndexType col = 1; col < nCols; ++col)
408 IndexType iArmIndex = col + 1;
409 poCurrent = poThisLineArm + iArmIndex;
410 poCurrent->iRow = nCurrentRow;
411 poCurrent->iCol = col;
412 poCurrent->poPolyInside = getPolygon(panThisLineId[col]);
413 poAbove = poLastLineArm + iArmIndex;
414 poLeft = poThisLineArm + iArmIndex - 1;
415 ProcessArmConnections(poCurrent, poAbove, poLeft);
417 poCurrent = poThisLineArm + nCols + 1;
418 poCurrent->iRow = nCurrentRow;
419 poCurrent->iCol = nCols;
420 poCurrent->poPolyInside = poTheOuterPolygon_;
421 poAbove = poLastLineArm + nCols + 1;
422 poAbove->poPolyInside = poTheOuterPolygon_;
423 poLeft = poThisLineArm + nCols;
424 ProcessArmConnections(poCurrent, poAbove, poLeft);
431 std::vector<PolygonMapEntry> oCompletedPolygons;
432 for (
auto &entry : oPolygonMap_)
434 RPolygon *poPolygon = entry.second;
436 if (poPolygon->iBottomRightRow + 1 == nCurrentRow)
438 oCompletedPolygons.push_back(entry);
442 for (
auto &entry : oCompletedPolygons)
444 PolyIdType nPolyId = entry.first;
445 RPolygon *poPolygon = entry.second;
448 if (nPolyId != nInvalidPolyId_)
450 poPolygonReceiver_->receive(
451 poPolygon, panLastLineVal[poPolygon->iBottomRightCol]);
454 destroyPolygon(nPolyId);
458template <
typename DataType>
459OGRPolygonWriter<DataType>::OGRPolygonWriter(
OGRLayerH hOutLayer,
461 double *padfGeoTransform)
462 : PolygonReceiver<DataType>(), hOutLayer_(hOutLayer),
463 iPixValField_(iPixValField), padfGeoTransform_(padfGeoTransform)
467template <
typename DataType>
468void OGRPolygonWriter<DataType>::receive(RPolygon *poPolygon,
469 DataType nPolygonCellValue)
471 std::vector<bool> oAccessedArc(poPolygon->oArcConnections.size(),
false);
472 double *padfGeoTransform = padfGeoTransform_;
476 auto AddRingToPolygon = [&poPolygon, &oAccessedArc, &hPolygon,
477 padfGeoTransform](std::size_t iFirstArcIndex)
482 [&poPolygon, &hRing, padfGeoTransform](std::size_t iArcIndex)
484 auto oArc = poPolygon->oArcs[iArcIndex];
485 bool bArcFollowRighthand =
486 poPolygon->oArcRighthandFollow[iArcIndex];
487 for (std::size_t i = 0; i < oArc->size(); ++i)
489 const Point &oPixel =
490 (*oArc)[bArcFollowRighthand ? i : (oArc->size() - i - 1)];
492 const double dfX = padfGeoTransform[0] +
493 oPixel[1] * padfGeoTransform[1] +
494 oPixel[0] * padfGeoTransform[2];
495 const double dfY = padfGeoTransform[3] +
496 oPixel[1] * padfGeoTransform[4] +
497 oPixel[0] * padfGeoTransform[5];
499 OGR_G_AddPoint_2D(hRing, dfX, dfY);
503 AddArcToRing(iFirstArcIndex);
505 std::size_t iArcIndex = iFirstArcIndex;
506 std::size_t iNextArcIndex = poPolygon->oArcConnections[iArcIndex];
507 oAccessedArc[iArcIndex] =
true;
508 while (iNextArcIndex != iFirstArcIndex)
510 AddArcToRing(iNextArcIndex);
511 iArcIndex = iNextArcIndex;
512 iNextArcIndex = poPolygon->oArcConnections[iArcIndex];
513 oAccessedArc[iArcIndex] =
true;
517 OGR_G_AddPoint_2D(hRing, OGR_G_GetX(hRing, 0), OGR_G_GetY(hRing, 0));
519 OGR_G_AddGeometryDirectly(hPolygon, hRing);
522 std::vector<bool>::iterator ite;
523 while ((ite = std::find_if_not(oAccessedArc.begin(), oAccessedArc.end(),
524 [](
bool accessed) { return accessed; })) !=
527 AddRingToPolygon(ite - oAccessedArc.begin());
535 if (iPixValField_ >= 0)
537 static_cast<double>(nPolygonCellValue));
#define CPLAssert(expr)
Assert on an expression.
Definition cpl_error.h:216
OGRFeatureH OGR_F_Create(OGRFeatureDefnH)
Feature factory.
Definition ogrfeature.cpp:132
void * OGRGeometryH
Opaque type for a geometry.
Definition ogr_api.h:66
void OGR_F_Destroy(OGRFeatureH)
Destroy feature.
Definition ogrfeature.cpp:224
OGRErr OGR_L_CreateFeature(OGRLayerH, OGRFeatureH)
Create and write a new feature within a layer.
Definition ogrlayer.cpp:803
OGRGeometryH OGR_G_CreateGeometry(OGRwkbGeometryType)
Create an empty geometry of desired type.
Definition ogrgeometryfactory.cpp:660
void * OGRLayerH
Opaque type for a layer (OGRLayer)
Definition ogr_api.h:688
OGRFeatureDefnH OGR_L_GetLayerDefn(OGRLayerH)
Fetch the schema information for this layer.
Definition ogrlayer.cpp:1322
void OGR_F_SetFieldDouble(OGRFeatureH, int, double)
Set field to double value.
Definition ogrfeature.cpp:4116
void * OGRFeatureH
Opaque type for a feature (OGRFeature)
Definition ogr_api.h:422
OGRErr OGR_F_SetGeometryDirectly(OGRFeatureH, OGRGeometryH)
Set feature geometry.
Definition ogrfeature.cpp:505
#define OGRERR_NONE
Success.
Definition ogr_core.h:389
@ wkbPolygon
planar 2-dimensional geometric object defined by 1 exterior boundary and 0 or more interior boundarie...
Definition ogr_core.h:422
@ wkbLinearRing
non-standard, just for createGeometry()
Definition ogr_core.h:455