← Back to branch summary

~ubuntu-branches/ubuntu/hardy/libterralib/hardy

« back to all changes in this revision

Viewing changes to src/terralib/kernel/TeOverlay.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Daniel T Chen
  • Date: 2005-11-25 22:32:59 UTC
  • Revision ID: james.westby@ubuntu.com-20051125223259-3zubal8ux4ki4fjg
Tags: upstream-3.0.3b2
Import upstream version 3.0.3b2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/terralib/kernel/TeOverlay.cpp
 
1
/************************************************************************************
 
2
TerraLib - a library for developing GIS applications.
 
3
Copyright � 2001-2004 INPE and Tecgraf/PUC-Rio.
 
4
 
 
5
This code is part of the TerraLib library.
 
6
This library is free software; you can redistribute it and/or
 
7
modify it under the terms of the GNU Lesser General Public
 
8
License as published by the Free Software Foundation; either
 
9
version 2.1 of the License, or (at your option) any later version.
 
10
 
 
11
You should have received a copy of the GNU Lesser General Public
 
12
License along with this library.
 
13
 
 
14
The authors reassure the license terms regarding the warranties.
 
15
They specifically disclaim any warranties, including, but not limited to,
 
16
the implied warranties of merchantability and fitness for a particular purpose.
 
17
The library provided hereunder is on an "as is" basis, and the authors have no
 
18
obligation to provide maintenance, support, updates, enhancements, or modifications.
 
19
In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
 
20
indirect, special, incidental, or consequential damages arising out of the use
 
21
of this library and its documentation.
 
22
*************************************************************************************/
 
23
 
 
24
#include "TeOverlay.h"
 
25
#include "TeIntersector.h"
 
26
#include "TeGeometryAlgorithms.h"
 
27
#include "TeFragmentation.h"
 
28
 
 
29
#include <map>
 
30
#include <vector>
 
31
#include <algorithm>
 
32
 
 
33
using namespace std;
 
34
 
 
35
 
 
36
//---------------- Auxiliary structure ----------------//
 
37
struct xyOrder
 
38
{
 
39
        bool operator()(const TeCoord2D& c1, const TeCoord2D& c2) const
 
40
        {
 
41
                if(TeGeometryAlgorithmsPrecision::IsGreater(c2.x_, c1.x_))
 
42
                        return true;
 
43
 
 
44
                if(TeGeometryAlgorithmsPrecision::IsGreater(c1.x_, c2.x_))
 
45
                        return false;
 
46
 
 
47
                if(TeGeometryAlgorithmsPrecision::IsGreater(c2.y_, c1.y_))
 
48
                        return true;            
 
49
 
 
50
                return false;
 
51
        }
 
52
};
 
53
 
 
54
typedef multimap<TeCoord2D, pair<unsigned int, TeLine2D>, xyOrder> TeLineIndex;
 
55
 
 
56
 
 
57
 
 
58
inline void TeRemoveDuplicatedSegments(TeLine2D& l)
 
59
{
 
60
        bool hasDuplicated = false;
 
61
 
 
62
        for(unsigned int i = 1; i < l.size() - 1; ++i)
 
63
                if(TeEquals(l[i - 1], l[i + 1]))
 
64
                {
 
65
                        l.erase(i + 1);
 
66
                        hasDuplicated = true;
 
67
                }
 
68
 
 
69
        if(hasDuplicated)
 
70
                TeRemoveDuplicatedCoordinates(l);
 
71
 
 
72
        return;
 
73
}
 
74
 
 
75
void TeClonePolygonSet(const TePolygonSet& pSetIn, TePolygonSet& pSetOut)
 
76
{
 
77
        for(unsigned int i = 0; i < pSetIn.size(); ++i)
 
78
        {
 
79
                TePolygon p;
 
80
                for(unsigned int j = 0; j < pSetIn[i].size(); ++j)
 
81
                {
 
82
                        TeLine2D l;
 
83
 
 
84
                        for(unsigned int k = 0; k < pSetIn[i][j].size(); ++k)
 
85
                                l.add(pSetIn[i][j][k]);
 
86
 
 
87
                        TeRemoveDuplicatedCoordinates(l);
 
88
 
 
89
                        TeRemoveDuplicatedSegments(l);
 
90
 
 
91
                        TeLinearRing r(l);
 
92
 
 
93
                        p.add(r);               
 
94
                }
 
95
 
 
96
                pSetOut.add(p);
 
97
        }
 
98
}
 
99
 
 
100
void TeCloneLineSet(const TeLineSet& lSetIn, TeLineSet& lSetOut)
 
101
{
 
102
        for(unsigned int i = 0; i < lSetIn.size(); ++i)
 
103
        {
 
104
                TeLine2D l;
 
105
 
 
106
                for(unsigned int j = 0; j < lSetIn[i].size(); ++j)
 
107
                        l.add(lSetIn[i][j]);
 
108
 
 
109
                TeRemoveDuplicatedCoordinates(l);
 
110
 
 
111
                lSetOut.add(l);
 
112
        }
 
113
}
 
