1 : /******************************************************************************
2 : * $Id: sdtspolygonreader.cpp 10645 2007-01-18 02:22:39Z warmerdam $
3 : *
4 : * Project: SDTS Translator
5 : * Purpose: Implementation of SDTSPolygonReader and SDTSRawPolygon classes.
6 : * Author: Frank Warmerdam, warmerdam@pobox.com
7 : *
8 : ******************************************************************************
9 : * Copyright (c) 1999, 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 "sdts_al.h"
31 :
32 : CPL_CVSID("$Id: sdtspolygonreader.cpp 10645 2007-01-18 02:22:39Z warmerdam $");
33 :
34 : /************************************************************************/
35 : /* ==================================================================== */
36 : /* SDTSRawPolygon */
37 : /* */
38 : /* This is a simple class for holding the data related with a */
39 : /* polygon feature. */
40 : /* ==================================================================== */
41 : /************************************************************************/
42 :
43 : /************************************************************************/
44 : /* SDTSRawPolygon() */
45 : /************************************************************************/
46 :
47 35 : SDTSRawPolygon::SDTSRawPolygon()
48 :
49 : {
50 35 : nAttributes = 0;
51 35 : nEdges = nRings = nVertices = 0;
52 35 : papoEdges = NULL;
53 :
54 35 : panRingStart = NULL;
55 35 : padfX = padfY = padfZ = NULL;
56 35 : }
57 :
58 : /************************************************************************/
59 : /* ~SDTSRawPolygon() */
60 : /************************************************************************/
61 :
62 70 : SDTSRawPolygon::~SDTSRawPolygon()
63 :
64 : {
65 35 : CPLFree( papoEdges );
66 35 : CPLFree( panRingStart );
67 35 : CPLFree( padfX );
68 35 : CPLFree( padfY );
69 35 : CPLFree( padfZ );
70 70 : }
71 :
72 : /************************************************************************/
73 : /* Read() */
74 : /* */
75 : /* Read a record from the passed SDTSPolygonReader, and assign the */
76 : /* values from that record to this object. This is the bulk of */
77 : /* the work in this whole file. */
78 : /************************************************************************/
79 :
80 35 : int SDTSRawPolygon::Read( DDFRecord * poRecord )
81 :
82 : {
83 : /* ==================================================================== */
84 : /* Loop over fields in this record, looking for those we */
85 : /* recognise, and need. */
86 : /* ==================================================================== */
87 105 : for( int iField = 0; iField < poRecord->GetFieldCount(); iField++ )
88 : {
89 70 : DDFField *poField = poRecord->GetField( iField );
90 : const char *pszFieldName;
91 :
92 : CPLAssert( poField != NULL );
93 70 : pszFieldName = poField->GetFieldDefn()->GetName();
94 :
95 70 : if( EQUAL(pszFieldName,"POLY") )
96 : {
97 35 : oModId.Set( poField );
98 : }
99 :
100 35 : else if( EQUAL(pszFieldName,"ATID") )
101 : {
102 0 : ApplyATID( poField );
103 : }
104 : }
105 :
106 35 : return TRUE;
107 : }
108 :
109 : /************************************************************************/
110 : /* AddEdge() */
111 : /************************************************************************/
112 :
113 50 : void SDTSRawPolygon::AddEdge( SDTSRawLine * poNewLine )
114 :
115 : {
116 50 : nEdges++;
117 :
118 50 : papoEdges = (SDTSRawLine **) CPLRealloc(papoEdges, sizeof(void*)*nEdges );
119 50 : papoEdges[nEdges-1] = poNewLine;
120 50 : }
121 :
122 : /************************************************************************/
123 : /* AddEdgeToRing() */
124 : /************************************************************************/
125 :
126 52 : void SDTSRawPolygon::AddEdgeToRing( int nVertToAdd,
127 : double * padfXToAdd,
128 : double * padfYToAdd,
129 : double * padfZToAdd,
130 : int bReverse, int bDropVertex )
131 :
132 : {
133 52 : int iStart=0, iEnd=nVertToAdd-1, iStep=1;
134 :
135 56 : if( bDropVertex && bReverse )
136 : {
137 4 : iStart = nVertToAdd - 2;
138 4 : iEnd = 0;
139 4 : iStep = -1;
140 : }
141 77 : else if( bDropVertex && !bReverse )
142 : {
143 29 : iStart = 1;
144 29 : iEnd = nVertToAdd - 1;
145 29 : iStep = 1;
146 : }
147 38 : else if( !bDropVertex && !bReverse )
148 : {
149 19 : iStart = 0;
150 19 : iEnd = nVertToAdd - 1;
151 19 : iStep = 1;
152 : }
153 0 : else if( !bDropVertex && bReverse )
154 : {
155 0 : iStart = nVertToAdd - 1;
156 0 : iEnd = 0;
157 0 : iStep = -1;
158 : }
159 :
160 1211 : for( int i = iStart; i != (iEnd+iStep); i += iStep )
161 : {
162 1159 : padfX[nVertices] = padfXToAdd[i];
163 1159 : padfY[nVertices] = padfYToAdd[i];
164 1159 : padfZ[nVertices] = padfZToAdd[i];
165 :
166 1159 : nVertices++;
167 : }
168 52 : }
169 :
170 : /************************************************************************/
171 : /* AssembleRings() */
172 : /************************************************************************/
173 :
174 : /**
175 : * Form border lines (arcs) into outer and inner rings.
176 : *
177 : * See SDTSPolygonReader::AssemblePolygons() for a simple one step process
178 : * to assembling geometry for all polygons in a transfer.
179 : *
180 : * This method will assemble the lines attached to a polygon into
181 : * an outer ring, and zero or more inner rings. Before calling it is
182 : * necessary that all the lines associated with this polygon have already
183 : * been attached. Normally this is accomplished by calling
184 : * SDTSLineReader::AttachToPolygons() on all line layers that might
185 : * contain edges related to this layer.
186 : *
187 : * This method then forms the lines into rings. Rings are formed by:
188 : * <ol>
189 : * <li> Take a previously unconsumed line, and start a ring with it. Mark
190 : * it as consumed, and keep track of it's start and end node ids as
191 : * being the start and end node ids of the ring.
192 : * <li> If the rings start id is the same as the end node id then this ring
193 : * is completely formed, return to step 1.
194 : * <li> Search all unconsumed lines for a line with the same start or end
195 : * node id as the rings current node id. If none are found then the
196 : * assembly has failed. Return to step 1 but report failure on
197 : * completion.
198 : * <li> Once found, add the line to the current ring, dropping the duplicated
199 : * vertex and reverse order if necessary. Mark the line as consumed,
200 : * and update the rings end node id accordingly.
201 : * <li> go to step 2.
202 : * </ol>
203 : *
204 : * Once ring assembly from lines is complete, another pass is made to
205 : * order the rings such that the exterior ring is first, the first ring
206 : * has counter-clockwise vertex ordering and the inner rings have clockwise
207 : * vertex ordering. This is accomplished based on the assumption that the
208 : * outer ring has the largest area, and using the +/- sign of area to establish
209 : * direction of rings.
210 : *
211 : * @return TRUE if all rings assembled without problems or FALSE if a problem
212 : * occured. If a problem occurs rings are still formed from all lines, but
213 : * some of the rings will not be closed, and rings will have no particular
214 : * order or direction.
215 : */
216 :
217 35 : int SDTSRawPolygon::AssembleRings()
218 :
219 : {
220 : int iEdge;
221 35 : int bSuccess = TRUE;
222 :
223 35 : if( nRings > 0 )
224 0 : return TRUE;
225 :
226 35 : if( nEdges == 0 )
227 22 : return FALSE;
228 :
229 : /* -------------------------------------------------------------------- */
230 : /* Allocate ring arrays. */
231 : /* -------------------------------------------------------------------- */
232 13 : panRingStart = (int *) CPLMalloc(sizeof(int) * nEdges);
233 :
234 13 : nVertices = 0;
235 63 : for( iEdge = 0; iEdge < nEdges; iEdge++ )
236 : {
237 50 : nVertices += papoEdges[iEdge]->nVertices;
238 : }
239 :
240 13 : padfX = (double *) CPLMalloc(sizeof(double) * nVertices);
241 13 : padfY = (double *) CPLMalloc(sizeof(double) * nVertices);
242 13 : padfZ = (double *) CPLMalloc(sizeof(double) * nVertices);
243 :
244 13 : nVertices = 0;
245 :
246 : /* -------------------------------------------------------------------- */
247 : /* Setup array of line markers indicating if they have been */
248 : /* added to a ring yet. */
249 : /* -------------------------------------------------------------------- */
250 13 : int *panEdgeConsumed, nRemainingEdges = nEdges;
251 :
252 13 : panEdgeConsumed = (int *) CPLCalloc(sizeof(int),nEdges);
253 :
254 : /* ==================================================================== */
255 : /* Loop generating rings. */
256 : /* ==================================================================== */
257 43 : while( nRemainingEdges > 0 )
258 : {
259 : int nStartNode, nLinkNode;
260 :
261 : /* -------------------------------------------------------------------- */
262 : /* Find the first unconsumed edge. */
263 : /* -------------------------------------------------------------------- */
264 : SDTSRawLine *poEdge;
265 :
266 17 : for( iEdge = 0; panEdgeConsumed[iEdge]; iEdge++ ) {}
267 :
268 17 : poEdge = papoEdges[iEdge];
269 :
270 : /* -------------------------------------------------------------------- */
271 : /* Start a new ring, copying in the current line directly */
272 : /* -------------------------------------------------------------------- */
273 17 : panRingStart[nRings++] = nVertices;
274 :
275 : AddEdgeToRing( poEdge->nVertices,
276 : poEdge->padfX, poEdge->padfY, poEdge->padfZ,
277 17 : FALSE, FALSE );
278 :
279 17 : panEdgeConsumed[iEdge] = TRUE;
280 17 : nRemainingEdges--;
281 :
282 17 : nStartNode = poEdge->oStartNode.nRecord;
283 17 : nLinkNode = poEdge->oEndNode.nRecord;
284 :
285 : /* ==================================================================== */
286 : /* Loop adding edges to this ring until we make a whole pass */
287 : /* within finding anything to add. */
288 : /* ==================================================================== */
289 17 : int bWorkDone = TRUE;
290 :
291 55 : while( nLinkNode != nStartNode
292 : && nRemainingEdges > 0
293 : && bWorkDone )
294 : {
295 21 : bWorkDone = FALSE;
296 :
297 319 : for( iEdge = 0; iEdge < nEdges; iEdge++ )
298 : {
299 298 : if( panEdgeConsumed[iEdge] )
300 182 : continue;
301 :
302 116 : poEdge = papoEdges[iEdge];
303 116 : if( poEdge->oStartNode.nRecord == nLinkNode )
304 : {
305 : AddEdgeToRing( poEdge->nVertices,
306 : poEdge->padfX, poEdge->padfY, poEdge->padfZ,
307 29 : FALSE, TRUE );
308 29 : nLinkNode = poEdge->oEndNode.nRecord;
309 : }
310 87 : else if( poEdge->oEndNode.nRecord == nLinkNode )
311 : {
312 : AddEdgeToRing( poEdge->nVertices,
313 : poEdge->padfX, poEdge->padfY, poEdge->padfZ,
314 4 : TRUE, TRUE );
315 4 : nLinkNode = poEdge->oStartNode.nRecord;
316 : }
317 : else
318 : {
319 83 : continue;
320 : }
321 :
322 33 : panEdgeConsumed[iEdge] = TRUE;
323 33 : nRemainingEdges--;
324 33 : bWorkDone = TRUE;
325 : }
326 : }
327 :
328 : /* -------------------------------------------------------------------- */
329 : /* Did we fail to complete the ring? */
330 : /* -------------------------------------------------------------------- */
331 17 : if( nLinkNode != nStartNode )
332 15 : bSuccess = FALSE;
333 :
334 : } /* next ring */
335 :
336 13 : CPLFree( panEdgeConsumed );
337 :
338 13 : if( !bSuccess )
339 11 : return bSuccess;
340 :
341 : /* ==================================================================== */
342 : /* Compute the area of each ring. The sign will be positive */
343 : /* for counter clockwise rings, otherwise negative. */
344 : /* */
345 : /* The algorithm used in this function was taken from _Graphics */
346 : /* Gems II_, James Arvo, 1991, Academic Press, Inc., section 1.1, */
347 : /* "The Area of a Simple Polygon", Jon Rokne, pp. 5-6. */
348 : /* ==================================================================== */
349 2 : double *padfRingArea, dfMaxArea = 0.0;
350 2 : int iRing, iBiggestRing = -1;
351 :
352 2 : padfRingArea = (double *) CPLCalloc(sizeof(double),nRings);
353 :
354 4 : for( iRing = 0; iRing < nRings; iRing++ )
355 : {
356 2 : double dfSum1 = 0.0, dfSum2 = 0.0;
357 : int i, nRingVertices;
358 :
359 2 : if( iRing == nRings - 1 )
360 2 : nRingVertices = nVertices - panRingStart[iRing];
361 : else
362 0 : nRingVertices = panRingStart[iRing+1] - panRingStart[iRing];
363 :
364 764 : for( i = panRingStart[iRing];
365 382 : i < panRingStart[iRing] + nRingVertices - 1;
366 : i++)
367 : {
368 380 : dfSum1 += padfX[i] * padfY[i+1];
369 380 : dfSum2 += padfY[i] * padfX[i+1];
370 : }
371 :
372 2 : padfRingArea[iRing] = (dfSum1 - dfSum2) / 2;
373 :
374 2 : if( ABS(padfRingArea[iRing]) > dfMaxArea )
375 : {
376 2 : dfMaxArea = ABS(padfRingArea[iRing]);
377 2 : iBiggestRing = iRing;
378 : }
379 : }
380 :
381 : /* ==================================================================== */
382 : /* Make a new set of vertices, and copy the largest ring into */
383 : /* it, adjusting the direction if necessary to ensure that this */
384 : /* outer ring is counter clockwise. */
385 : /* ==================================================================== */
386 2 : double *padfXRaw = padfX;
387 2 : double *padfYRaw = padfY;
388 2 : double *padfZRaw = padfZ;
389 2 : int *panRawRingStart = panRingStart;
390 2 : int nRawVertices = nVertices;
391 2 : int nRawRings = nRings;
392 : int nRingVertices;
393 :
394 2 : padfX = (double *) CPLMalloc(sizeof(double) * nVertices);
395 2 : padfY = (double *) CPLMalloc(sizeof(double) * nVertices);
396 2 : padfZ = (double *) CPLMalloc(sizeof(double) * nVertices);
397 2 : panRingStart = (int *) CPLMalloc(sizeof(int) * nRawRings);
398 2 : nVertices = 0;
399 2 : nRings = 0;
400 :
401 2 : if( iBiggestRing == nRawRings - 1 )
402 2 : nRingVertices = nRawVertices - panRawRingStart[iBiggestRing];
403 : else
404 : nRingVertices =
405 0 : panRawRingStart[iBiggestRing+1] - panRawRingStart[iBiggestRing];
406 :
407 2 : panRingStart[nRings++] = 0;
408 : AddEdgeToRing( nRingVertices,
409 2 : padfXRaw + panRawRingStart[iBiggestRing],
410 2 : padfYRaw + panRawRingStart[iBiggestRing],
411 2 : padfZRaw + panRawRingStart[iBiggestRing],
412 8 : padfRingArea[iBiggestRing] < 0.0, FALSE );
413 :
414 : /* ==================================================================== */
415 : /* Add the rest of the rings, which must be holes, in clockwise */
416 : /* order. */
417 : /* ==================================================================== */
418 4 : for( iRing = 0; iRing < nRawRings; iRing++ )
419 : {
420 2 : if( iRing == iBiggestRing )
421 2 : continue;
422 :
423 0 : if( iRing == nRawRings - 1 )
424 0 : nRingVertices = nRawVertices - panRawRingStart[iRing];
425 : else
426 0 : nRingVertices = panRawRingStart[iRing+1] - panRawRingStart[iRing];
427 :
428 0 : panRingStart[nRings++] = nVertices;
429 : AddEdgeToRing( nRingVertices,
430 0 : padfXRaw + panRawRingStart[iRing],
431 0 : padfYRaw + panRawRingStart[iRing],
432 0 : padfZRaw + panRawRingStart[iRing],
433 0 : padfRingArea[iRing] > 0.0, FALSE );
434 : }
435 :
436 : /* -------------------------------------------------------------------- */
437 : /* Cleanup */
438 : /* -------------------------------------------------------------------- */
439 2 : CPLFree( padfXRaw );
440 2 : CPLFree( padfYRaw );
441 2 : CPLFree( padfZRaw );
442 2 : CPLFree( padfRingArea );
443 2 : CPLFree( panRawRingStart );
444 :
445 2 : CPLFree( papoEdges );
446 2 : papoEdges = NULL;
447 2 : nEdges = 0;
448 :
449 2 : return TRUE;
450 : }
451 :
452 : /************************************************************************/
453 : /* Dump() */
454 : /************************************************************************/
455 :
456 0 : void SDTSRawPolygon::Dump( FILE * fp )
457 :
458 : {
459 : int i;
460 :
461 0 : fprintf( fp, "SDTSRawPolygon %s: ", oModId.GetName() );
462 :
463 0 : for( i = 0; i < nAttributes; i++ )
464 0 : fprintf( fp, " ATID[%d]=%s", i, paoATID[i].GetName() );
465 :
466 0 : fprintf( fp, "\n" );
467 0 : }
468 :
469 : /************************************************************************/
470 : /* ==================================================================== */
471 : /* SDTSPolygonReader */
472 : /* */
473 : /* This is the class used to read a Polygon module. */
474 : /* ==================================================================== */
475 : /************************************************************************/
476 :
477 : /************************************************************************/
478 : /* SDTSPolygonReader() */
479 : /************************************************************************/
480 :
481 1 : SDTSPolygonReader::SDTSPolygonReader()
482 :
483 : {
484 1 : bRingsAssembled = FALSE;
485 1 : }
486 :
487 : /************************************************************************/
488 : /* ~SDTSPolygonReader() */
489 : /************************************************************************/
490 :
491 2 : SDTSPolygonReader::~SDTSPolygonReader()
492 : {
493 2 : }
494 :
495 : /************************************************************************/
496 : /* Close() */
497 : /************************************************************************/
498 :
499 0 : void SDTSPolygonReader::Close()
500 :
501 : {
502 0 : oDDFModule.Close();
503 0 : }
504 :
505 : /************************************************************************/
506 : /* Open() */
507 : /* */
508 : /* Open the requested line file, and prepare to start reading */
509 : /* data records. */
510 : /************************************************************************/
511 :
512 1 : int SDTSPolygonReader::Open( const char * pszFilename )
513 :
514 : {
515 1 : return( oDDFModule.Open( pszFilename ) );
516 : }
517 :
518 : /************************************************************************/
519 : /* GetNextPolygon() */
520 : /* */
521 : /* Fetch the next feature as an STDSRawPolygon. */
522 : /************************************************************************/
523 :
524 36 : SDTSRawPolygon * SDTSPolygonReader::GetNextPolygon()
525 :
526 : {
527 : DDFRecord *poRecord;
528 :
529 : /* -------------------------------------------------------------------- */
530 : /* Read a record. */
531 : /* -------------------------------------------------------------------- */
532 36 : if( oDDFModule.GetFP() == NULL )
533 0 : return NULL;
534 :
535 36 : poRecord = oDDFModule.ReadRecord();
536 :
537 36 : if( poRecord == NULL )
538 1 : return NULL;
539 :
540 : /* -------------------------------------------------------------------- */
541 : /* Transform into a Polygon feature. */
542 : /* -------------------------------------------------------------------- */
543 35 : SDTSRawPolygon *poRawPolygon = new SDTSRawPolygon();
544 :
545 35 : if( poRawPolygon->Read( poRecord ) )
546 : {
547 35 : return( poRawPolygon );
548 : }
549 : else
550 : {
551 0 : delete poRawPolygon;
552 0 : return NULL;
553 : }
554 : }
555 :
556 : /************************************************************************/
557 : /* AssembleRings() */
558 : /************************************************************************/
559 :
560 : /**
561 : * Assemble geometry for a polygon transfer.
562 : *
563 : * This method takes care of attaching lines from all the line layers in
564 : * this transfer to this polygon layer, assembling the lines into rings on
565 : * the polygons, and then cleaning up unnecessary intermediate results.
566 : *
567 : * Currently this method will leave the line layers rewound to the beginning
568 : * but indexed, and the polygon layer rewound but indexed. In the future
569 : * it may restore reading positions, and possibly flush line indexes if they
570 : * were not previously indexed.
571 : *
572 : * This method does nothing if the rings have already been assembled on
573 : * this layer using this method.
574 : *
575 : * See SDTSRawPolygon::AssembleRings() for more information on how the lines
576 : * are assembled into rings.
577 : *
578 : * @param poTransfer the SDTSTransfer that this reader is a part of. Used
579 : * to get a list of line layers that might be needed.
580 : */
581 :
582 37 : void SDTSPolygonReader::AssembleRings( SDTSTransfer * poTransfer )
583 :
584 : {
585 37 : if( bRingsAssembled )
586 36 : return;
587 :
588 1 : bRingsAssembled = TRUE;
589 :
590 : /* -------------------------------------------------------------------- */
591 : /* To write polygons we need to build them from their related */
592 : /* arcs. We don't know off hand which arc (line) layers */
593 : /* contribute so we process all line layers, attaching them to */
594 : /* polygons as appropriate. */
595 : /* -------------------------------------------------------------------- */
596 9 : for( int iLineLayer = 0;
597 : iLineLayer < poTransfer->GetLayerCount();
598 : iLineLayer++ )
599 : {
600 : SDTSLineReader *poLineReader;
601 :
602 8 : if( poTransfer->GetLayerType(iLineLayer) != SLTLine )
603 7 : continue;
604 :
605 : poLineReader = (SDTSLineReader *)
606 1 : poTransfer->GetLayerIndexedReader( iLineLayer );
607 1 : if( poLineReader == NULL )
608 0 : continue;
609 :
610 1 : poLineReader->AttachToPolygons( poTransfer );
611 1 : poLineReader->Rewind();
612 : }
613 :
614 : /* -------------------------------------------------------------------- */
615 : /* Scan all polygons indexed on this reader, and assemble their */
616 : /* rings. */
617 : /* -------------------------------------------------------------------- */
618 : SDTSFeature *poFeature;
619 :
620 1 : Rewind();
621 37 : while( (poFeature = GetNextFeature()) != NULL )
622 : {
623 35 : SDTSRawPolygon *poPoly = (SDTSRawPolygon *) poFeature;
624 :
625 35 : poPoly->AssembleRings();
626 : }
627 :
628 1 : Rewind();
629 : }
|
