← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/vnc4/gutsy

« back to all changes in this revision

Viewing changes to unix/xc/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/polyDBG.cc

  • Committer: Bazaar Package Importer
  • Author(s): Ola Lundqvist
  • Date: 2006-05-15 20:35:17 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20060515203517-l4lre1ku942mn26k
Tags: 4.1.1+X4.3.0-10
* Correction of critical security issue. Thanks to Martin Kogler
  <e9925248@student.tuwien.ac.at> that informed me about the issue,
  and provided the patch.
  This flaw was originally found by Steve Wiseman of intelliadmin.com.
* Applied patch from Javier Kohen <jkohen@users.sourceforge.net> that
  inform the user that only 8 first characters of the password will
  actually be used when typing more than 8 characters, closes:
  #355619.

Show diffs side-by-side

added added

removed removed

Lines of Context:
unix/xc/extras/ogl-sample/main/gfx/lib/glu/libnurbs/nurbtess/polyDBG.cc
 
1
/*
 
2
** License Applicability. Except to the extent portions of this file are
 
3
** made subject to an alternative license as permitted in the SGI Free
 
4
** Software License B, Version 1.1 (the "License"), the contents of this
 
5
** file are subject only to the provisions of the License. You may not use
 
6
** this file except in compliance with the License. You may obtain a copy
 
7
** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
 
8
** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
 
9
** 
 
10
** http://oss.sgi.com/projects/FreeB
 
11
** 
 
12
** Note that, as provided in the License, the Software is distributed on an
 
13
** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
 
14
** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
 
15
** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
 
16
** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
 
17
** 
 
18
** Original Code. The Original Code is: OpenGL Sample Implementation,
 
19
** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
 
20
** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
 
21
** Copyright in any portions created by third parties is as indicated
 
22
** elsewhere herein. All Rights Reserved.
 
23
** 
 
24
** Additional Notice Provisions: The application programming interfaces
 
25
** established by SGI in conjunction with the Original Code are The
 
26
** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
 
27
** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
 
28
** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
 
29
** Window System(R) (Version 1.3), released October 19, 1998. This software
 
30
** was created using the OpenGL(R) version 1.2.1 Sample Implementation
 
31
** published by SGI, but has not been independently verified as being
 
32
** compliant with the OpenGL(R) version 1.2.1 Specification.
 
33
**
 
34
** $Date$ $Revision$
 
35
*/
 
36
/*
 
37
** $Header: //depot/main/gfx/lib/glu/libnurbs/nurbtess/polyDBG.cc#3 $
 
38
*/
 
39
 
 
40
#include <stdlib.h>
 
41
#include <stdio.h>
 
42
#include <math.h>
 
43
#include "zlassert.h"
 
44
#include "polyDBG.h"
 
45
 
 
46
 
 
47
static Real area(Real A[2], Real B[2], Real C[2])
 
48
{
 
49
  Real Bx, By, Cx, Cy;
 
50
  Bx = B[0] - A[0];
 
51
  By = B[1] - A[1];
 
52
  Cx = C[0] - A[0];
 
53
  Cy = C[1] - A[1];
 
54
  return Bx*Cy - Cx*By;
 
55
}
 
56
 
 
57
Int DBG_isConvex(directedLine *poly)
 
58
{
 
59
  directedLine* temp;
 
60
  if(area(poly->head(), poly->tail(), poly->getNext()->tail()) < 0.00000)
 
61
    return 0;
 
62
  for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
 
63
    {
 
64
      if(area(temp->head(), temp->tail(), temp->getNext()->tail()) < 0.00000)
 
65
        return 0;
 
66
    }
 
67
  return 1;
 
68
}
 
69
 
 
70
Int DBG_is_U_monotone(directedLine* poly)
 
71
{
 
72
  Int n_changes = 0;
 
73
  Int prev_sign;
 
74
  Int cur_sign;  
 
75
   directedLine* temp;
 
76
  cur_sign = compV2InX(poly->tail(), poly->head());
 
77
 
 
78
  n_changes = (compV2InX(poly->getPrev()->tail(), poly->getPrev()->head())
 
79
               != cur_sign);
 
80
 
 
81
  for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
 
82
    {
 
83
      prev_sign = cur_sign;
 
84
      cur_sign = compV2InX(temp->tail(), temp->head());
 
85
 
 
86
      if(cur_sign != prev_sign)
 
87
        n_changes++;
 
88
    }
 
89
 
 
90
  if(n_changes ==2) return 1;
 
91
  else return 0;
 
92
}
 