114
 
 
115
 
 
116
// Verifica qual opera��o a realizar e j� coloca as fronteiras dos pol�gonos na ordem correta e caso n�o seja necess�rio opera��o, ele j� retorna o resultado
 
117
TePolygonSet TeChooseOperation(const short& operation, TePolygonSet& redPols, TePolygonSet& bluePols, short& locationRedFragments, short& locationBlueFragments)
 
118
{
 
119
        TePolygonSet result;
 
120
 
 
121
        unsigned int i = 0;
 
122
 
 
123
        switch(operation)
 
124
        {                                                       
 
125
                // Intersection gets all fragments from red polygon wich are
 
126
                // inside the blue polygon and the blue fragments that are inside
 
127
                // the red polygon.
 
128
                case TeINTERSECTION:  if(TeDisjoint(redPols.box(), bluePols.box()))
 
129
                                                                  return result;
 
130
 
 
131
                                                          // Need to reverse orientation
 
132
                                                          for(i = 0; i < bluePols.size(); ++i)
 
133
                                                          {
 
134
                                                                  if(TeOrientation(bluePols[i][0]) == TeCOUNTERCLOCKWISE)
 
135
                                                                          reverse(bluePols[i][0].begin(), bluePols[i][0].end());
 
136
 
 
137
                                                                  for(unsigned int j = 1; j < bluePols[i].size(); ++j)
 
138
                                                                  {
 
139
                                                                          if(TeOrientation(bluePols[i][j]) == TeCLOCKWISE)
 
140
                                                                                  reverse(bluePols[i][j].begin(), bluePols[i][j].end());
 
141
                                                                  }
 
142
                                                          }
 
143
 
 
144
                                                          // Need to reverse orientation
 
145
                                                          for(i = 0; i < redPols.size(); ++i)
 
146
                                                          {
 
147
                                                                  if(TeOrientation(redPols[i][0]) == TeCOUNTERCLOCKWISE)
 
148
                                                                          reverse(redPols[i][0].begin(), redPols[i][0].end());
 
149
 
 
150
                                                                  for(unsigned int j = 1; j < redPols[i].size(); ++j)
 
151
                                                                  {
 
152
                                                                          if(TeOrientation(redPols[i][j]) == TeCLOCKWISE)
 
153
                                                                                  reverse(redPols[i][j].begin(), redPols[i][j].end());
 
154
                                                                  }
 
155
                                                          }
 
156
                        
 
157
                                          locationRedFragments  = TeINSIDE;
 
158
                                          locationBlueFragments = TeINSIDE;
 
159
 
 
160
                                                          break;
 
161
 
 
162
                // Union gets all fragments from red polygon wich are
 
163
                // outside the blue polygon and the blue fragments that are outside
 
164
                // the red polygon.
 
165
                case TeUNION:         if(TeDisjoint(redPols.box(), bluePols.box()))
 
166
                                                          {
 
167
                                                                  result = redPols;
 
168
 
 
169
                                                                  for(i = 0; i < bluePols.size(); ++i)
 
170
                                                                          result.add(bluePols[i]);
 
171
 
 
172
                                                                  return result;
 
173
                                                          }
 
174
 
 
175
                                                          // Need to reverse orientation
 
176
                                                          for(i = 0; i < bluePols.size(); ++i)
 
177
                                                          {
 
178
                                                                  if(TeOrientation(bluePols[i][0]) == TeCOUNTERCLOCKWISE)
 
179
                                                                          reverse(bluePols[i][0].begin(), bluePols[i][0].end());
 
180
 
 
181
                                                                  for(unsigned int j = 1; j < bluePols[i].size(); ++j)
 
182
                                                                  {
 
183
                                                                          if(TeOrientation(bluePols[i][j]) == TeCLOCKWISE)
 
184
                                                                                  reverse(bluePols[i][j].begin(), bluePols[i][j].end());
 
185
                                                                  }
 
186
                                                          }
 
187
 
 
188
                                                          // Need to reverse orientation
 
189
                                                          for(i = 0; i < redPols.size(); ++i)
 
190
                                                          {
 
191
                                                                  if(TeOrientation(redPols[i][0]) == TeCOUNTERCLOCKWISE)
 
192
                                                                          reverse(redPols[i][0].begin(), redPols[i][0].end());
 
193
 
 
194
                                                                  for(unsigned int j = 1; j < redPols[i].size(); ++j)
 
195
                                                                  {
 
196
                                                                          if(TeOrientation(redPols[i][j]) == TeCLOCKWISE)
 
197
                                                                                  reverse(redPols[i][j].begin(), redPols[i][j].end());
 
198
                                                                  }
 
199
                                                          }
 
200
 
 
201
                                                          locationRedFragments  = TeOUTSIDE;
 
202
                                          locationBlueFragments = TeOUTSIDE;
 
203
 
 
204
                                                          break;
 
205
 
 
206
                // Difference gets all fragments from red polygon wich are
 
207
                // outside the blue polygon and the blue fragments that are inside
 
208
                // the red polygon.
 
209
                case TeDIFFERENCE:        if(TeDisjoint(redPols.box(), bluePols.box()))
 
210
                                                                return redPols;
 
211
                        
 
212
                                                      locationRedFragments  = TeOUTSIDE;
 
213
                                          locationBlueFragments = TeINSIDE;
 
214
 
 
215
                                                          // Need to reverse orientation
 
216
                                                          for(i = 0; i < bluePols.size(); ++i)
 
217
                                                          {
 
218
                                                                  if(TeOrientation(bluePols[i][0]) == TeCLOCKWISE)
 
219
                                                                          reverse(bluePols[i][0].begin(), bluePols[i][0].end());
 
220
 
 
221
                                                                  for(unsigned int j = 1; j < bluePols[i].size(); ++j)
 
222
                                                                  {
 
223
                                                                          if(TeOrientation(bluePols[i][j]) == TeCOUNTERCLOCKWISE)
 
224
                                                                                  reverse(bluePols[i][j].begin(), bluePols[i][j].end());
 
225
                                                                  }
 
226
                                                          }
 
227
 
 
228
                                                          // Need to reverse orientation
 
229
                                                          for(i = 0; i < redPols.size(); ++i)
 
230
                                                          {
 
231
                                                                  if(TeOrientation(redPols[i][0]) == TeCOUNTERCLOCKWISE)
 
232
                                                                          reverse(redPols[i][0].begin(), redPols[i][0].end());
 
233
 
 
234
                                                                  for(unsigned int j = 1; j < redPols[i].size(); ++j)
 
235
                                                                  {
 
236
                                                                          if(TeOrientation(redPols[i][j]) == TeCLOCKWISE)
 
237
                                                                                  reverse(redPols[i][j].begin(), redPols[i][j].end());
 
238
                                                                  }
 
239
                                                          }                                                       
 
240
 
 
241
                                      break;
 
242
        }
 
243
 
 
244
        return result;
 
245
}
 
