1 : /******************************************************************************
2 : * $Id: sdtspolygonreader.cpp 19952 2010-07-02 05:44:18Z 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 19952 2010-07-02 05:44:18Z 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 70 : SDTSRawPolygon::SDTSRawPolygon()
48 :
49 : {
50 70 : nAttributes = 0;
51 70 : nEdges = nRings = nVertices = 0;
52 70 : papoEdges = NULL;
53 :
54 70 : panRingStart = NULL;
55 70 : padfX = padfY = padfZ = NULL;
56 70 : }
57 :
58 : /************************************************************************/
59 : /* ~SDTSRawPolygon() */
60 : /************************************************************************/
61 :
62 70 : SDTSRawPolygon::~SDTSRawPolygon()
63 :
64 : {
65 70 : CPLFree( papoEdges );
66 70 : CPLFree( panRingStart );
67 70 : CPLFree( padfX );
68 70 : CPLFree( padfY );
69 70 : 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 70 : 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 210 : for( int iField = 0; iField < poRecord->GetFieldCount(); iField++ )
88 : {
89 140 : DDFField *poField = poRecord->GetField( iField );
90 : const char *pszFieldName;
91 :
92 140 : CPLAssert( poField != NULL );
93 140 : pszFieldName = poField->GetFieldDefn()->GetName();
94 :
95 140 : if( EQUAL(pszFieldName,"POLY") )
96 : {
97 70 : oModId.Set( poField );
98 : }
99 :
100 70 : else if( EQUAL(pszFieldName,"ATID") )
101 : {
102 0 : ApplyATID( poField );
103 : }
104 : }
105 :
106 70 : return TRUE;
107 : }
108 :
109 : /************************************************************************/
110 : /* AddEdge() */
111 : /************************************************************************/
112 :
113 100 : void SDTSRawPolygon::AddEdge( SDTSRawLine * poNewLine )
114 :
115 : {
116 100 : nEdges++;
117 :
118 100 : papoEdges = (SDTSRawLine **) CPLRealloc(papoEdges, sizeof(void*)*nEdges );
119 100 : papoEdges[nEdges-1] = poNewLine;
120 100 : }
121 :
122 : /************************************************************************/
123 : /* AddEdgeToRing() */
124 : /************************************************************************/
125 :
126 104 : void SDTSRawPolygon::AddEdgeToRing( int nVertToAdd,
127 : double * padfXToAdd,
128 : double * padfYToAdd,
129 : double * padfZToAdd,
130 : int bReverse, int bDropVertex )
131 :
132 : {
133 104 : int iStart=0, iEnd=nVertToAdd-1, iStep=1;
134 :
135 112 : if( bDropVertex && bReverse )
136 : {
137 8 : iStart = nVertToAdd - 2;
138 8 : iEnd = 0;
139 8 : iStep = -1;
140 : }
141 154 : else if( bDropVertex && !bReverse )
142 : {
143 58 : iStart = 1;
144 58 : iEnd = nVertToAdd - 1;
145 58 : iStep = 1;
146 : }
147 76 : else if( !bDropVertex && !bReverse )
148 : {
149 38 : iStart = 0;
150 38 : iEnd = nVertToAdd - 1;
151 38 : 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 2422 : for( int i = iStart; i != (iEnd+iStep); i += iStep )
161 : {
162 2318 : padfX[nVertices] = padfXToAdd[i];
163 2318 : padfY[nVertices] = padfYToAdd[i];
164 2318 : padfZ[nVertices] = padfZToAdd[i];
165 :
166 2318 : nVertices++;
167 : }
168 104 : }
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 70 : int SDTSRawPolygon::AssembleRings()
218 :
219 : {
220 : int iEdge;
221 70 : int bSuccess = TRUE;
222 :
223 70 : if( nRings > 0 )
224 0 : return TRUE;
225 :
226 70 : if( nEdges == 0 )
227 44 : return FALSE;
228 :
229 : /* -------------------------------------------------------------------- */
230 : /* Allocate ring arrays. */
231 : /* -------------------------------------------------------------------- */
232 26 : panRingStart = (int *) CPLMalloc(sizeof(int) * nEdges);
233 :
234 26 : nVertices = 0;
235 126 : for( iEdge = 0; iEdge < nEdges; iEdge++ )
236 : {
237 100 : nVertices += papoEdges[iEdge]->nVertices;
238 : }
239 :
240 26 : padfX = (double *) CPLMalloc(sizeof(double) * nVertices);
241 26 : padfY = (double *) CPLMalloc(sizeof(double) * nVertices);
242 26 : padfZ = (double *) CPLMalloc(sizeof(double) * nVertices);
243 :
244 26 : nVertices = 0;
245 :
246 : /* -------------------------------------------------------------------- */
247 : /* Setup array of line markers indicating if they have been */
248 : /* added to a ring yet. */
249 : /* -------------------------------------------------------------------- */
250 26 : int *panEdgeConsumed, nRemainingEdges = nEdges;
251 :
252 26 : panEdgeConsumed = (int *) CPLCalloc(sizeof(int),nEdges);
253 :
254 : /* ==================================================================== */
255 : /* Loop generating rings. */
256 : /* ==================================================================== */
257 86 : while( nRemainingEdges > 0 )
258 : {
259 : int nStartNode, nLinkNode;
260 :
261 : /* -------------------------------------------------------------------- */
262 : /* Find the first unconsumed edge. */
263 : /* -------------------------------------------------------------------- */
264 : SDTSRawLine *poEdge;
265 :
266 34 : for( iEdge = 0; panEdgeConsumed[iEdge]; iEdge++ ) {}
267 :
268 34 : poEdge = papoEdges[iEdge];
269 :
270 : /* -------------------------------------------------------------------- */
271 : /* Start a new ring, copying in the current line directly */
272 : /* -------------------------------------------------------------------- */
273 34 : panRingStart[nRings++] = nVertices;
274 :
275 : AddEdgeToRing( poEdge->nVertices,
276 : poEdge->padfX, poEdge->padfY, poEdge->padfZ,
277 34 : FALSE, FALSE );
278 :
279 34 : panEdgeConsumed[iEdge] = TRUE;
280 34 : nRemainingEdges--;
281 :
282 34 : nStartNode = poEdge->oStartNode.nRecord;
283 34 : 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 34 : int bWorkDone = TRUE;
290 :
291 110 : while( nLinkNode != nStartNode
292 : && nRemainingEdges > 0
293 : && bWorkDone )
294 : {
295 42 : bWorkDone = FALSE;
296 :
297 638 : for( iEdge = 0; iEdge < nEdges; iEdge++ )
298 : {
299 596 : if( panEdgeConsumed[iEdge] )
300 364 : continue;
301 :
302 232 : poEdge = papoEdges[iEdge];
303 232 : if( poEdge->oStartNode.nRecord == nLinkNode )
304 : {
305 : AddEdgeToRing( poEdge->nVertices,
306 : poEdge->padfX, poEdge->padfY, poEdge->padfZ,
307 58 : FALSE, TRUE );
308 58 : nLinkNode = poEdge->oEndNode.nRecord;
309 : }
310 174 : else if( poEdge->oEndNode.nRecord == nLinkNode )
311 : {
312 : AddEdgeToRing( poEdge->nVertices,
313 : poEdge->padfX, poEdge->padfY, poEdge->padfZ,
314 8 : TRUE, TRUE );
315 8 : nLinkNode = poEdge->oStartNode.nRecord;
316 : }
317 : else
318 : {
319 166 : continue;
320 : }
321 :
322 66 : panEdgeConsumed[iEdge] = TRUE;
323 66 : nRemainingEdges--;
324 66 : bWorkDone = TRUE;
325 : }
326 : }
327 :
328 : /* -------------------------------------------------------------------- */
329 : /* Did we fail to complete the ring? */
330 : /* -------------------------------------------------------------------- */
331 34 : if( nLinkNode != nStartNode )
332 30 : bSuccess = FALSE;
333 :
334 : } /* next ring */
335 :
336 26 : CPLFree( panEdgeConsumed );
337 :
338 26 : if( !bSuccess )
339 22 : 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 4 : double *padfRingArea, dfMaxArea = 0.0;
350 4 : int iRing, iBiggestRing = -1;
351 :
352 4 : padfRingArea = (double *) CPLCalloc(sizeof(double),nRings);
353 :
354 8 : for( iRing = 0; iRing < nRings; iRing++ )
355 : {
356 4 : double dfSum1 = 0.0, dfSum2 = 0.0;
357 : int i, nRingVertices;
358 :
359 4 : if( iRing == nRings - 1 )
360 4 : nRingVertices = nVertices - panRingStart[iRing];
361 : else
362 0 : nRingVertices = panRingStart[iRing+1] - panRingStart[iRing];
363 :
364 1528 : for( i = panRingStart[iRing];
365 764 : i < panRingStart[iRing] + nRingVertices - 1;
366 : i++)
367 : {
368 760 : dfSum1 += padfX[i] * padfY[i+1];
369 760 : dfSum2 += padfY[i] * padfX[i+1];
370 : }
371 :
372 4 : padfRingArea[iRing] = (dfSum1 - dfSum2) / 2;
373 :
374 4 : if( ABS(padfRingArea[iRing]) > dfMaxArea )
375 : {
376 4 : dfMaxArea = ABS(padfRingArea[iRing]);
377 4 : 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 4 : double *padfXRaw = padfX;
387 4 : double *padfYRaw = padfY;
388 4 : double *padfZRaw = padfZ;
389 4 : int *panRawRingStart = panRingStart;
390 4 : int nRawVertices = nVertices;
391 4 : int nRawRings = nRings;
392 : int nRingVertices;
393 :
394 4 : padfX = (double *) CPLMalloc(sizeof(double) * nVertices);
395 4 : padfY = (double *) CPLMalloc(sizeof(double) * nVertices);
396 4 : padfZ = (double *) CPLMalloc(sizeof(double) * nVertices);
397 4 : panRingStart = (int *) CPLMalloc(sizeof(int) * nRawRings);
398 4 : nVertices = 0;
399 4 : nRings = 0;
400 :
401 4 : if( iBiggestRing == nRawRings - 1 )
402 4 : nRingVertices = nRawVertices - panRawRingStart[iBiggestRing];
403 : else
404 : nRingVertices =
405 0 : panRawRingStart[iBiggestRing+1] - panRawRingStart[iBiggestRing];
406 :
407 4 : panRingStart[nRings++] = 0;
408 : AddEdgeToRing( nRingVertices,
409 4 : padfXRaw + panRawRingStart[iBiggestRing],
410 4 : padfYRaw + panRawRingStart[iBiggestRing],
411 4 : padfZRaw + panRawRingStart[iBiggestRing],
412 16 : padfRingArea[iBiggestRing] < 0.0, FALSE );
413 :
414 : /* ==================================================================== */
415 : /* Add the rest of the rings, which must be holes, in clockwise */
416 : /* order. */
417 : /* ==================================================================== */
418 8 : for( iRing = 0; iRing < nRawRings; iRing++ )
419 : {
420 4 : if( iRing == iBiggestRing )
421 4 : 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 4 : CPLFree( padfXRaw );
440 4 : CPLFree( padfYRaw );
441 4 : CPLFree( padfZRaw );
442 4 : CPLFree( padfRingArea );
443 4 : CPLFree( panRawRingStart );
444 :
445 4 : CPLFree( papoEdges );
446 4 : papoEdges = NULL;
447 4 : nEdges = 0;
448 :
449 4 : 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 2 : SDTSPolygonReader::SDTSPolygonReader()
482 :
483 : {
484 2 : bRingsAssembled = FALSE;
485 2 : }
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 2 : int SDTSPolygonReader::Open( const char * pszFilename )
513 :
514 : {
515 2 : return( oDDFModule.Open( pszFilename ) );
516 : }
517 :
518 : /************************************************************************/
519 : /* GetNextPolygon() */
520 : /* */
521 : /* Fetch the next feature as an STDSRawPolygon. */
522 : /************************************************************************/
523 :
524 72 : SDTSRawPolygon * SDTSPolygonReader::GetNextPolygon()
525 :
526 : {
527 : DDFRecord *poRecord;
528 :
529 : /* -------------------------------------------------------------------- */
530 : /* Read a record. */
531 : /* -------------------------------------------------------------------- */
532 72 : if( oDDFModule.GetFP() == NULL )
533 0 : return NULL;
534 :
535 72 : poRecord = oDDFModule.ReadRecord();
536 :
537 72 : if( poRecord == NULL )
538 2 : return NULL;
539 :
540 : /* -------------------------------------------------------------------- */
541 : /* Transform into a Polygon feature. */
542 : /* -------------------------------------------------------------------- */
543 70 : SDTSRawPolygon *poRawPolygon = new SDTSRawPolygon();
544 :
545 70 : if( poRawPolygon->Read( poRecord ) )
546 : {
547 70 : 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 : * @param iPolyLayer the polygon reader instance number, used to avoid processing
581 : * lines for other layers.
582 : */
583 :
584 74 : void SDTSPolygonReader::AssembleRings( SDTSTransfer * poTransfer,
585 : int iPolyLayer )
586 :
587 : {
588 74 : if( bRingsAssembled )
589 72 : return;
590 :
591 2 : bRingsAssembled = TRUE;
592 :
593 : /* -------------------------------------------------------------------- */
594 : /* To write polygons we need to build them from their related */
595 : /* arcs. We don't know off hand which arc (line) layers */
596 : /* contribute so we process all line layers, attaching them to */
597 : /* polygons as appropriate. */
598 : /* -------------------------------------------------------------------- */
599 18 : for( int iLineLayer = 0;
600 : iLineLayer < poTransfer->GetLayerCount();
601 : iLineLayer++ )
602 : {
603 : SDTSLineReader *poLineReader;
604 :
605 16 : if( poTransfer->GetLayerType(iLineLayer) != SLTLine )
606 14 : continue;
607 :
608 : poLineReader = (SDTSLineReader *)
609 2 : poTransfer->GetLayerIndexedReader( iLineLayer );
610 2 : if( poLineReader == NULL )
611 0 : continue;
612 :
613 2 : poLineReader->AttachToPolygons( poTransfer, iPolyLayer );
614 2 : poLineReader->Rewind();
615 : }
616 :
617 : /* -------------------------------------------------------------------- */
618 : /* Scan all polygons indexed on this reader, and assemble their */
619 : /* rings. */
620 : /* -------------------------------------------------------------------- */
621 : SDTSFeature *poFeature;
622 :
623 2 : Rewind();
624 74 : while( (poFeature = GetNextFeature()) != NULL )
625 : {
626 70 : SDTSRawPolygon *poPoly = (SDTSRawPolygon *) poFeature;
627 :
628 70 : poPoly->AssembleRings();
629 : }
630 :
631 2 : Rewind();
632 : }
|