93
 
 
94
/*if u-monotone, and there is a long horizontal edge*/
 
95
Int DBG_is_U_direction(directedLine* poly)
 
96
{
 
97
/*
 
98
  if(! DBG_is_U_monotone(poly))
 
99
    return 0;
 
100
*/
 
101
  Int V_count = 0;
 
102
  Int U_count = 0;
 
103
  directedLine* temp;
 
104
  if( fabs(poly->head()[0] - poly->tail()[0]) <= fabs(poly->head()[1]-poly->tail()[1]))
 
105
    V_count += poly->get_npoints();
 
106
  else
 
107
    U_count += poly->get_npoints();
 
108
  /*
 
109
  else if(poly->head()[1] == poly->tail()[1])
 
110
    U_count += poly->get_npoints();
 
111
    */
 
112
  for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
 
113
    {
 
114
      if( fabs(temp->head()[0] - temp->tail()[0]) <= fabs(temp->head()[1]-temp->tail()[1]))
 
115
        V_count += temp->get_npoints();
 
116
      else
 
117
        U_count += temp->get_npoints();
 
118
      /*
 
119
      if(temp->head()[0] == temp->tail()[0])
 
120
        V_count += temp->get_npoints();
 
121
      else if(temp->head()[1] == temp->tail()[1])
 
122
        U_count += temp->get_npoints();      
 
123
        */
 
124
    }
 
125
 
 
126
  if(U_count > V_count) return 1;
 
127
  else return 0;
 
128
}
 
129
 
 
130
/*given two line segments, determine whether
 
131
 *they intersect each other or not.
 
132
 *return 1 if they do,
 
133
 *return 0 otherwise
 
134
 */
 
135
Int DBG_edgesIntersect(directedLine* l1, directedLine* l2)
 
136
{
 
137
  if(l1->getNext() == l2)
 
138
    {
 
139
      if(area(l1->head(), l1->tail(), l2->tail()) == 0) //colinear
 
140
        {
 
141
          if( (l1->tail()[0] - l1->head()[0])*(l2->tail()[0]-l2->head()[0]) +
 
142
             (l1->tail()[1] - l1->head()[1])*(l2->tail()[1]-l2->head()[1]) >=0)
 
143
            return 0; //not intersect
 
144
          else
 
145
            return 1;       
 
146
        }
 
147
      //else we use the normal code
 
148
    }
 
149
  else if(l1->getPrev() == l2)
 
150
    {
 
151
      if(area(l2->head(), l2->tail(), l1->tail()) == 0) //colinear
 
152
        {
 
153
          if( (l2->tail()[0] - l2->head()[0])*(l1->tail()[0]-l1->head()[0]) +
 
154
             (l2->tail()[1] - l2->head()[1])*(l1->tail()[1]-l1->head()[1]) >=0)
 
155
            return 0; //not intersect
 
156
          else
 
157
            return 1;       
 
158
        }      
 
159
      //else we use the normal code
 
160
    }
 
161
  else //the two edges are not connected
 
162
    {
 
163
      if((l1->head()[0] == l2->head()[0] &&
 
164
         l1->head()[1] == l2->head()[1]) ||
 
165
         (l1->tail()[0] == l2->tail()[0] &&
 
166
         l1->tail()[1] == l2->tail()[1]))
 
167
        return 1;
 
168
        
 
169
    }
 
170
  
 
171
 
 
172
  if( 
 
173
     (
 
174
      area(l1->head(), l1->tail(), l2->head())
 
175
      *
 
176
      area(l1->head(), l1->tail(), l2->tail())
 
177
      < 0
 
178
      )
 
179
     &&
 
180
     (
 
181
      area(l2->head(), l2->tail(), l1->head())
 
182
      *area(l2->head(), l2->tail(), l1->tail())
 
183
      < 0
 
184
      )
 
185
     )
 
186
    return 1;
 
187
  else 
 
188
    return 0;
 
189
}
 
190
 
 
191
/*whether AB and CD intersect
 
192
 *return 1 if they do
 
193
 *retur 0 otheriwse
 
194
 */
 