246
 
 
247
TeMultiGeometry TeChooseOperation(const short& operation, TeLineSet& redLines, TePolygonSet& bluePols, short& locationRedFragments)
 
248
{
 
249
        TeMultiGeometry result;
 
250
 
 
251
        switch(operation)
 
252
        {                                                       
 
253
                // Intersection gets all fragments from red polygon wich are
 
254
                // inside the blue polygon and the blue fragments that are inside
 
255
                // the red polygon.
 
256
                case TeINTERSECTION:  if(TeDisjoint(redLines.box(), bluePols.box()))
 
257
                                                                  return result;
 
258
                        
 
259
                                          locationRedFragments  = TeINSIDE;
 
260
                                                          break;
 
261
 
 
262
                // Union gets all fragments from red polygon wich are
 
263
                // outside the blue polygon and the blue fragments that are outside
 
264
                // the red polygon.
 
265
                case TeUNION:         if(TeDisjoint(redLines.box(), bluePols.box()))
 
266
                                                          {
 
267
                                                                  result.setGeometry(redLines);
 
268
                                                                  result.setGeometry(bluePols);
 
269
 
 
270
                                                                  return result;
 
271
                                                          }
 
272
 
 
273
                                                          locationRedFragments  = TeOUTSIDE;
 
274
 
 
275
                                                          break;
 
276
 
 
277
                // Difference gets all fragments from red polygon wich are
 
278
                // outside the blue polygon and the blue fragments that are inside
 
279
                // the red polygon.
 
280
                case TeDIFFERENCE:        if(TeDisjoint(redLines.box(), bluePols.box()))
 
281
                                                          {
 
282
                                                                  result.setGeometry(redLines);
 
283
                                                                  return result;
 
284
                                                          }
 
285
                        
 
286
                                                      locationRedFragments  = TeOUTSIDE;
 
287
 
 
288
                                      break;
 
289
        }
 
290
 
 
291
        return result;
 
292
} 
 
293
 
 
294
void TeRemoveOpositeBoundaryFragments(TeLineIndex& redFragmentsIndex, TeLineIndex& blueFragmentsIndex)
 
295
{
 
296
        TeLineIndex::iterator indexIterator = blueFragmentsIndex.begin();
 
297
        
 
298
        while(indexIterator != blueFragmentsIndex.end())
 
299
        {
 
300
                TeLineIndex::iterator idx = redFragmentsIndex.find(indexIterator->second.second[(indexIterator->second.second.size() - 1u)]);
 
301
 
 
302
                if(idx != redFragmentsIndex.end())
 
303
                {
 
304
                        if(TeEquals(idx->second.second[idx->second.second.size() - 1u], indexIterator->second.second[0u]))
 
305
                        {
 
306
                                redFragmentsIndex.erase(idx);
 
307
 
 
308
                                TeLineIndex::iterator idxAux;
 
309
                                idxAux = indexIterator;
 
310
                                ++indexIterator;
 
311
                                blueFragmentsIndex.erase(idxAux);
 
312
 
 
313
                                continue;
 
314
                        }
 
315
 
 
316
                }
 
317
                                        
 
318
 
 
319
                ++indexIterator;
 
320
        }
 
321
}
 
322
 
 
323
void TeRemoveSameBoundaryFragments(TeLineIndex& redFragmentsIndex, TeLineIndex& blueFragmentsIndex)
 
