%! This is a PostScript library meant to be included in other files %%% %% Postscript Code by Jon Monsarrat Copyright 1991 %% permission given for anything except selling this or deleting the header. %%%%%%%%%%% - Approx array %%%%%%%%%%%%%%%%% % Approx flattens a path into a series of lines. % This new flattened path is returned as a triple-array path representation. % The path is broken into sub-paths which have a double-array representation. % Each sub-path breaks into vertices which have a single-array representation. % Each vertex is of the form X Y. We're doing a fill here so any % unclosed subpaths get closed. That's how postscript normally handles fill. % It would be easier to use [ X Y ] vertices, but that would waste memory! /Approx { [ [ { /Y exch def /X exch def ] [ X Y } { } { } { X Y } pathforall ] ] } bind def %%%%%%%%%%%%%%%%%%% array num bool SortArray array %%%%%%%%%%%%%%% % SortArray bubble sorts "array" of packets in increasing order, packets are % groups of numbers and a packet is of size "num". Sorting is done based % on the value of the first item in each packet. When sorting is done, % SortArray goes through and deletes all equal packets if "bool" is true. /SortArray { 10 dict begin /DelEquals exch def /Pack exch def /newlist exch def 0 Pack newlist length 2 Pack mul sub { /anum exch def anum Pack add Pack newlist length 1 Pack mul sub { /bnum exch def newlist anum get newlist bnum get ge { /flag true def newlist anum get newlist bnum get eq Pack 2 eq and { /flag false def newlist anum 1 add get newlist bnum 1 add get add 0 eq { newlist anum 1 add get 1 eq ontop xor { /flag true def } if } if } if flag { 0 1 Pack 1 sub { /ind exch def /temp newlist anum ind add get def newlist anum ind add newlist bnum ind add get put newlist bnum ind add temp put } for } if } if } for } for DelEquals % if this boolean is true, delete all equal packs { [ 0 Pack newlist length 2 Pack mul sub { /anum exch def newlist anum get newlist anum Pack add get ne { 0 1 Pack 1 sub { anum add newlist exch get } for } if } for 0 1 Pack 1 sub { /ind exch def newlist newlist length Pack sub ind add get } for ] } { newlist } ifelse end % temp dict 10 } bind def %%%%%%%%%%%%%%%%%% bool CheeseY X1 W1 or nothing %%%%%%%%%% % CheeseY uses defined variables Y1 (a number), oldx, oldy, newx, newy. % CheeseY asks "does the line segment bounded by oldxy, newxy cross y=Y1? % If so, CheeseY leaves X1 W on the stack, where (X1,Y1) is the point of % intersection. The winding value W is calculated from the sign of the slope. % CheeseY takes one argument which is a boolean value. This boolean is % true is the Y1 value is "on top" of the region of interest, false if "below". % This is to deal correctly with line segments which end on the y=Y1 line. % These special line segments are ignored if they don't pass through the % region of interest. It would be easier to use [ X W ] but memory wasteful. /CheeseY { /top exch def oldy newy 2 copy gt { exch } if Y1 ge exch Y1 le and { oldy newy ne { oldx newx sub oldy newy sub div oldy Y1 sub mul oldx exch sub oldy newy lt { 1 } { -1 } ifelse } { newx 0 } ifelse % If the line segment does NOT go through region of interest % but rather just happens to end on line y=Y1, don't use it. oldy Y1 eq { dup top { -1 } { 1 } ifelse ne { pop pop } if } { newy Y1 eq { dup top { 1 } { -1 } ifelse ne { pop pop } if } if } ifelse } if } bind def %%%%%%%%%%%%%%%%%%%%% array num bool CheeseWhiz array %%%%%%%%%%%%%%%%% % CheeseWhiz traverses the flattened path as computed by Approx to find % any points of intersection with the line y=Y1, where Y1 is it's num argument. % It's boolean argument is true if y=Y1 bounds the region of interest "on top". % For all points of intersection X1 goes on the stack, where [ X1 Y1 ] % is the point, BUT ONLY IF the winding value or evenodd calculation says % to. The winding value is complex and calculated from the sign of the slope. % CheeseWhiz does this by breaking the path into line segments and passing % it to CheeseY. The final array of X1 values is sorted, keeping duplicates. /CheeseWhiz { 15 dict begin /ontop exch def /Y1 exch def [ exch { /oldx (Begin) def /flag false def { flag { /newy exch def oldx (Begin) eq { /firstx newx def /firsty newy def} { ontop CheeseY } ifelse /oldx newx def /oldy newy def } { /newx exch def } ifelse /flag flag not def } forall oldx (Begin) ne { /newx firstx def % Even if the subpath is not closed, PostScript /newy firsty def % fill methodology says close it. So wrap around. ontop CheeseY } if } forall ] % Sort the array of X W values 2 false SortArray % Now go through and take out X's where there is no inside/outside change [ exch fillout { LM exch } if /winding 0 def /inside false def % always start off outside /flag false def { flag { winding add /winding exch def evenodd not { winding 0 eq inside xor { pop } { /inside inside not def } ifelse } if } if /flag flag not def } forall fillout { RM } if ] end % temp dict 15 } def %% End of PostScript Path-breaking Library