195
Int DBG_edgesIntersectGen(Real A[2], Real B[2], Real C[2], Real D[2])
 
196
{
 
197
  if(
 
198
     (
 
199
      area(A, B, C) * area(A,B,D) <0
 
200
      )
 
201
     &&
 
202
     (
 
203
      area(C,D,A) * area(C,D,B) < 0
 
204
      )
 
205
     )
 
206
    return 1;
 
207
  else
 
208
    return 0;
 
209
}
 
210
        
 
211
/*determien whether    (A,B) interesect chain[start] to [end]
 
212
 */
 
213
Int DBG_intersectChain(vertexArray* chain, Int start, Int end, Real A[2], Real B[2])
 
214
{
 
215
  Int i;
 
216
  for(i=start; i<=end-2; i++)
 
217
    if(DBG_edgesIntersectGen(chain->getVertex(i), chain->getVertex(i+1), A, B))
 
218
      return 1;
 
219
  
 
220
  return 0;
 
221
}
 
222
 
 
223
/*determine whether a polygon intersect itself or not
 
224
 *return 1 is it does,
 
225
 *       0 otherwise
 
226
 */
 
227
Int DBG_polygonSelfIntersect(directedLine* poly)
 
228
{
 
229
  directedLine* temp1;
 
230
  directedLine* temp2;
 
231
  temp1=poly;
 
232
  for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
 
233
    {
 
234
      if(DBG_edgesIntersect(temp1, temp2))
 
235
        {
 
236
          return 1;
 
237
        }
 
238
          
 
239
    }
 
240
 
 
241
  for(temp1=poly->getNext(); temp1 != poly; temp1 = temp1->getNext())
 
242
    for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
 
243
      {
 
244
        if(DBG_edgesIntersect(temp1, temp2))
 
245
          {
 
246
            return 1;
 
247
          }
 
248
      }
 
249
  return 0;
 
250
}
 
251
 
 
252
/*check whether a line segment intersects a  polygon
 
253
 */
 
254
Int DBG_edgeIntersectPoly(directedLine* edge, directedLine* poly)
 
255
{
 
256
  directedLine* temp;
 
257
  if(DBG_edgesIntersect(edge, poly))
 
258
    return 1;
 
259
  for(temp=poly->getNext(); temp != poly; temp=temp->getNext())
 
260
    if(DBG_edgesIntersect(edge, temp))
 
261
      return 1;
 
262
  return 0;
 
263
}
 
264
  
 
265
/*check whether two polygons intersect
 
266
 */
 
267
Int DBG_polygonsIntersect(directedLine* p1, directedLine* p2)
 
268
{
 
269
  directedLine* temp;
 
270
  if(DBG_edgeIntersectPoly(p1, p2))
 
271
    return 1;
 
272
  for(temp=p1->getNext(); temp!= p1; temp = temp->getNext())
 
273
    if(DBG_edgeIntersectPoly(temp, p2))
 
274
      return 1;
 
275
  return 0;
 
276
}
 
277
 
 
278
/*check whether there are polygons intersecting each other in
 
279
 *a list of polygons
 
280
 */
 
281
Int DBG_polygonListIntersect(directedLine* pList)
 
282
{
 
283
  directedLine *temp;
 
284
  for(temp=pList; temp != NULL; temp = temp->getNextPolygon())
 
285
    if(DBG_polygonSelfIntersect(temp))
 
286
      return 1;
 
287
  directedLine* temp2;
 
288
  for(temp=pList; temp!=NULL; temp=temp->getNextPolygon())
 
289
    {
 
290
      for(temp2=temp->getNextPolygon(); temp2 != NULL; temp2=temp2->getNextPolygon())
 
291
        if(DBG_polygonsIntersect(temp, temp2))
 
292
          return 1;
 
293
    }
 
294
  
 
295
  return 0;
 
296
}
 
297
 
 
298
 
 
299
Int DBG_isCounterclockwise(directedLine* poly)
 
300
{
 
301
  return (poly->polyArea() > 0);
 
302
}
 