324
{
 
325
        TeLineIndex::iterator indexIterator = blueFragmentsIndex.begin();
 
326
        
 
327
        while(indexIterator != blueFragmentsIndex.end())
 
328
        {
 
329
                TeLineIndex::iterator idx = redFragmentsIndex.find(indexIterator->second.second[0u]);
 
330
 
 
331
                if(idx != redFragmentsIndex.end())
 
332
                {
 
333
                        if(TeEquals(idx->second.second[idx->second.second.size() - 1u], indexIterator->second.second[(indexIterator->second.second.size() - 1u)]))
 
334
                        {
 
335
                                redFragmentsIndex.erase(idx);
 
336
                                continue;
 
337
                        }
 
338
 
 
339
                }                                       
 
340
 
 
341
                ++indexIterator;
 
342
        }
 
343
}
 
344
 
 
345
void TeMergeFragments(TeLineIndex& fragmentsIndex, TeLineIndex& boundaryFragmentsIndex)
 
346
{
 
347
        TeLineIndex::iterator indexIterator = boundaryFragmentsIndex.begin();
 
348
 
 
349
        while(indexIterator != boundaryFragmentsIndex.end())
 
350
        {
 
351
                fragmentsIndex.insert(*indexIterator);
 
352
                ++indexIterator;
 
353
        }
 
354
 
 
355
        boundaryFragmentsIndex.clear(); 
 
356
}
 
357
 
 
358
void TeFindAndMoveClosedRings(TeLineIndex& fragmentsIndex, vector<TeLinearRing>& rings)
 
359
{
 
360
        TeLineIndex::iterator indexIterator = fragmentsIndex.begin();
 
361
 
 
362
        while(indexIterator != fragmentsIndex.end())
 
363
        {
 
364
                if(indexIterator->second.second.isRing())
 
365
                {
 
366
                        rings.push_back(indexIterator->second.second);
 
367
 
 
368
                        TeLineIndex::iterator idxAux;
 
369
                        idxAux = indexIterator;
 
370
                        ++indexIterator;
 
371
                        fragmentsIndex.erase(idxAux);
 
372
                }
 
373
                else
 
374
                        ++indexIterator;
 
375
        }
 
376
}
 
377
 
 
378
// Recebe um polygonset com an�is externos e um vetor de pol�gonos que seriam buracos e
 
379
// define em qual pol�gono colocar os buracos
 
380
bool TeMountTopology(TePolygonSet& polysOut, vector<TeLinearRing>& holes)
 
381
{
 
382
        bool returnValue = true;
 
383
 
 
384
        if((polysOut.size() == 0) && (holes.size() > 0))
 
385
        {
 
386
                return false;   // Formou buracos e n�o formou os an�is externos
 
387
        }
 
388
 
 
389
        if(polysOut.size() == 1)
 
390
        {
 
391
                for(unsigned int i = 0; i < holes.size(); ++i)
 
392
                        polysOut[0].add(holes[i]);              
 
393
        }
 
394
        else
 
395
        {
 
396
                for(unsigned int i = 0; i < holes.size(); ++i)
 
397
                {
 
398
                        TeLinearRing ring = holes[i];
 
399
 
 
400
                        vector<TePolygon> candidates;
 
401
                        vector<unsigned int> candidatesPos;
 
402
 
 
403
                        unsigned int j = 0;
 
404
 
 
405
                        for(j = 0; j < polysOut.size(); ++j)
 
406
                        {
 
407
                                if(TeWithinOrCoveredByOrEquals(ring.box(), polysOut[j].box()))
 
408
                                {
 
409
                                        candidates.push_back(polysOut[j]);
 
410
                                        candidatesPos.push_back(j);
 
411
                                }
 
412
                        }
 
413
 
 
414
                        if(candidates.size() == 1)
 
415
                        {
 
416
                                candidates[0].add(ring);
 
417
                                continue;
 
418
                        }
 
419
 
 
420
                        vector<TePolygon> newCandidates;
 
421
 
 
422
                        for(j = 0; j < candidates.size(); ++j)
 
423
                        {
 
424
                                short rel = TeBOUNDARY;
 
425
 
 
426
                                unsigned int nthVert = ring.size();
 
427
                                unsigned int iVert = 0u;
 
428
 
 
429
                                while(iVert < nthVert)
 
430
                                {
 
431
                                        rel = TeRelation(ring[iVert], candidates[j][0]);
 
432
 
 
433
                                        if(rel & TeINSIDE)
 
434
                                        {                               
 
435
                                                newCandidates.push_back(candidates[j]);
 
436
                                                break;
 
437
                                        }
 
438
                                        else if(rel & TeOUTSIDE)
 
439
                                        {
 
440
                                                break;
 
441
                                        }
 
442
                                
 
443
                                        ++iVert;
 
444
                                }
 
445
 
 
446
                                if(iVert == nthVert)    
 
447
                                {
 
448
                                        // Erro topol�gico, todos os pontos est�o na fronteira do anel externo...
 
449
                                        returnValue = false;
 
450
 
 
451
                                        TePolygon topTest;
 
452
                                        topTest.add(ring);
 
453
 
 
454
                                        short whatRel = TeRelation(topTest, candidates[j]);
 
455
 
 
456
                                        // Se um buraco for igual ao exterior, existe um erro topol�gico
 
457
                                        // No momento, eliminamos o anel externo
 
458
                                        // e o interno... 
 
459
                                        // Se o buraco for coberto pelo pol�gono externo, ent�o ele ir� ficar dentro deste
 
460
                                        // Caso contr�rio � erro sem possibilidades...
 
461
                                        if(whatRel & TeEQUALS)
 
462
                                        {                                               
 
463
                                                polysOut.erase(candidatesPos[j]);
 
464
                                                continue;
 
465
                                        }
 
466
                                }                               
 
467
                        }
 
468
 
 
469
                        if(newCandidates.size() <= 0)
 
470
                        {
 
471
                                // N�o encontrou o anel externo ao qual o buraco pertence
 
472
                                returnValue = false;
 
473
                                continue;
 
474
                        }
 
475
 
 
476
                        int idxMinArea = 0;
 
477
                        
 
478
                        double minArea = TeMAXFLOAT;
 
479
 
 
480
                        for(j = 0; j < newCandidates.size(); ++j)
 
481
                        {
 
482
                                if(TeGeometryArea(newCandidates[j].box()) < minArea)
 
483
                                {
 
484
                                        idxMinArea = j;
 
485
                                        minArea = TeGeometryArea(newCandidates[j].box());
 
486
                                }
 
487
                        }
 
488
 
 
489
                        newCandidates[idxMinArea].add(ring);
 
490
                }
 
491
        }
 
492
 
 
493
        return returnValue;
 
494
}
 
