! Polygon Fill, by Gordon T.
! This routine has been brought from KB (from the APM) and implemented
! on the APOLLO and then moved to the MG1, and then for the Laserjet...

%routine Polyfill(%integer NE, %record (pointfm) %array %name PP)
!   %own %long %real Epson Offset = 0
   %integer min = 10000, max = -100, i

   %for i = 1,1,NE %cycle
      min = (pp(i)_y) %if (pp(i)_y) < min
      max = (pp(i)_y) %if (pp(i)_y) > max
   %repeat

   %begin
      %integer i

      %record %format EdgeFm(%integer   dy, y, %long %real x, dx,
                             %record(EdgeFm) %name Next)
      %record(EdgeFm) %name %array Edges(min:max)
      %record(EdgeFm) %name  Act, t1, t2, e1, e2, e3, e4, Head
      %record(EdgeFm) %array Edg(1:NE)
      %integer Scan Line
      %long %real X1, X2
       
      ! *******************************************************************
      
      %record(EdgeFm) %function Create Edge(%record(PointFm) ed1, ed2)
         ! ed1_y > ed2_y
         %record(EdgeFm) t
       
         t_x = ed1_x
         t_y = ed1_y
         %if ed1_y = ed2_y  %start
            t_dx = ed2_x - ed1_x
         %else
            t_dx = (ed2_x - ed1_x)/(ed1_y - ed2_y)
         %finish
         t_dy = ed1_y - ed2_y
         t_Next == nil
         %result = t
      %end
       
      ! *******************************************************************

      %predicate List Sorted On X(%record(EdgeFm) %name Head)

         %long %real Last X
         %record(EdgeFm) %name e1

         Last X = -1
         e1 == Head
         %while %not(e1 == nil) %cycle
            %if Last X > e1_x %start 
               %false
            %else 
               Last X = e1_x
               e1 == e1_Next
            %finish
         %repeat

         %true

      %end

      ! ****************************************************************

      %routine Insert On X    
      
         ! Head = top and e2 = inserted

         %integer Flag = 1

         Flag = 0 %if Head == nil
         e1 == Head
         %while %not(e2 == nil) %cycle
            e4 == Head
            %while (%not(e1 == nil)) %and (e2_x >= e1_x) %cycle
               e4 == e1
               e1 == e1_Next
            %repeat
          
            %if e1 == nil %start
               %if Flag # 0 %start
                  e4_Next == e2
                  e2 == e2_Next
                  e4 == e4_Next
                  e4_Next == nil
               %else 
                  Head == e2
                  e2 == e2_Next
                  Head_Next == nil
                  Flag = 1
               %finish
            %else 
               e3 == e2
               e2 == e2_Next
               e3_Next == e1
               %if %not(e1 == Head) %then e4_Next == e3 %else Head == e3
            %finish
            e1 == Head
         %repeat

      %end

      ! *******************************************************************

      %routine Remove Rec(%integer Val)

         %record(EdgeFm) %name First, Second

         Act == Act_Next %while %not(Act == nil) %and (Act_dy = Val)

         First == Act
         %while %not(First == nil) %cycle
            Second == First_Next
            %if %not(Second == nil) %and (Second_dy = Val) %start
               First_Next == Second_Next 
            %else 
               First == First_Next
            %finish
         %repeat
      %end

      ! *******************************************************************

      %for i = 1,1,NE - 1 %cycle
         %if pp(i)_y > pp(i+1)_y %start
            Edg(i) = Create Edge (pp(i),pp(i+1))
         %else
            Edg(i) = Create Edge (pp(i+1),pp(i)) 
         %finish
      %repeat

      %if pp(NE)_y > pp(1)_y %start
         Edg(NE) = Create Edge(pp(NE), pp(1))
      %else
         Edg(NE) = Create Edge(pp(1), pp(NE))
      %finish
      Edges(i) == nil %for i = min, 1, max 

      %for i = 1,1,NE %cycle
         %if Edges(Edg(i)_y) == nil %start
            Edges(Edg(i)_y) == Edg(i)
         %else 
            t1 == Edges(Edg(i)_y)
            t1 == t1_Next %while %not(t1_Next == nil)
            t1_Next == Edg(i)
          %finish
      %repeat

      Min = WLY %if Min < WLY
      Scan Line = max
      Max = WHY %if Max > WHY
      Act == nil

      %while Scan Line > min %cycle
         %if %not(List Sorted On X(Act)) %start
            Head == nil
            e2   == Act
            Insert On X
            Act == Head
         %finish
         Head == Act
         e2 == Edges(Scan Line)
         Insert On X
         Act == Head
         ! Inserts a new record and sorts the list pointed to by Act on x
         Remove Rec(-1)
         ! removes a record if the value of dy = -1
         Remove Rec(0) %if %not(Edges(Scan Line) == nil)
         %if Act == nil %then t1 == nil %else t1 == Act_Next
         t2 == Act
         ! point to two Edges to generate two points
         %while %not(t2 == nil) %and %not(t1 == nil) %cycle
            %if WLX > t2_x %then x2 = WLX %else x2=t2_x
            %if WHX < t1_x %then x1 = WHX %else x1=t1_x
            %if 0 < Scan Line < Max %start
               Draw Box(Round(x2), Scan Line, Round(x1), Scan Line)
            %finish
            t2 == t1_Next
            %if t2 == nil %then t1 == nil %else t1 == t2_Next
         %repeat
         t1 == Act
         %while %not(t1 == nil) %cycle
            ! Compute Point t1 for next scan line
            t1_x = t1_x + t1_dx {+ t1_dx*Epson Offset
            t1_dy = t1_dy - 1
            t1 == t1_Next
         %repeat
         Scan Line = Scan Line - 1
      %repeat
   %end
%end

%end %of %file