303
 
 
304
/*ray: v0 with direction (dx,dy).
 
305
 *edge: v1-v2.
 
306
 * the extra point v10[2] is given for the information at 
 
307
 *v1. Basically this edge is connectd to edge
 
308
 * v10-v1. If v1 is on the ray, 
 
309
 * then we need v10  to determine whether this ray intersects
 
310
 * the edge or not (that is, return 1 or return 0). 
 
311
 * If v1 is on the ray, then if v2 and v10 are on the same side of the ray,
 
312
 * we return 0, otherwise return 1.
 
313
 *For v2, if v2 is on the ray, we always return 0.
 
314
 *Notice that v1 and v2 are not symmetric. So the edge is directed!!!
 
315
 * The purpose for this convention is such that: a point is inside a polygon 
 
316
 * if and only if it intersets with odd number of edges.
 
317
 */
 
318
Int DBG_rayIntersectEdge(Real v0[2], Real dx, Real dy, Real v10[2], Real v1[2], Real v2[2])
 
319
{
 
320
/*
 
321
if( (v1[1] >= v0[1] && v2[1]<= v0[1] )
 
322
  ||(v2[1] >= v0[1] && v1[1]<= v0[1] )
 
323
   )
 
324
  printf("rayIntersectEdge, *********\n");
 
325
*/
 
326
 
 
327
  Real denom = (v2[0]-v1[0])*(-dy) - (v2[1]-v1[1]) * (-dx);
 
328
  Real nomRay = (v2[0]-v1[0]) * (v0[1] - v1[1]) - (v2[1]-v1[1])*(v0[0]-v1[0]);
 
329
  Real nomEdge = (v0[0]-v1[0]) * (-dy) - (v0[1]-v1[1])*(-dx);
 
330
 
 
331
 
 
332
  /*if the ray is parallel to the edge, return 0: not intersect*/
 
333
  if(denom == 0.0) 
 
334
    return 0;
 
335
 
 
336
  /*if v0 is on the edge, return 0: not intersect*/
 
337
  if(nomRay == 0.0) 
 
338
    return 0;
 
339
  
 
340
  /*if v1 is on the positive ray, and the neighbor of v1 crosses the ray
 
341
   *return 1: intersect
 
342
   */
 
343
  if(nomEdge == 0) 
 
344
    { /*v1 is on the positive or negative ray*/
 
345
 
 
346
/*
 
347
      printf("v1 is on the ray\n");
 
348
*/
 
349
 
 
350
      if(dx*(v1[0]-v0[0])>=0 && dy*(v1[1]-v0[1])>=0) /*v1 on positive ray*/
 
351
        {
 
352
          if(area(v0, v1, v10) * area(v0, v1, v2) >0)
 
353
            return 0;
 
354
          else 
 
355
            return 1;
 
356
        }
 
357
      else /*v1 on negative ray*/
 
358
        return 0;
 
359
    }
 
360
 
 
361
  /*if v2 is on the ray, always return 0: not intersect*/
 
362
  if(nomEdge == denom) {
 
363
/*    printf("v2 is on the ray\n");*/
 
364
    return 0;
 
365
  }
 
366
 
 
367
  /*finally */
 
368
  if(denom*nomRay>0 && denom*nomEdge>0 && nomEdge/denom <=1.0)
 
369
    return 1;
 
370
  return 0;
 
371
}
 
372
 
 
373
 
 
374
/*return the number of intersections*/
 
375
Int DBG_rayIntersectPoly(Real v0[2], Real dx, Real dy, directedLine* poly)
 
376
{
 
377
  directedLine* temp;
 
378
  Int count=0;
 
379
  if(DBG_rayIntersectEdge(v0, dx, dy, poly->getPrev()->head(), poly->head(), poly->tail()))
 
380
    count++;
 
381
  
 
382
  for(temp=poly->getNext(); temp != poly; temp = temp->getNext())
 
383
    if(DBG_rayIntersectEdge(v0, dx, dy, temp->getPrev()->head(), temp->head(), temp->tail()))
 
384
      count++;    
 
385
/*printf("ray intersect poly: count=%i\n", count);*/
 
386
  return count;
 
387
}
 
388
 
 
389
Int DBG_pointInsidePoly(Real v[2], directedLine* poly)
 
