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