-
Notifications
You must be signed in to change notification settings - Fork 0
/
polypack_iftran_CodeIftran.txt
10067 lines (10041 loc) · 275 KB
/
polypack_iftran_CodeIftran.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
.OP LS=10001 LI=1 CB OC UC=0 BI=66 IF=2
.EL I
I
I $Id: CodeIftran,v 1.6 2006-03-10 00:05:51 kennison Exp $
I
I ---------------------------------------------------------------------
I P O L Y G O N M A N I P U L A T I O N R O U T I N E S
I ---------------------------------------------------------------------
SUBROUTINE PPDIPO (XCCP,YCCP,NCCP,XCSP,YCSP,NCSP,
+ RWRK,IWRK,NWRK,URPP,IERR)
C
DIMENSION XCCP(NCCP),YCCP(NCCP)
DIMENSION XCSP(NCSP),YCSP(NCSP)
DIMENSION RWRK(NWRK),IWRK(NWRK)
C
C The subroutine PPDIPO, given X/Y coordinates defining the vertices
C of a "clip polygon" in (XCCP(I),I=1,NCCP) and (YCCP(I),I=1,NCCP),
C X/Y coordinates defining the vertices of a "subject polygon" in
C (XCSP(I),I=1,NCSP) and (YCSP(I),I=1,NCSP), and the real and integer
C workspaces RWRK and IWRK, each of which is of length NWRK, generates
C the set of polygons representing pieces of the subject polygon lying
C outside the clip polygon and delivers each of them to a user-defined
C polygon-processing routine called URPP. Errors, in general, result
C in an immediate RETURN with IERR non-zero; on a normal return, IERR
C is zero.
C
C For most efficient use of memory, IWRK and RWRK should be EQUIVALENCEd
C to each other.
C
C The algorithm used is that described by Bala R. Vatti in the article
C "A Generic Solution to Polygon Clipping", which was published in the
C July, 1992, issue of "Communications of the ACM" (Vol. 35, No. 7).
C
C The various linked lists used in Vatti's algorithm are implemented as
C follows:
C
C LMT (Local Minimum Table). Formed initially at the lower end of the
C workspace. Released 3-word nodes are put on a garbage list and may
C be re-used as part of an output polygon. LMT nodes have the following
C structure:
C
C 0: Y value of a local minimum on one of the two input polygons.
C LMT nodes are sorted by increasing value of this element.
C
C 1: Index of local minimum (1 to LCCP for clip polygon, LCCP+1 to
C LCCP+LCSP for subject polygon).
C
C 2: Index of the next node of the LMT.
C
C AET (Active Edge Table). Occupies space at the lower end of the
C workspace. Released 10-word nodes are put on a garbage list and may
C be re-used for new AET nodes. AET nodes have the following structure:
C
C 0: X coordinate at the current scanbeam position. AET nodes are
C sorted by increasing value of this element.
C
C 1: X coordinate at the end of the edge segment. (I added this to
C get around a problem which arose because Vatti's formulation did
C not result in correct X coordinates at the end of a segment.)
C
C 2: Y coordinate at the end of the edge segment.
C
C 3: Change in X for a unit increase in Y.
C
C 4: Clip/subject edge flag (0 for clip, 1 for subject).
C
C 5: Left/right flag (0 for left, 1 for right).
C
C 6: Pointer to the next edge in the AET.
C
C 7: Pointer to the previous edge in the AET.
C
C 8: Pointer to the edge segment which succeeds this one. This value
C is either positive or negative and has absolute value "n". If
C the value is positive, it implies that the indices of the points
C at the ends of the succeeding edge are "n" and "n+1"; if the
C value is negative, the indices are "n" and "n-1". The indices
C are into the arrays XCCP and YCCP, if element 4 is zero, or XCSP
C and YCSP, if element 4 is non-zero.
C
C 9: Pointer to output polygon to which the edge is "contributing"
C (0 if no such polygon).
C
C Output Polygon. Occupies space at the upper end of the workspace.
C Released 3-word nodes are put on a garbage list from which they can
C be re-used for other polygons. Output-polygon nodes have the
C following structure:
C
C Principal Node:
C
C 0: Pointer to the left-end subsidiary node.
C
C 1: Pointer to the right-end subsidiary node.
C
C 2: Pointer to the principal node of the next polygon (0 if none).
C
C Subsidiary Node:
C
C 0: X coordinate of a point.
C
C 1: Y coordinate of a point.
C
C 2: Pointer to the next subsidiary node to the "right" along the
C polygon. ("Left" and "right" are defined from the standpoint
C of an observer standing on the edge of the polygon and facing
C inwards.)
C
C SET (Sorted Edge Table). Occupies space at the lower end of the
C workspace, following the AET. All space used is reclaimed. SET
C nodes have the following structure:
C
C 0: X coordinate of edge's intersection with the top of the scanbeam.
C SET nodes are sorted by decreasing value of this element.
C
C 1: Pointer to a node in the AET. Says which edge is represented by
C the node.
C
C 2: Pointer to the next node in the SET.
C
C INT (INtersection Table). Occupies space at the lower end of the
C workspace, following the AET. All space used is reclaimed. INT
C nodes have the following structure:
C
C 0: X coordinate of point of intersection.
C
C 1: Y coordinate of point of intersection. INT nodes are sorted
C by increasing value of this element.
C
C 2: Pointer to a node in the AET, identifying one of the two edges
C that intersect.
C
C 3: Pointer to a later node in the AET, identifying the other edge.
C
C 4: Pointer to the next node in the INT.
C
C Define RBIG to be a large real number.
C
DATA RBIG / 1.E36 /
C
C Zero error flag.
C
IERR=0
C
C Decide what the real lengths of the polygons are (depending on whether
C the first point is repeated at the end or not).
C
LCCP=NCCP
IF (XCCP(NCCP).EQ.XCCP(1).AND.YCCP(NCCP).EQ.YCCP(1)) LCCP=NCCP-1
C
LCSP=NCSP
IF (XCSP(NCSP).EQ.XCSP(1).AND.YCSP(NCSP).EQ.YCSP(1)) LCSP=NCSP-1
C
C Do some simple checks for degenerate cases.
C
IF (LCCP.LT.3)
INVOKE (DEGENERATE-CLIP-POLYGON,NR)
END IF
C
IF (LCSP.LT.3)
INVOKE (DEGENERATE-SUBJECT-POLYGON,NR)
END IF
C
C Initialize the garbage lists, onto which released 3-word and 10-word
C nodes are put for possible re-use.
C
IG03=0
IG10=0
C
C Initialize pointers to the last-used elements at the beginning and
C end of the available workspace. Initially, the whole thing is
C available:
C
IPWL=0
IPWU=NWRK+1
C
C Build the "LMT" ("Local Minimum Table"). Initially, it is empty:
C
ILMT=0
C
C Search for local minima of the clip polygon. First, find a starting
C place where the Y coordinate changes one way or the other.
C
INXT=0
C
DO (I=1,LCCP-1)
IF (YCCP(I).NE.YCCP(I+1))
INXT=I
YNXT=YCCP(INXT)
GO TO 101
END IF
END DO
C
C If there is no such starting place, take an error exit.
C
INVOKE (DEGENERATE-CLIP-POLYGON,NR)
C
C Otherwise, go through the entire polygon from the starting position,
C finding all those places where the Y value increases after having
C decreased. Each such place constitutes one of the local minima in
C the LMT.
C
101 IDIR=0
C
DO (I=0,LCCP)
ILST=INXT
YLST=YNXT
INXT=INXT+1
IF (INXT.GT.LCCP) INXT=INXT-LCCP
YNXT=YCCP(INXT)
IF (YNXT.LT.YLST)
IDIR=-1
ELSE IF (YNXT.GT.YLST)
IF (IDIR.LT.0)
ILMN=IPWL+1
IPWL=IPWL+3
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
RWRK(ILMN)=YLST
IWRK(ILMN+1)=ILST
ITM1=0
ITM2=ILMT
LOOP
EXIT IF (ITM2.EQ.0)
EXIT IF (RWRK(ILMN).LE.RWRK(ITM2))
ITM1=ITM2
ITM2=IWRK(ITM2+2)
END LOOP
IF (ITM1.EQ.0)
ILMT=ILMN
ELSE
IWRK(ITM1+2)=ILMN
END IF
IWRK(ILMN+2)=ITM2
END IF
IDIR=+1
END IF
END DO
C
C In the same way, search for local minima of the subject polygon.
C
INXT=0
C
DO (I=1,LCSP-1)
IF (YCSP(I).NE.YCSP(I+1))
INXT=I
YNXT=YCSP(INXT)
GO TO 102
END IF
END DO
C
INVOKE (DEGENERATE-SUBJECT-POLYGON,NR)
C
102 IDIR=0
C
DO (I=0,LCSP)
ILST=INXT
YLST=YNXT
INXT=INXT+1
IF (INXT.GT.LCSP) INXT=INXT-LCSP
YNXT=YCSP(INXT)
IF (YNXT.LT.YLST)
IDIR=-1
ELSE IF (YNXT.GT.YLST)
IF (IDIR.LT.0)
ILMN=IPWL+1
IPWL=IPWL+3
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
RWRK(ILMN)=YLST
IWRK(ILMN+1)=LCCP+ILST
ITM1=0
ITM2=ILMT
LOOP
EXIT IF (ITM2.EQ.0)
EXIT IF (RWRK(ILMN).LE.RWRK(ITM2))
ITM1=ITM2
ITM2=IWRK(ITM2+2)
END LOOP
IF (ITM1.EQ.0)
ILMT=ILMN
ELSE
IWRK(ITM1+2)=ILMN
END IF
IWRK(ILMN+2)=ITM2
END IF
IDIR=+1
END IF
END DO
C
C Initialize the output polygon list pointer to indicate that no
C polygons have been generated yet:
C
IPPL=0
C
C Initialize the "AET" ("Active Edge Table") to be empty:
C
IAET=0
C
C Initialize the variable that normally keeps track of the Y coordinate
C at the top of the current "scanbeam"; the value will be used as the Y
C coordinate at the bottom of the first one.
C
YTOS=RWRK(ILMT)
C
C Loop through the "scanbeams".
C
LOOP
C
C YBOS is the Y coordinate of the bottom of the new scanbeam.
C
YBOS=YTOS
C
C Loop through those local minima in the LMT having Y coordinate
C YBOS; for each, add to the AET the pair of edges that start at
C that local minimum.
C
LOOP
C
C Quit if the end of the LMT has been reached.
C
EXIT IF (ILMT.EQ.0)
C
C Quit if the Y coordinate of the next local minimum is too large.
C
EXIT IF (RWRK(ILMT).GT.YBOS)
C
C Retrieve in IMIN the index of the coordinates of the local minimum.
C
IMIN=IWRK(ILMT+1)
C
C Set ICOS to indicate whether the local minimum comes from the clip
C polygon or the subject polygon. XMIN and YMIN are the X and Y
C coordinates of the local minimum. ILST indexes the coordinates of
C the last point along the polygon; the coordinates are XLST and YLST.
C Similarly, INXT indexes the coordinates of the next point along
C the polygon; the coordinates are XNXT and YNXT.
C
IF (IMIN.LE.LCCP)
ICOS=0
XMIN=XCCP(IMIN)
YMIN=YCCP(IMIN)
ILST=IMIN-1
IF (ILST.LT.1) ILST=ILST+LCCP
XLST=XCCP(ILST)
YLST=YCCP(ILST)
INXT=IMIN+1
IF (INXT.GT.LCCP) INXT=INXT-LCCP
XNXT=XCCP(INXT)
YNXT=YCCP(INXT)
ELSE
ICOS=1
IMIN=IMIN-LCCP
XMIN=XCSP(IMIN)
YMIN=YCSP(IMIN)
ILST=IMIN-1
IF (ILST.LT.1) ILST=ILST+LCSP
XLST=XCSP(ILST)
YLST=YCSP(ILST)
INXT=IMIN+1
IF (INXT.GT.LCSP) INXT=INXT-LCSP
XNXT=XCSP(INXT)
YNXT=YCSP(INXT)
END IF
C
C Now we must scan the AET to determine where to put the new edges.
C After executing the loop below, ITM1 will point to the node after
C which they will be inserted (zero if at beginning) and ITM2 will
C point to the node before which they will be inserted (zero if at
C end). The variable IOCP will be updated to indicate whether the
C local minimum is inside (1) or outside (0) the clip polygon.
C Similarly, IOSP will be updated to indicate whether the local
C minimum is inside (1) or outside (0) the subject polygon.
C
ITM1=0
ITM2=IAET
C
IOCP=0
IOSP=0
C
LOOP
C
C Exit if the end of the AET has been reached.
C
EXIT IF (ITM2.EQ.0)
C
C Exit if the new local minimum fits between elements ITM1 and ITM2 of
C the AET.
C
EXIT IF (XMIN.LE.RWRK(ITM2))
C
C Advance to the next position in the AET.
C
ITM1=ITM2
ITM2=IWRK(ITM2+6)
C
C Update the flags that say where we are relative to the clip and
C subject polygons.
C
IF (IWRK(ITM1+4).EQ.0)
IOCP=1-IOCP
ELSE
IOSP=1-IOSP
END IF
C
C End of loop through the AET.
C
END LOOP
C
C Create two new nodes in the AET. Either re-use 10-word nodes from the
C garbage list or create new ones.
C
IF (IG10.NE.0)
IPNL=IG10
IG10=IWRK(IG10)
ELSE
IPNL=IPWL+1
IPWL=IPWL+10
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
END IF
C
IF (IG10.NE.0)
IPNN=IG10
IG10=IWRK(IG10)
ELSE
IPNN=IPWL+1
IPWL=IPWL+10
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
END IF
C
C Fill in the information about the two new edges:
C
RWRK(IPNL)=XMIN
RWRK(IPNN)=XMIN
C
RWRK(IPNL+1)=XLST
RWRK(IPNN+1)=XNXT
C
RWRK(IPNL+2)=YLST
RWRK(IPNN+2)=YNXT
C
IF (YLST.NE.YMIN)
RWRK(IPNL+3)=(XLST-XMIN)/(YLST-YMIN)
ELSE
RWRK(IPNL+3)=SIGN(RBIG,XLST-XMIN)
END IF
C
IF (YNXT.NE.YMIN)
RWRK(IPNN+3)=(XNXT-XMIN)/(YNXT-YMIN)
ELSE
RWRK(IPNN+3)=SIGN(RBIG,XNXT-XMIN)
END IF
C
IWRK(IPNL+4)=ICOS
IWRK(IPNN+4)=ICOS
C
IF (ICOS.EQ.0)
IOPO=IOCP
ELSE
IOPO=IOSP
END IF
C
IF (RWRK(IPNL+3).LT.RWRK(IPNN+3))
C
IPE1=IPNL
IPE2=IPNN
C
ELSE
C
IPE1=IPNN
IPE2=IPNL
C
END IF
C
IWRK(IPE1+5)=IOPO
IWRK(IPE2+5)=1-IOPO
C
IF (ITM1.EQ.0)
IAET=IPE1
ELSE
IWRK(ITM1+6)=IPE1
END IF
C
IWRK(IPE1+6)=IPE2
IWRK(IPE2+6)=ITM2
IF (ITM2.NE.0) IWRK(ITM2+7)=IPE2
IWRK(IPE2+7)=IPE1
IWRK(IPE1+7)=ITM1
C
IWRK(IPNL+8)=-ILST
IWRK(IPNN+8)=+INXT
C
C If the edges are "contributing", create an output polygon for them
C to "contribute" to and put the initial point in it; otherwise, zero
C the output-polygon pointers.
C
IF ((IOCP.EQ.0.AND.IOSP.NE.0).OR.
+ (IOCP.NE.0.AND.IOSP.NE.0.AND.ICOS.EQ.0).OR.
+ (IOCP.EQ.0.AND.IOSP.EQ.0.AND.ICOS.NE.0))
C
IF (IG03.NE.0)
IPSN=IG03
IG03=IWRK(IG03)
ELSE
IPWU=IPWU-3
IF (IPWU.LE.IPWL)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
IPSN=IPWU
END IF
C
RWRK(IPSN )=XMIN
RWRK(IPSN+1)=YMIN
IWRK(IPSN+2)=0
C
IF (IG03.NE.0)
IPPN=IG03
IG03=IWRK(IG03)
ELSE
IPWU=IPWU-3
IF (IPWU.LE.IPWL)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
IPPN=IPWU
END IF
C
IWRK(IPPN )=IPSN
IWRK(IPPN+1)=IPSN
IWRK(IPPN+2)=IPPL
C
IPPL=IPPN
IWRK(IPNL+9)=IPPN
IWRK(IPNN+9)=IPPN
C
ELSE
C
IWRK(IPNL+9)=0
IWRK(IPNN+9)=0
C
END IF
C
C Put the current LMT node on the appropriate garbage list for re-use.
C
IWRK(ILMT)=IG03
IG03=ILMT
C
C Advance to the next element of the LMT.
C
ILMT=IWRK(ILMT+2)
C
C End of the loop through the LMT.
C
END LOOP
C
C At this point, if the AET is empty, the scanbeam loop is exited.
C
103 EXIT IF (IAET.EQ.0)
C
C Scan the AET to compute the value of the Y coordinate at the top of
C the scanbeam (YTOS) and to look for horizontal edges in the list.
C
ITMP=IAET
C
YTOS=RWRK(ITMP+2)
C
IF (ILMT.NE.0) YTOS=MIN(YTOS,RWRK(ILMT))
C
LOOP
C
C Check for a horizontal section.
C
IF (YTOS.EQ.YBOS)
C
C Step through points in the user's arrays until the end of the
C horizontal section is reached, updating the X coordinate and the
C index of the successor edge as we go.
C
INNP=ABS(IWRK(ITMP+8))
C
LOOP
C
IF (IWRK(ITMP+4).EQ.0)
IF (INNP.LT.1)
INNP=INNP+LCCP
ELSE IF (INNP.GT.LCCP)
INNP=INNP-LCCP
END IF
EXIT IF (YCCP(INNP).NE.YBOS)
RWRK(ITMP)=XCCP(INNP)
ELSE
IF (INNP.LT.1)
INNP=INNP+LCSP
ELSE IF (INNP.GT.LCSP)
INNP=INNP-LCSP
END IF
EXIT IF (YCSP(INNP).NE.YBOS)
RWRK(ITMP)=XCSP(INNP)
END IF
C
RWRK(ITMP+1)=RWRK(ITMP)
C
IWRK(ITMP+8)=SIGN(INNP,IWRK(ITMP+8))
INNP=INNP+SIGN(1,IWRK(ITMP+8))
C
END LOOP
C
C Compute a quantity that will be used to recognize the successor of
C the horizontal edge.
C
INNL=ABS(IWRK(ITMP+8))-SIGN(1,IWRK(ITMP+8))
IF (IWRK(ITMP+4).EQ.0)
IF (INNL.LT.1)
INNL=INNL+LCCP
ELSE IF (INNL.GT.LCCP)
INNL=INNL-LCCP
END IF
ELSE
IF (INNL.LT.1)
INNL=INNL+LCSP
ELSE IF (INNL.GT.LCSP)
INNL=INNL-LCSP
END IF
END IF
INNL=-SIGN(INNL,IWRK(ITMP+8))
C
C Zero the pointer to the list of intersection points.
C
IINT=0
C
C Save the current value of the pointer to the last word currently used
C in the lower end of the workspace, so that the space occupied by the
C list of intersection points can easily be reclaimed.
C
ISWL=IPWL
C
C Initialize pointers used below. The horizontal edge is considered
C to intersect edges that it actually passes over. If there are edges
C in the AET with X coordinates equal to the X coordinate of the end of
C the horizontal edge, it only intersects them if that is necessary in
C order to make it and its successor be next to each other in the AET.
C
IINN=-1
IINQ=0
C
C Generate the list of intersection points, either to the left ...
C
IF (IWRK(ITMP+7).NE.0)
C
IDUM=IWRK(ITMP+7)
C
LOOP
C
EXIT IF (RWRK(IDUM).LT.RWRK(ITMP))
C
IF (IWRK(IDUM+4).EQ.IWRK(ITMP+4).AND.
+ IWRK(IDUM+8).EQ.INNL)
IINQ=IINN
EXIT
END IF
C
IF (IINT.EQ.0)
IINT=IPWL+1
ELSE
IWRK(IINN+4)=IPWL+1
END IF
C
IINN=IPWL+1
IPWL=IPWL+5
C
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
C
RWRK(IINN)=RWRK(IDUM)
RWRK(IINN+1)=YBOS
IWRK(IINN+2)=IDUM
IWRK(IINN+3)=ITMP
IWRK(IINN+4)=0
C
IF (RWRK(IDUM).GT.RWRK(ITMP)) IINQ=IINN
C
IDUM=IWRK(IDUM+7)
C
EXIT IF (IDUM.EQ.0)
C
END LOOP
C
END IF
C
C ... or to the right.
C
IF (IINQ.EQ.0)
C
IINT=0
IPWL=ISWL
IINN=-1
C
IF (IWRK(ITMP+6).NE.0)
C
IDUM=IWRK(ITMP+6)
C
LOOP
C
EXIT IF (RWRK(IDUM).GT.RWRK(ITMP))
C
IF (IWRK(IDUM+4).EQ.IWRK(ITMP+4).AND.
+ IWRK(IDUM+8).EQ.INNL)
IINQ=IINN
EXIT
END IF
C
IF (IINT.EQ.0)
IINT=IPWL+1
ELSE
IWRK(IINN+4)=IPWL+1
END IF
C
IINN=IPWL+1
IPWL=IPWL+5
C
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
C
RWRK(IINN)=RWRK(IDUM)
RWRK(IINN+1)=YBOS
IWRK(IINN+2)=ITMP
IWRK(IINN+3)=IDUM
IWRK(IINN+4)=0
C
IF (RWRK(IDUM).LT.RWRK(ITMP)) IINQ=IINN
C
IDUM=IWRK(IDUM+6)
C
EXIT IF (IDUM.EQ.0)
C
END LOOP
C
END IF
C
END IF
C
C Clear entries at the end of the intersection list that don't need to
C be considered to be intersections. (This may clear the whole list.)
C
IF (IINQ.EQ.0)
IINT=0
IPWL=ISWL
ELSE IF (IINQ.GT.0)
IWRK(IINQ+4)=0
END IF
C
C If any intersection points were found, process them and then reclaim
C the space used for the list.
C
IF (IINT.NE.0)
INVOKE (PROCESS-INTERSECTION-LIST)
IPWL=ISWL
END IF
C
C The horizontal edge is terminating at this point, so handle that.
C
INVOKE (PROCESS-TERMINATING-EDGE)
C
C Go back to see if the AET is empty now and, if not, to rescan it for
C more horizontal segments.
C
GO TO 103
C
END IF
C
C Move to the next node in the AET.
C
ITMP=IWRK(ITMP+6)
C
C Quit if there are none.
C
EXIT IF (ITMP.EQ.0)
C
C Update the variable that says where the top of the scanbeam is.
C
YTOS=MIN(YTOS,RWRK(ITMP+2))
C
END LOOP
C
C Create a table of all intersections of edges in the AET, sorted in
C order of increasing Y coordinate. To do this, we also create a table
C of the current edges in the AET, sorted in the opposite order in which
C they intersect the top of the scanbeam. Initially, the intersection
C table is empty:
C
IINT=0
C
C The intersection table and the sorted edge table are formed in the
C lower part of the workspace array. The value of the pointer to the
C last word currently used in that part of the workspace is saved so
C that, when we are done using the INT and the SET, the space used for
C them can be reclaimed by just restoring the value of this pointer:
C
ISWL=IPWL
C
C Initialize the "Sorted Edge Table" to contain just the first edge
C from the AET.
C
ISET=IPWL+1
C
IPWL=IPWL+3
C
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
C
RWRK(ISET)=RWRK(IAET+1)+(YTOS-RWRK(IAET+2))*RWRK(IAET+3)
IWRK(ISET+1)=IAET
IWRK(ISET+2)=0
C
C Examine each of the remaining edges in the AET, one at a time,
C looking for intersections with edges that have already gone into
C the SET; for each one found, generate an entry in the INT. Special
C care is taken to ensure that edges which are each other's successors
C end up adjacent to each other in the AET.
C
ITMP=IWRK(IAET+6)
C
LOOP
C
EXIT IF (ITMP.EQ.0)
C
XTMP=RWRK(ITMP+1)+(YTOS-RWRK(ITMP+2))*RWRK(ITMP+3)
C
IST1=0
IST2=ISET
C
LOOP
C
EXIT IF (IST2.EQ.0)
EXIT IF (XTMP.GT.RWRK(IST2))
C
IF (XTMP.EQ.RWRK(IST2))
C
IST3=IWRK(IST2+2)
IST4=0
C
LOOP
C
EXIT IF (IST3.EQ.0)
EXIT IF (XTMP.NE.RWRK(IST3))
C
IF (IWRK(IWRK(IST3+1)+4).EQ. IWRK(ITMP+4).AND.
+ IWRK(IWRK(IST3+1)+8).EQ.-IWRK(ITMP+8) )
IST4=1
EXIT
END IF
C
IST3=IWRK(IST3+2)
C
END LOOP
C
EXIT IF (IST4.EQ.0)
C
XINT=XTMP
YINT=YTOS
C
ELSE
C
IF (ABS(RWRK(ITMP+3)-RWRK(IWRK(IST2+1)+3)).GT.1.E-6)
YINT=YBOS-(RWRK(ITMP )-RWRK(IWRK(IST2+1) ))/
+ (RWRK(ITMP+3)-RWRK(IWRK(IST2+1)+3))
ELSE
YINT=.5*(YBOS+YTOS)
END IF
C
IF (ABS(RWRK(ITMP+3)).LT.ABS(RWRK(IWRK(IST2+1)+3)))
XINT=RWRK(ITMP+1)+(YINT-RWRK(ITMP+2))*RWRK(ITMP+3)
ELSE
XINT=RWRK(IWRK(IST2+1)+1)+(YINT-RWRK(IWRK(IST2+1)+2))*
+ RWRK(IWRK(IST2+1)+3)
END IF
C
END IF
C
IINN=IPWL+1
IPWL=IPWL+5
C
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
C
RWRK(IINN)=XINT
RWRK(IINN+1)=YINT
IWRK(IINN+2)=IWRK(IST2+1)
IWRK(IINN+3)=ITMP
C
IIN1=0
IIN2=IINT
C
LOOP
EXIT IF (IIN2.EQ.0)
EXIT IF (RWRK(IINN+1).LE.RWRK(IIN2+1))
IIN1=IIN2
IIN2=IWRK(IIN2+4)
END LOOP
C
IF (IIN1.EQ.0)
IINT=IINN
ELSE
IWRK(IIN1+4)=IINN
END IF
C
IWRK(IINN+4)=IIN2
C
IST1=IST2
IST2=IWRK(IST2+2)
C
END LOOP
C
ISTN=IPWL+1
IPWL=IPWL+3
C
IF (IPWL.GE.IPWU)
INVOKE (WORKSPACE-TOO-SMALL,NR)
END IF
C
IF (IST1.EQ.0)
ISET=ISTN
ELSE
IWRK(IST1+2)=ISTN
END IF
C
RWRK(ISTN)=XTMP
IWRK(ISTN+1)=ITMP
IWRK(ISTN+2)=IST2
C
ITMP=IWRK(ITMP+6)
C
END LOOP
C
C If intersections have been found, process them.
C
IF (IINT.NE.0)
INVOKE (PROCESS-INTERSECTION-LIST)
END IF
C
C Discard the intersection table and the sorted edge table.
C
IPWL=ISWL
C
C Loop through all the edges in the AET, updating the X coordinates and
C further processing those that terminate at the top of the scanbeam.
C
ITMP=IAET
C
LOOP
C
C Exit if all the edges have been done.
C
EXIT IF (ITMP.EQ.0)
C
C Update the X coordinate to its position at the top of the scanbeam.
C
RWRK(ITMP)=RWRK(ITMP+1)+(YTOS-RWRK(ITMP+2))*RWRK(ITMP+3)
C
C If the edge terminates at the top of this scanbeam, process it.
C
IF (RWRK(ITMP+2).EQ.YTOS)
INVOKE (PROCESS-TERMINATING-EDGE)
END IF
C
C Advance to the next edge in the AET.
C
ITMP=IWRK(ITMP+6)
C
C End of loop on edges in the AET.
C
END LOOP
C
C End of scanbeam loop.
C
END LOOP
C
C Dump out all the polygons that have been formed.
C
C THE FOLLOWING CODE HAS BEEN REPLACED BY CODE THAT CULLS OUT DUPLICATE
C ADJACENT POINTS. SINCE THE REPLACEMENT CODE IS SLOWER, IT WOULD BE
C ADVANTAGEOUS TO FIGURE OUT (ABOVE) HOW TO PREVENT THE DUPLICATES FROM
C SNEAKING IN. ONCE THAT HAS BEEN DONE, THE FOLLOWING CODE CAN BE PUT
C BACK IN:
C
C MXYC=(IPWU-1-IPWL)/2
C IPXC=IPWL
C IPYC=IPWL+MXYC