390
{
 
391
/*
 
392
printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]);
 
393
printf("the polygon is\n");
 
394
poly->printList();
 
395
*/
 
396
  /*for debug purpose*/
 
397
  assert( (DBG_rayIntersectPoly(v,1,0,poly) % 2 )
 
398
         == (DBG_rayIntersectPoly(v,1,0.1234, poly) % 2 )
 
399
         );
 
400
  if(DBG_rayIntersectPoly(v, 1, 0, poly) % 2 == 1)
 
401
    return 1; 
 
402
  else 
 
403
    return 0;
 
404
}
 
405
 
 
406
/*return the number of polygons which contain thie polygon
 
407
 * as a subset
 
408
 */
 
409
Int DBG_enclosingPolygons(directedLine* poly, directedLine* list)
 
410
{
 
411
  directedLine* temp;
 
412
  Int count=0;
 
413
/*  
 
414
printf("%i\n", DBG_pointInsidePoly(poly->head(), 
 
415
                                   list->getNextPolygon()
 
416
                                   ->getNextPolygon()
 
417
                                   ->getNextPolygon()
 
418
                                   ->getNextPolygon()
 
419
));
 
420
*/
 
421
 
 
422
  for(temp = list; temp != NULL; temp = temp->getNextPolygon())
 
423
    {
 
424
      if(poly != temp)
 
425
        if(DBG_pointInsidePoly(poly->head(), temp))
 
426
          count++;    
 
427
/*      printf("count=%i\n", count);*/
 
428
    }
 
429
  return count;
 
430
}
 
431
 
 
432
void  DBG_reverse(directedLine* poly)
 
433
{
 
434
  if(poly->getDirection() == INCREASING) 
 
435
    poly->putDirection(DECREASING);
 
436
  else
 
437
    poly->putDirection(INCREASING);
 
438
 
 
439
  directedLine* oldNext = poly->getNext();
 
440
  poly->putNext(poly->getPrev());
 
441
  poly->putPrev(oldNext);
 
442
 
 
443
  directedLine* temp;
 
444
  for(temp=oldNext; temp!=poly; temp = oldNext)
 
445
    {
 
446
      if(temp->getDirection() == INCREASING) 
 
447
        temp->putDirection(DECREASING);
 
448
      else
 
449
        temp->putDirection(INCREASING);
 
450
 
 
451
      oldNext = temp->getNext();
 
452
      temp->putNext(temp->getPrev());
 
453
      temp->putPrev(oldNext);
 
454
    }
 
455
  printf("reverse done\n");
 
456
}
 
457
 
 
458
Int DBG_checkConnectivity(directedLine *polygon)
 
459
{
 
460
  if(polygon == NULL) return 1;
 
461
  directedLine* temp;
 
462
  if(polygon->head()[0] != polygon->getPrev()->tail()[0] ||
 
463
     polygon->head()[1] != polygon->getPrev()->tail()[1])
 
464
    return 0;
 
465
  for(temp=polygon->getNext(); temp != polygon; temp=temp->getNext())
 
466
    {
 
467
      if(temp->head()[0] != temp->getPrev()->tail()[0] ||
 
468
         temp->head()[1] != temp->getPrev()->tail()[1])
 
469
        return 0;
 
470
    }
 
471
  return 1;
 
472
}
 
473
 
 
474
/*print out error message.
 
475
 *If it cannot modify the polygon list to make it satify the
 
476
 *requirements, return 1.
 
477
 *otherwise modify the polygon list, and return 0
 
478
 */
 
479
Int DBG_check(directedLine *polyList)
 
480
{
 
481
  directedLine* temp;
 
482
  if(polyList == NULL) return 0;
 
483
 
 
484
  /*if there are intersections, print out error message
 
485
   */
 
486
  if(DBG_polygonListIntersect(polyList))
 
487
    {
 
488
      fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n");
 
489
    return 1;
 
490
    }
 
491
 
 
492
  /*check the connectivity of each polygon*/
 
493
  for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
 
494
    {
 
495
      if(! DBG_checkConnectivity(temp))
 
496
        {
 
497
          fprintf(stderr, "DBG_check, polygon not connected\n");
 
498
          return 1;
 
499
        }
 
500
    }
 
501
 
 
502
  /*check the orientation of each polygon*/
 
503
  for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
 
504
    {
 
505
 
 
506
 
 
507
      Int correctDir;
 
508
 
 
509
      if( DBG_enclosingPolygons(temp, polyList) % 2 == 0)
 
510
        correctDir = 1; /*counterclockwise*/
 
511
      else
 
512
        correctDir = 0; /*clockwise*/
 
513
 
 
514
      Int actualDir = DBG_isCounterclockwise(temp);
 
515
      
 
516
      if(correctDir != actualDir)
 
517
        {
 
518
          fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n");
 
519
 
 
520
          DBG_reverse(temp);
 
521
        }
 
522
 
 
523
    }
 
524
  return 0;
 
525
}
 
