1 : /******************************************************************************
2 : * $Id: gdalrasterpolygonenumerator.cpp 18523 2010-01-11 18:12:25Z mloskot $
3 : *
4 : * Project: GDAL
5 : * Purpose: Raster Polygon Enumerator
6 : * Author: Frank Warmerdam, warmerdam@pobox.com
7 : *
8 : ******************************************************************************
9 : * Copyright (c) 2008, Frank Warmerdam
10 : *
11 : * Permission is hereby granted, free of charge, to any person obtaining a
12 : * copy of this software and associated documentation files (the "Software"),
13 : * to deal in the Software without restriction, including without limitation
14 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15 : * and/or sell copies of the Software, and to permit persons to whom the
16 : * Software is furnished to do so, subject to the following conditions:
17 : *
18 : * The above copyright notice and this permission notice shall be included
19 : * in all copies or substantial portions of the Software.
20 : *
21 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 : * DEALINGS IN THE SOFTWARE.
28 : ****************************************************************************/
29 :
30 : #include "gdal_alg_priv.h"
31 : #include "cpl_conv.h"
32 : #include <vector>
33 :
34 : CPL_CVSID("$Id: gdalrasterpolygonenumerator.cpp 18523 2010-01-11 18:12:25Z mloskot $");
35 :
36 : /************************************************************************/
37 : /* GDALRasterPolygonEnumerator() */
38 : /************************************************************************/
39 :
40 : GDALRasterPolygonEnumerator::GDALRasterPolygonEnumerator(
41 24 : int nConnectedness )
42 :
43 : {
44 24 : panPolyIdMap = NULL;
45 24 : panPolyValue = NULL;
46 24 : nNextPolygonId = 0;
47 24 : nPolyAlloc = 0;
48 24 : this->nConnectedness = nConnectedness;
49 24 : CPLAssert( nConnectedness == 4 || nConnectedness == 8 );
50 24 : }
51 :
52 : /************************************************************************/
53 : /* ~GDALRasterPolygonEnumerator() */
54 : /************************************************************************/
55 :
56 24 : GDALRasterPolygonEnumerator::~GDALRasterPolygonEnumerator()
57 :
58 : {
59 24 : Clear();
60 24 : }
61 :
62 : /************************************************************************/
63 : /* Clear() */
64 : /************************************************************************/
65 :
66 30 : void GDALRasterPolygonEnumerator::Clear()
67 :
68 : {
69 30 : CPLFree( panPolyIdMap );
70 30 : CPLFree( panPolyValue );
71 :
72 30 : panPolyIdMap = NULL;
73 30 : panPolyValue = NULL;
74 :
75 30 : nNextPolygonId = 0;
76 30 : nPolyAlloc = 0;
77 30 : }
78 :
79 : /************************************************************************/
80 : /* MergePolygon() */
81 : /* */
82 : /* Update the polygon map to indicate the merger of two polygons. */
83 : /************************************************************************/
84 :
85 115 : void GDALRasterPolygonEnumerator::MergePolygon( int nSrcId, int nDstId )
86 :
87 : {
88 437 : while( panPolyIdMap[nDstId] != nDstId )
89 207 : nDstId = panPolyIdMap[nDstId];
90 :
91 252 : while( panPolyIdMap[nSrcId] != nSrcId )
92 22 : nSrcId = panPolyIdMap[nSrcId];
93 :
94 115 : if( nSrcId == nDstId )
95 40 : return;
96 :
97 75 : panPolyIdMap[nSrcId] = nDstId;
98 : }
99 :
100 : /************************************************************************/
101 : /* NewPolygon() */
102 : /* */
103 : /* Allocate a new polygon id, and reallocate the polygon maps */
104 : /* if needed. */
105 : /************************************************************************/
106 :
107 802 : int GDALRasterPolygonEnumerator::NewPolygon( GInt32 nValue )
108 :
109 : {
110 802 : int nPolyId = nNextPolygonId;
111 :
112 802 : if( nNextPolygonId >= nPolyAlloc )
113 : {
114 37 : nPolyAlloc = nPolyAlloc * 2 + 20;
115 37 : panPolyIdMap = (GInt32 *) CPLRealloc(panPolyIdMap,nPolyAlloc*4);
116 37 : panPolyValue = (GInt32 *) CPLRealloc(panPolyValue,nPolyAlloc*4);
117 : }
118 :
119 802 : nNextPolygonId++;
120 :
121 802 : panPolyIdMap[nPolyId] = nPolyId;
122 802 : panPolyValue[nPolyId] = nValue;
123 :
124 802 : return nPolyId;
125 : }
126 :
127 : /************************************************************************/
128 : /* CompleteMerges() */
129 : /* */
130 : /* Make a pass through the maps, ensuring every polygon id */
131 : /* points to the final id it should use, not an intermediate */
132 : /* value. */
133 : /************************************************************************/
134 :
135 12 : void GDALRasterPolygonEnumerator::CompleteMerges()
136 :
137 : {
138 : int iPoly;
139 12 : int nFinalPolyCount = 0;
140 :
141 356 : for( iPoly = 0; iPoly < nNextPolygonId; iPoly++ )
142 : {
143 722 : while( panPolyIdMap[iPoly]
144 : != panPolyIdMap[panPolyIdMap[iPoly]] )
145 34 : panPolyIdMap[iPoly] = panPolyIdMap[panPolyIdMap[iPoly]];
146 :
147 344 : if( panPolyIdMap[iPoly] == iPoly )
148 312 : nFinalPolyCount++;
149 : }
150 :
151 : CPLDebug( "GDALRasterPolygonEnumerator",
152 : "Counted %d polygon fragments forming %d final polygons.",
153 12 : nNextPolygonId, nFinalPolyCount );
154 12 : }
155 :
156 : /************************************************************************/
157 : /* ProcessLine() */
158 : /* */
159 : /* Assign ids to polygons, one line at a time. */
160 : /************************************************************************/
161 :
162 : void GDALRasterPolygonEnumerator::ProcessLine(
163 : GInt32 *panLastLineVal, GInt32 *panThisLineVal,
164 : GInt32 *panLastLineId, GInt32 *panThisLineId,
165 283 : int nXSize )
166 :
167 : {
168 : int i;
169 :
170 : /* -------------------------------------------------------------------- */
171 : /* Special case for the first line. */
172 : /* -------------------------------------------------------------------- */
173 283 : if( panLastLineVal == NULL )
174 : {
175 257 : for( i=0; i < nXSize; i++ )
176 : {
177 357 : if( i == 0 || panThisLineVal[i] != panThisLineVal[i-1] )
178 : {
179 130 : panThisLineId[i] = NewPolygon( panThisLineVal[i] );
180 : }
181 : else
182 97 : panThisLineId[i] = panThisLineId[i-1];
183 : }
184 :
185 30 : return;
186 : }
187 :
188 : /* -------------------------------------------------------------------- */
189 : /* Process each pixel comparing to the previous pixel, and to */
190 : /* the last line. */
191 : /* -------------------------------------------------------------------- */
192 4165 : for( i = 0; i < nXSize; i++ )
193 : {
194 6652 : if( i > 0 && panThisLineVal[i] == panThisLineVal[i-1] )
195 : {
196 2740 : panThisLineId[i] = panThisLineId[i-1];
197 :
198 2740 : if( panLastLineVal[i] == panThisLineVal[i]
199 : && (panPolyIdMap[panLastLineId[i]]
200 : != panPolyIdMap[panThisLineId[i]]) )
201 : {
202 115 : MergePolygon( panLastLineId[i], panThisLineId[i] );
203 : }
204 : }
205 1172 : else if( panLastLineVal[i] == panThisLineVal[i] )
206 : {
207 490 : panThisLineId[i] = panLastLineId[i];
208 : }
209 687 : else if( i > 0 && nConnectedness == 8
210 : && panLastLineVal[i-1] == panThisLineVal[i] )
211 : {
212 5 : panThisLineId[i] = panLastLineId[i-1];
213 : }
214 682 : else if( i < nXSize-1 && nConnectedness == 8
215 : && panLastLineVal[i+1] == panThisLineVal[i] )
216 : {
217 5 : panThisLineId[i] = panLastLineId[i+1];
218 : }
219 : else
220 : panThisLineId[i] =
221 672 : NewPolygon( panThisLineVal[i] );
222 : }
223 : }
224 :
|