495
 
 
496
// Set operation for rings
 
497
bool TeOVERLAY::TeOverlay(const TePolygonSet& redPolsIn, const TePolygonSet& bluePolsIn, TePolygonSet& polsOut, const short& operation)
 
498
{
 
499
        polsOut.clear();
 
500
 
 
501
        short locationRedFragments = 0;         // Wich red fragments to consider.      
 
502
        short locationBlueFragments = 0;        // Wich blue fragments to consider.
 
503
 
 
504
        short redMask  = TeUNKNOWNPOSITION;     
 
505
        short blueMask = TeUNKNOWNPOSITION;     
 
506
        short location = TeUNKNOWNPOSITION;
 
507
 
 
508
        TePolygonSet redPols;
 
509
        TePolygonSet bluePols;
 
510
 
 
511
        // Copia o conte�do dos pol�gonos de entrada
 
512
        TeClonePolygonSet(redPolsIn, redPols);
 
513
        TeClonePolygonSet(bluePolsIn, bluePols);
 
514
 
 
515
        // Ajeita a orienta��o das fronteiras dos pol�gonos e determina a localiza��o dos fragmentos que ser�o utilizados
 
516
        polsOut = TeChooseOperation(operation, redPols, bluePols, locationRedFragments, locationBlueFragments);
 
517
 
 
518
        if(polsOut.size() > 0)
 
519
                return true;
 
520
 
 
521
 
 
522
        // If we are here so the rings are not disjoint by box
 
523
 
 
524
        // Gets intersection list
 
525
        TeINTERSECTOR2::TeVectorBoundaryIP report;
 
526
 
 
527
        TeINTERSECTOR2::TeSafeIntersections(redPols, bluePols, report);
 
528
 
 
529
        // So we need to create the fragments
 
530
        TeLineIndex redFragmentsIndex;
 
531
        TeLineIndex blueFragmentsIndex; 
 
532
 
 
533
        TeLineIndex redBoundaryFragmentsIndex;
 
534
        TeLineIndex blueBoundaryFragmentsIndex; 
 
535
 
 
536
 
 
537
        TeLineSet redRings;
 
538
        for(unsigned int i = 0; i < redPols.size(); ++i)
 
539
                for(unsigned int j = 0; j < redPols[i].size(); ++j)
 
540
                        redRings.add(redPols[i][j]);
 
541
 
 
542
        TeLineSet blueRings;
 
543
        for(unsigned int k = 0; k < bluePols.size(); ++k)
 
544
                for(unsigned int j = 0; j < bluePols[k].size(); ++j)
 
545
                        blueRings.add(bluePols[k][j]);
 
546
 
 
547
        // Choose red fragments
 
548
        TeLineSet redFragments;
 
549
        TeLineSet redFragmentsBoundary;
 
550
        TeFragmentBoundary(redRings, report, redFragmentsBoundary, redFragments);
 
551
 
 
552
        unsigned int setSize = redFragments.size();
 
553
 
 
554
        TeCoord2D middle;
 
555
 
 
556
        if(redFragmentsBoundary.size())
 
557
                redMask = TeBOUNDARY;
 
558
 
 
559
        unsigned int w = 0;
 
560
 
 
561
        for(w = 0; w < redFragmentsBoundary.size(); ++w)
 
562
                redBoundaryFragmentsIndex.insert(TeLineIndex::value_type(redFragmentsBoundary[w][0], pair<short, TeLine2D>(TeBOUNDARY, redFragmentsBoundary[w])));
 
563
 
 
564
        vector<TeLinearRing> rings;
 
565
 
 
566
        // Do a position test for each fragment and stop if all relations have been found.
 
567
        for(w = 0; w < setSize; ++w)
 
568
        {       
 
569
                if(redFragments[w].size() ==  2)        // If the fragment has two points I need to check the middle point of this fragment.
 
570
                        TeGetMiddlePoint(redFragments[w][0], redFragments[w][1], middle);
 
571
                else    // If the fragment has more than two points so I check one point between the end points.
 
572
                        middle = redFragments[w][(unsigned int)((double(redFragments[w].size()) / 2.0 + 0.6)) - 1];
 
573
                        
 
574
                location = TeRelation(middle, bluePols);
 
575
 
 
576
                // If fragment is on location type or is boundary, get it.
 
577
                if((location & locationRedFragments))
 
578
                {
 
579
                        if(redFragments[w].isRing())
 
580
                                rings.push_back(redFragments[w]);
 
581
                        else
 
582
                                redFragmentsIndex.insert(TeLineIndex::value_type(redFragments[w][0], pair<short, TeLine2D>(w, redFragments[w])));
 
583
                }
 
584
 
 
585
                redMask |= location;
 
586
        }
 
587
 
 
588
        // Choose blue fragments
 
589
 
 
590
        TeINTERSECTOR2::TeVectorBoundaryIP::iterator it     = report.begin();
 
591
        TeINTERSECTOR2::TeVectorBoundaryIP::iterator it_end = report.end();
 
592
        
 
593
        while(it != it_end)
 
594
        {
 
595
                swap(it->bluePartNum_, it->redPartNum_);
 
596
                swap(it->blueSegNum_, it->redSegNum_);
 
597
                ++it;
 
598
        }
 
599
 
 
600
        // Choose blue fragments
 
601
        TeLineSet blueFragments;
 
602
        TeLineSet blueFragmentsBoundary;
 
603
        
 
604
        TeFragmentBoundary(blueRings, report, blueFragmentsBoundary, blueFragments);
 
605
 
 
606
                
 
607
        setSize = blueFragments.size();
 
608
 
 
609
        for(w = 0; w < blueFragmentsBoundary.size(); ++w)
 
610
                blueBoundaryFragmentsIndex.insert(TeLineIndex::value_type(blueFragmentsBoundary[w][0], pair<short, TeLine2D>(TeBOUNDARY, blueFragmentsBoundary[w])));
 
611
 
 
612
        if(blueFragmentsBoundary.size())
 
613
                blueMask = TeBOUNDARY;
 
614
 
 
615
        // Do a position test for each fragment and stop if all relations have been found.
 
616
        for(unsigned int j = 0; j < setSize; ++j)
 
617
        {       
 
618
                if(blueFragments[j].size() ==  2)       // If the fragment has two points I need to check the middle point of this fragment.
 
619
                        TeGetMiddlePoint(blueFragments[j][0], blueFragments[j][1], middle);
 
620
                else    // If the fragment has more than two points so I check one point between the end points.
 
621
                        middle = blueFragments[j][(unsigned int)((double(blueFragments[j].size()) / 2.0 + 0.6)) - 1];
 
622
                        
 
623
                location = TeRelation(middle, redPols);
 
624
 
 
625
                // If fragment is on location type or is boundary, get it.
 
626
                if((location & locationBlueFragments))
 
627
                {
 
628
                        if(blueFragments[j].isRing())
 
629
                                rings.push_back(blueFragments[j]);
 
630
                        else
 
631
                                blueFragmentsIndex.insert(TeLineIndex::value_type(blueFragments[j][0], pair<short, TeLine2D>(w, blueFragments[j])));
 
632
                }
 
633
                
 
634
                blueMask |= location;           
 
635
        }
 
636
 
 
637
        // Remove closed rings => Only needs to test open segments
 
638
        TeFindAndMoveClosedRings(redBoundaryFragmentsIndex, rings);
 
639
        TeFindAndMoveClosedRings(blueBoundaryFragmentsIndex, rings);
 
640
 
 
641
 
 
642
        // Try to eliminate oposite boundaries
 
643
        TeRemoveOpositeBoundaryFragments(redBoundaryFragmentsIndex, blueBoundaryFragmentsIndex);
 
644
 
 
645
        // Try to eliminate same boundary fragments
 
646
        TeRemoveSameBoundaryFragments(redBoundaryFragmentsIndex, blueBoundaryFragmentsIndex);
 
647
 
 
648
        // Merge all red fragments in the first fragment index
 
649
        TeMergeFragments(redFragmentsIndex, redBoundaryFragmentsIndex);
 
650
 
 
651
        // Merge all blue fragments in the first fragment index
 
652
        TeMergeFragments(blueFragmentsIndex, blueBoundaryFragmentsIndex);
 
653
 
 
654
 
 
655
        // Make polygons from fragments.
 
656
        bool returnValue = true;
 
657
 
 
658
        TeLine2D  lAux; 
 
659
        TeCoord2D endLineCoordinate;
 
660
 
 
661
        while(!(redFragmentsIndex.empty() && blueFragmentsIndex.empty()))
 
662
        {
 
663
                if(lAux.size() == 0)
 
664
                {
 
665
                        TeLineIndex::iterator indexIterator  = redFragmentsIndex.begin();
 
666
                        if(indexIterator != redFragmentsIndex.end())
 
667
                        {
 
668
                                if(indexIterator->second.second.isRing())
 
669
                                {
 
670
                                        rings.push_back(indexIterator->second.second);
 
671
                                        redFragmentsIndex.erase(indexIterator);
 
672
                                        continue;
 
673
                                }
 
674
                                
 
675
                                for(unsigned int i = 0; i < indexIterator->second.second.size(); ++i)
 
676
                                        lAux.add(indexIterator->second.second[i]);
 
677
 
 
678
                                lAux.setBox(::TeUnion(lAux.box(), indexIterator->second.second.box()));
 
679
 
 
680
                                redFragmentsIndex.erase(indexIterator);
 
681
                        }
 
682
                        else
 
683
                        {
 
684
                                TeLineIndex::iterator indexIterator  = blueFragmentsIndex.begin();
 
685
                                if(indexIterator != blueFragmentsIndex.end())
 
686
                                {
 
687
                                        if(indexIterator->second.second.isRing())
 
688
                                        {
 
689
                                                rings.push_back(indexIterator->second.second);
 
690
                                                blueFragmentsIndex.erase(indexIterator);
 
691
                                                continue;
 
692
                                        }
 
693
 
 
694
                                        for(unsigned int i = 0; i < indexIterator->second.second.size(); ++i)
 
695
                                                lAux.add(indexIterator->second.second[i]);
 
696
 
 
697
                                        //lAux.copyElements(indexIterator->second);
 
698
                                        lAux.setBox(::TeUnion(lAux.box(), indexIterator->second.second.box()));
 
699
                                        blueFragmentsIndex.erase(indexIterator);
 
700
                                }
 
701
                                else
 
702
                                {
 
703
                                        returnValue = false;    //N�o poderia vir aqui, deveria ter sa�do no teste do la�o!!
 
704
                                }
 
705
                        }
 
706
                }       
 
707
                else
 
708
                {
 
709
                        endLineCoordinate = lAux[lAux.size() - 1];
 
710
 
 
711
                        // Try to find the beginning of the next fragment that is part of the polygon in the same list
 
712
                        TeLineIndex::iterator indexIterator = redFragmentsIndex.find(endLineCoordinate);
 
713
 
 
714
                        if(indexIterator != redFragmentsIndex.end())
 
715
                        {
 
716
                                for(unsigned int i = 1; i < indexIterator->second.second.size(); ++i)
 
717
                                        lAux.add(indexIterator->second.second[i]);
 
718
 
 
719
                                lAux.setBox(::TeUnion(lAux.box(), indexIterator->second.second.box()));
 
720
                                redFragmentsIndex.erase(indexIterator);
 
721
                        }                       
 
722
                        else
 
723
                        {
 
724
                                indexIterator = blueFragmentsIndex.find(endLineCoordinate);
 
725
 
 
726
                                if(indexIterator != blueFragmentsIndex.end())
 
727
                                {
 
728
                                        for(unsigned int i = 1; i < indexIterator->second.second.size(); ++i)
 
729
                                                lAux.add(indexIterator->second.second[i]);
 
730
 
 
731
                                        lAux.setBox(::TeUnion(lAux.box(), indexIterator->second.second.box()));
 
732
                                        blueFragmentsIndex.erase(indexIterator);
 
733
                                }
 
734
                                else
 
735
                                {
 
736
                                        if(lAux.isRing())
 
737
                                        {
 
738
                                                // Add ring
 
739
                                                rings.push_back(TeLinearRing(lAux));                                            
 
740
                                        }
 
741
 
 
742
                                        returnValue = false;    // Erro na topologia dos pol�gonos
 
743
 
 
744
                                        // Clear auxiliary.
 
745
                                        TeLine2D emptyLine;
 
746
                                        lAux = emptyLine;
 
747
                                }
 
748
                        }
 
749
                }
 
750
 
 
751
                if(lAux.isRing())
 
752
                {  
 
753
                        // Add polygon
 
754
                        rings.push_back(TeLinearRing(lAux));
 
755
                        
 
756
                        // Clear auxiliary.
 
757
                        TeLine2D emptyLine;                                     
 
758
                        lAux = emptyLine;
 
759
                }
 
760
        }
 
761
 
 
762
        if(lAux.size() > 0)
 
763
                returnValue = false;    // Erro, alguma linha n�o fechou!!!
 
764
 
 
765
        // Separate holes from islands
 
766
        vector<TeLinearRing> holes;
 
767
 
 
768
        //string aux = "";
 
769
        for(unsigned int z = 0; z < rings.size(); ++z)
 
770
        {
 
771
                short ori = TeOrientation(rings[z]);
 
772
 
 
773
                if(ori == TeCOUNTERCLOCKWISE)   // It is a hole
 
774
                {
 
775
                        holes.push_back(rings[z]);                      // add to holes list
 
776
                }
 
777
                else if(ori == TeCLOCKWISE)             // else if island
 
778
                {                                                                               // create a polygon
 
779
                        TePolygon p;
 
780
                        p.add(rings[z]);
 
781
                        polsOut.add(p);
 
782
                }
 
783
                else    
 
784
                {
 
785
                        returnValue = false;    // Objeto sem �rea? Isso � um erro!
 
786
                }
 
787
        }
 
788
        
 
789
        if((polsOut.size() == 0) && (holes.size() == 0))
 
790
        {
 
791
                if(operation & TeUNION)
 
792
                        return false;   // Na uni�o deve haver a forma��o de pol�gonos
 
793
                else
 
794
                        return returnValue;     // Diferen�a e interse��o podem retornar vazio
 
795
        }
 
796
 
 
797
        bool mountResult = TeMountTopology(polsOut, holes);
 
798
 
 
799
        return (returnValue && mountResult);    
 
800
}
 