526
 
 
527
/**************handle self intersections*****************/
 
528
//determine whether e interects [begin, end] or not
 
529
static directedLine* DBG_edgeIntersectChainD(directedLine *e, 
 
530
                               directedLine *begin, directedLine *end)
 
531
{
 
532
  directedLine *temp;
 
533
  for(temp=begin; temp != end; temp = temp->getNext())
 
534
    {
 
535
      if(DBG_edgesIntersect(e, temp))
 
536
         return temp;
 
537
    }
 
538
  if(DBG_edgesIntersect(e, end))
 
539
    return end;
 
540
  return NULL;      
 
541
}
 
542
 
 
543
//given a polygon, cut the edges off and finally obtain a 
 
544
//a polygon without intersections. The cut-off edges are
 
545
//dealloated. The new polygon is returned.
 
546
directedLine* DBG_cutIntersectionPoly(directedLine *polygon, int& cutOccur)
 
547
{
 
548
  directedLine *begin, *end, *next;
 
549
  begin = polygon;
 
550
  end = polygon;
 
551
  cutOccur = 0;
 
552
  while( (next = end->getNext()) != begin)
 
553
    {
 
554
      directedLine *interc = NULL;
 
555
      if( (interc = DBG_edgeIntersectChainD(next, begin, end)))
 
556
        {
 
557
          int fixed = 0;
 
558
          if(DBG_edgesIntersect(next, interc->getNext()))
 
559
             {
 
560
               //trying to fix it
 
561
               Real buf[2];
 
562
               int i;
 
563
               Int n=5;
 
564
               buf[0] = interc->tail()[0];
 
565
               buf[1] = interc->tail()[1];
 
566
               
 
567
               for(i=1; i<n; i++)
 
568
                 {
 
569
                   Real r = ((Real)i) / ((Real) n);
 
570
                   Real u = (1-r) * interc->head()[0] + r * interc->tail()[0];
 
571
                   Real v = (1-r) * interc->head()[1] + r * interc->tail()[1];
 
572
                   interc->tail()[0] = interc->getNext()->head()[0] = u;
 
573
                   interc->tail()[1] = interc->getNext()->head()[1] = v;
 
574
                   if( (! DBG_edgesIntersect(next, interc)) &&
 
575
                      (! DBG_edgesIntersect(next, interc->getNext())))
 
576
                     break; //we fixed it
 
577
                 }
 
578
               if(i==n) // we didn't fix it
 
579
                 {
 
580
                   fixed = 0;
 
581
                   //back to original
 
582
                   interc->tail()[0] = interc->getNext()->head()[0] = buf[0];
 
583
                   interc->tail()[1] = interc->getNext()->head()[1] = buf[1];
 
584
                 }
 
585
               else
 
586
                 {
 
587
                   fixed = 1;
 
588
                 }
 
589
             }
 
590
          if(fixed == 0)
 
591
            {
 
592
              cutOccur = 1;
 
593
              begin->deleteSingleLine(next);
 
594
              
 
595
              if(begin != end)
 
596
                {
 
597
                  if(DBG_polygonSelfIntersect(begin))
 
598
                    {
 
599
                      directedLine* newEnd = end->getPrev();
 
600
                      begin->deleteSingleLine(end);
 
601
                      end = newEnd;
 
602
                    }
 
603
                }
 
604
            }
 
605
          else
 
606
            {
 
607
              end = end->getNext();
 
608
            }
 
609
        }
 
610
      else
 
611
        {
 
612
          end = end->getNext();
 
613
        }
 
614
    }
 
615
  return begin;
 
616
}
 
617
 
 
618
//given a polygon, cut the edges off and finally obtain a 
 
619
//a polygon without intersections. The cut-off edges are
 
620
//dealloated. The new polygon is returned.
 
621
static directedLine* DBG_cutIntersectionPoly_notwork(directedLine *polygon)
 
