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