801
 
 
802
TeMultiGeometry TeOVERLAY::TeOverlay(const TeLineSet& redLinesIn, const TePolygonSet& bluePolsIn, const short& operation)
 
803
{
 
804
        short location = TeUNKNOWNPOSITION;
 
805
        short locationRedFragments = TeUNKNOWNPOSITION;
 
806
 
 
807
        TeMultiGeometry mGeom;
 
808
 
 
809
        TeLineSet redLines;
 
810
        TePolygonSet bluePols;
 
811
        TeLineSet blueLines;
 
812
 
 
813
        // Copia o conte�do das linhas de entrada
 
814
        TeCloneLineSet(redLinesIn, redLines);
 
815
 
 
816
        // Copia o conte�do dos pol�gonos de entrada
 
817
        TeClonePolygonSet(bluePolsIn, bluePols);
 
818
 
 
819
 
 
820
        // Ajeita a orienta��o das fronteiras dos pol�gonos e determina a localiza��o dos fragmentos que ser�o utilizados
 
821
        mGeom = TeChooseOperation(operation, redLines, bluePols, locationRedFragments);
 
822
 
 
823
        if(!mGeom.empty())
 
824
                return mGeom;
 
825
 
 
826
        unsigned int i = 0u;
 
827
 
 
828
        // Gets intersection list
 
829
        TeINTERSECTOR2::TeVectorBoundaryIP report;
 
830
 
 
831
        unsigned int redLinesSize = redLines.size();
 
832
 
 
833
        // Loops through red lines
 
834
        for(i = 0u; i < redLinesSize; ++i)
 
835
        {
 
836
                unsigned int bluePart = 0u;
 
837
 
 
838
                // Loops through blue polygonset
 
839
                unsigned int bluePolsSize = bluePols.size();
 
840
 
 
841
                for(unsigned int j = 0u; j < bluePolsSize; ++j)
 
842
                {
 
843
                        //Loops trough blue polygon rings
 
844
                        unsigned int bluePolNumRings = bluePols[j].size();
 
845
 
 
846
                        for(unsigned k = 0u; k < bluePolNumRings; ++k)
 
847
                        {
 
848
                                TeINTERSECTOR2::TeSafeIntersections(redLines[i], bluePols[j][k], report, i, bluePart);
 
849
 
 
850
                                ++bluePart;
 
851
                        }
 
852
                }
 
853
 
 
854
                //++redPart;
 
855
        }
 
856
 
 
857
        // Fragment red Lines
 
858
        TeLineSet redFragments;
 
859
        TeLineSet redFragmentsBoundary;
 
860
        TeFragmentBoundary(redLines, report, redFragmentsBoundary, redFragments);
 
861
 
 
862
        // Choose red fragments
 
863
        unsigned int setSize = redFragments.size();
 
864
 
 
865
        TeCoord2D middle;
 
866
 
 
867
        for(i = 0u; i < setSize; ++i)
 
868
        {       
 
869
                if(redFragments[i].size() ==  2)        // If the fragment has two points I need to check the middle point of this fragment.
 
870
                        TeGetMiddlePoint(redFragments[i][0u], redFragments[i][1u], middle);
 
871
                else    // If the fragment has more than two points so I check one point between the end points.
 
872
                        middle = redFragments[i][(unsigned int)((double(redFragments[i].size()) / 2.0 + 0.6)) - 1];
 
873
                        
 
874
                location = TeRelation(middle, bluePols);
 
875
 
 
876
                // If fragment is on location type, get it.
 
877
                if((location & locationRedFragments))
 
878
                        mGeom.addGeometry(redFragments[i]);
 
879
        }
 
880
 
 
881
        switch(operation)
 
882
        {                                                       
 
883
                case TeINTERSECTION:  break;
 
884
 
 
885
                case TeUNION:         mGeom.setGeometry(bluePols);
 
886
                                                          break;
 
887
 
 
888
                case TeDIFFERENCE:        break;
 
889
        }
 
890
 
 
891
        return mGeom;
 
892
 
 
893
}
 
894
 
 
895