622
{
 
623
  directedLine *crt;//current polygon
 
624
  directedLine *begin;
 
625
  directedLine *end;
 
626
  directedLine *temp;
 
627
  crt = polygon;
 
628
  int find=0;
 
629
  while(1)
 
630
    {
 
631
//printf("loop\n");
 
632
      //if there are less than 3 edges, we should stop
 
633
      if(crt->getPrev()->getPrev() == crt)
 
634
        return NULL;
 
635
 
 
636
      if(DBG_edgesIntersect(crt, crt->getNext()) ||
 
637
        (crt->head()[0] == crt->getNext()->tail()[0] &&
 
638
        crt->head()[1] == crt->getNext()->tail()[1])
 
639
         )
 
640
        {
 
641
          find = 1;
 
642
          crt=crt->deleteChain(crt, crt->getNext());
 
643
        }
 
644
      else
 
645
        {         
 
646
          //now we know crt and crt->getNext do not intersect
 
647
          begin = crt;
 
648
          end = crt->getNext();
 
649
//printf("begin=(%f,%f)\n", begin->head()[0], begin->head()[1]);
 
650
//printf("end=(%f,%f)\n", end->head()[0], end->head()[1]);
 
651
          for(temp=end->getNext(); temp!=begin; temp= temp->getNext())
 
652
            {
 
653
//printf("temp=(%f,%f)\n", temp->head()[0], temp->head()[1]);
 
654
               directedLine *intersect = DBG_edgeIntersectChainD(temp, begin, end);
 
655
               if(intersect != NULL)
 
656
                {
 
657
                  crt = crt->deleteChain(intersect, temp);
 
658
                  find=1;
 
659
                  break; //the for loop
 
660
                }
 
661
              else
 
662
                {
 
663
                  end = temp;
 
664
                }
 
665
            }
 
666
        }
 
667
      if(find == 0)
 
668
        return crt;
 
669
      else
 
670
        find = 0;    //go to next loop
 
671
}
 
672
}
 
673
 
 
674
directedLine* DBG_cutIntersectionAllPoly(directedLine* list)
 
675
{
 
676
  directedLine* temp;
 
677
  directedLine* tempNext=NULL;
 
678
  directedLine* ret = NULL;
 
679
  int cutOccur=0;
 
680
  for(temp=list; temp != NULL; temp = tempNext)
 
681
    {
 
682
      directedLine *left;
 
683
      tempNext = temp->getNextPolygon();
 
684
 
 
685
      left = DBG_cutIntersectionPoly(temp, cutOccur);
 
686
      if(left != NULL)
 
687
        ret=left->insertPolygon(ret);
 
688
    }
 
689
  return ret;            
 
690
}
 
691
 
 
692
sampledLine*  DBG_collectSampledLinesAllPoly(directedLine *polygonList)
 
693
{
 
694
  directedLine *temp;
 
695
  sampledLine* tempHead = NULL;
 
696
  sampledLine* tempTail = NULL;
 
697
  sampledLine* cHead = NULL;
 
698
  sampledLine* cTail = NULL;
 
699
 
 
700
  if(polygonList == NULL)
 
701
    return NULL;
 
702
 
 
703
  DBG_collectSampledLinesPoly(polygonList, cHead, cTail);
 
704
 
 
705
  assert(cHead);
 
706
  assert(cTail);
 
707
  for(temp = polygonList->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
 
708
    {
 
709
      DBG_collectSampledLinesPoly(temp, tempHead, tempTail);
 
710
      cTail->insert(tempHead);
 
711
      cTail = tempTail;
 
712
    }  
 
713
  return cHead;
 
714
}
 
715
 
 
716
void  DBG_collectSampledLinesPoly(directedLine *polygon, sampledLine*& retHead, sampledLine*& retTail)
 
717
{
 
718
  directedLine *temp;
 
719
  sampledLine *ret = NULL;
 
720
  retHead = NULL;
 
721
  retTail = NULL;
 
722
  if(polygon == NULL)
 
723
    return;
 
724
    
 
725
  retHead = retTail = polygon->getSampledLine();
 
726
  for(temp = polygon->getNext(); temp != polygon; temp=temp->getNext())
 
727
    {
 
728
      retHead = temp->getSampledLine()->insert(retHead);
 
729
    }
 
730
}