summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/dvips/pst-intersect
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2014-02-21 00:22:39 +0000
committerKarl Berry <karl@freefriends.org>2014-02-21 00:22:39 +0000
commita5737bc6edabf060276b0476fcbe35e3088a5e24 (patch)
tree574ccf5c3926bfb1a0c1f2e5200e7b5e9f5fdf1a /Master/texmf-dist/dvips/pst-intersect
parentaf161732d0da218229ae153646c74621e65a75a8 (diff)
pst-intersect (19feb14)
git-svn-id: svn://tug.org/texlive/trunk@33014 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/dvips/pst-intersect')
-rw-r--r--Master/texmf-dist/dvips/pst-intersect/pst-intersect.pro1069
1 files changed, 1069 insertions, 0 deletions
diff --git a/Master/texmf-dist/dvips/pst-intersect/pst-intersect.pro b/Master/texmf-dist/dvips/pst-intersect/pst-intersect.pro
new file mode 100644
index 00000000000..fc0492bb9f5
--- /dev/null
+++ b/Master/texmf-dist/dvips/pst-intersect/pst-intersect.pro
@@ -0,0 +1,1069 @@
+%%
+%% This is file `pst-intersect.pro',
+%% generated with the docstrip utility.
+%%
+%% The original source files were:
+%%
+%% pst-intersect.dtx (with options: `prolog')
+%%
+%% This is a generated file.
+%%
+%% Project: pst-intersect
+%% Version: 0.1 (2014/02/19)
+%%
+%% Copyright (C) 2007-2014 by Christoph Bersch <usenet@bersch.net>
+%%
+%% This work may be distributed and/or modified under the
+%% conditions of the LaTeX Project Public License, either version 1.3c
+%% of this license or (at your option) any later version.
+%% The latest version of this license is in
+%% http://www.latex-project.org/lppl.txt
+%% and version 1.3c or later is part of all distributions of LaTeX
+%% version 2008/05/04 or later.
+%%
+%% This work has the LPPL maintenance status "maintained".
+%%
+%% The current maintainer of this work is Christoph Bersch.
+%%
+%% This work consists of the files pst-intersect.dtx and pst-intersect.ins
+%% and the derived files
+%% pst-intersect.sty, pst-intersect.tex, pst-intersect.pro.
+%%
+/tx@IntersectDict 200 dict def
+tx@IntersectDict begin
+/VecAdd {
+ 3 -1 roll add 3 1 roll add exch
+} bind def
+/VecSub {
+ neg 3 -1 roll add 3 1 roll neg add exch
+} bind def
+/VecScale {
+ dup 4 -1 roll mul 3 1 roll mul
+} bind def
+/ToVec {
+ [ 3 1 roll ]
+} bind def
+/MaxPrecision 1e-6 def
+/Epsilon 1e-4 def
+/MinClippedSizeThreshold 0.8 def
+/H1Interval [0 0.5] def
+/H2Interval [0.5 MaxPrecision add 1] def
+/IntersectBeziers {
+ 2 copy length 2 eq exch length 2 eq and {
+ IntersectLines
+ }{
+ 2 copy [0 1] [0 1] IterateIntersection
+ } ifelse
+ 3 -1 roll exch
+} bind def
+/IntersectLines {
+ (IntersectLines) DebugBegin
+ 2 copy
+ exch { aload pop } forall 5 -1 roll { aload pop } forall
+ 8 -2 roll 2 copy 10 4 roll 4 2 roll 2 copy 6 2 roll 10 2 roll
+ VecSub
+ 6 2 roll 4 2 roll VecSub
+ 8 4 roll 4 2 roll VecSub % X3-X4 Y3-Y4 X2-X1 Y2-Y1 X3-X1 Y3-Y1 % b1 b2 a1 a2 c1 c2
+ 6 copy 12 -4 roll
+ neg 4 -1 roll mul 3 1 roll mul add
+ dup 0 eq {
+ % no intersections
+ 9 { pop } repeat [] []
+ } {
+ dup 10 1 roll 5 1 roll
+ 4 -1 roll mul 3 1 roll mul sub exch div
+ 6 1 roll 4 -1 roll mul 3 1 roll mul sub exch div
+ 2 copy 2 copy 0 ge exch 0 ge and 3 1 roll 1 le exch 1 le and and {
+ [ exch ] exch [ exch ]
+ } {
+ pop pop [] []
+ } ifelse
+ } ifelse
+ DebugEnd
+} bind def
+/IntersectPaths {
+ (IntersectPaths) DebugBegin
+ 6 dict begin
+ 2 copy exch PreparePath dup length /nA exch def
+ exch PreparePath dup length /nB exch def
+ /isect [] def
+ /tA [] def /tB [] def
+ { % [pathA] [Bi]
+ /nB nB 1 sub def
+ exch dup 3 1 roll % [pathA] [Bi] [pathA]
+ {
+ /nA nA 1 sub def
+ exch dup 3 1 roll % [pathA] [Bi] [Aj] [Bi]
+ IntersectBeziers % [curveA] [tA] [curveB] [tB]
+ 4 copy LoadIntersectionPoints
+ [ exch isect aload pop ] /isect exch def
+ exch pop 3 -1 roll pop
+ [ tB aload length 2 add -1 roll TArray { nB add } forall ] /tB exch def
+ [ tA aload length 2 add -1 roll TArray { nA add } forall ] /tA exch def
+ } forall
+ pop % remove [Bi]
+ dup length /nA exch def
+ } forall
+ pop % remove [pathA]
+ [ isect { aload pop } forall ] 3 1 roll tA exch tB
+ % [intersections] [pathA] [tA] [pathB] [tB]
+ end
+ DebugEnd
+} bind def
+/IntersectCurvePath {
+ (IntersectCurvePath) DebugBegin
+ 6 dict begin
+ 2 copy PreparePath dup length /n exch def
+ /isect [] def
+ /tA [] def /tB [] def
+ { % [curveA] [Bi]
+ /n n 1 sub def
+ exch dup 3 -1 roll % [curveA] [curveA] [Bi]
+ IntersectBeziers
+ 4 copy LoadIntersectionPoints % [curveA] [tA] [curveB] [tB]
+ [ exch isect aload pop ] /isect exch def
+ pop 3 -1 roll pop
+ [ tB aload length 2 add -1 roll TArray { n add } forall ] /tB exch def
+ [ tA aload length 2 add -1 roll TArray aload pop ] /tA exch def
+ } forall
+ pop % remove [curveA]
+ [ isect { aload pop } forall ] 3 1 roll tA exch tB
+ % [intersections] [curveA] [tA] [pathB] [tB]
+ end
+ DebugEnd
+} bind def
+/IntersectPathCurve {
+ exch IntersectCurvePath 4 2 roll
+} bind def
+/SaveIntersection {
+ (SaveIntersection) DebugBegin
+ 4 dict dup 10 -1 roll exch def
+ begin %
+ /Points 6 -1 roll def
+ 5 -1 roll dup 4 -1 roll def % /curveA [curveA] [tA] [tB] /curveB /curveB [curveB] def
+ nametostr (@t) strcat cvn exch TArray def % /curveA [curveA] [tA] /curveB@t [tB] def
+ 3 -1 roll dup 4 -1 roll def
+ nametostr (@t) strcat cvn exch TArray def
+ end
+ DebugEnd
+} bind def
+/TArray {
+ (TArray) DebugBegin
+ dup length 0 gt {
+ dup 0 get type /arraytype eq {
+ [ exch
+ { %dup type /nulltype eq { pop exit } if
+ aload pop add 0.5 mul
+ } forall ]
+ } if
+ dup /lt exch quicksort
+ } if
+ DebugEnd %1 debug
+} bind def
+/movetype { /moveto load } bind def
+/linetype { /lineto load } bind def
+/curvetype { /curveto load } bind def
+/PreparePath {
+ [ exch aload pop
+ {
+dup type /nametype eq not { exit } if
+dup /movetype eq {
+ pop ToVec /@mycp exch def
+} {
+ dup /linetype eq {
+pop [ @mycp 4 2 roll 2 copy ToVec /@mycp exch def ToVec ]
+ } {
+pop [ @mycp 8 2 roll 2 copy ToVec /@mycp exch def
+ToVec 5 1 roll ToVec 4 1 roll ToVec 3 1 roll ]
+ } ifelse
+ counttomark 1 roll
+} ifelse
+ } loop ]
+} bind def
+/LoadLineIntersectionPoints {
+ (LoadLineIntersectionPoints) DebugBegin
+ exch [ exch { aload pop } forall ]
+ tx@Dict begin tx@FuncDict begin 2 dict begin
+ dup length 2 idiv 1 sub /BezierType exch def /Points exch def
+ [ exch { GetBezierCoor } forall ]
+ end end end
+ DebugEnd
+} bind def
+/LoadCurveIntersectionPoints {
+ (LoadCurveIntersectionPoints) DebugBegin
+ 2 {
+ 4 2 roll
+ [ exch { aload pop } forall ]
+ exch [ exch { aload pop } forall ]
+ } repeat
+ % [A0.x A0.y ... AM.x AM.y] [tA0a tA0b ... tAMa tAMb] [tB0a tB0b ... tBNa tBNb] [B0.x B0.y ... BN.x BN.y]
+ tx@Dict begin tx@FuncDict begin 2 dict begin
+ dup length 2 idiv 1 sub /BezierType exch def /Points exch def
+ [ exch { GetBezierCoor } forall ]
+ 3 1 roll
+ dup length 2 idiv 1 sub /BezierType exch def /Points exch def
+ [ exch { GetBezierCoor } forall ]
+ end
+ %2 debug
+ % [IB0.xa IB0.ya IB0.xb IB0.yb ... IBM.yb] [IA0.xa IA0.ya IA0.xb IA0.yb ... IAM.yb]
+ 2 {
+ [ exch aload length 4 idiv {
+ [ 5 1 roll ] counttomark 1 roll
+ } repeat ]
+ exch
+ } repeat
+ % [[IB0.xa ...] ... [... IBM.yb]] [[IA0.xa IA0.ya IA0.xb IA0.yb] ...[IAM.xa ... IAM.yb]]
+ 2 {
+ dup hulldict /comp get exch quicksort exch
+ } repeat
+ 2 dict begin
+ /B exch def /A exch def
+ [ 0 1 A length 1 sub {
+ dup A exch get exch B exch get % [IAi] [IBi]
+ 2 copy aload pop VecSub Pyth exch
+ aload pop VecSub Pyth lt { exch } if pop
+ aload pop VecAdd 0.5 VecScale
+ } for
+ % merge near intersection points
+ %counttomark 2 idiv 1 1 3 -1 roll {
+ % pop
+ % counttomark 4 lt { exit } if
+ % 4 copy 4 2 roll ToVec 3 1 roll ToVec AreNear {
+
+ % }
+ %} for
+ ]
+ end
+ end end
+ DebugEnd
+} bind def
+/LoadIntersectionPoints {
+ (LoadIntersectionPoints) DebugBegin
+ 4 copy pop exch pop length 2 eq exch length 2 eq and {
+ pop pop LoadLineIntersectionPoints
+ }{
+ LoadCurveIntersectionPoints
+ } ifelse
+ DebugEnd
+} bind def
+/IterateIntersection {
+ (IterateIntersection) DebugBegin
+ 11 dict begin
+/precision MaxPrecision def
+ /counter 0 def
+/depth 0 def
+/domsA [] def
+/domsB [] def
+/domsA /domsB 6 2 roll _IterateIntersection
+domsB domsA
+ end
+ dup length 0 gt {
+ TArraysRemoveDup
+ } if
+ DebugEnd
+} bind def
+/TArraysRemoveDup {
+ 4 dict begin
+ /tB exch def
+ /tA exch def
+ /j 0 def
+ [ tA 0 get tB 0 get
+ 1 1 tA length 1 sub {
+ /i exch def
+ tA j get aload pop tA i get aload pop tx@Dict begin Pyth2 end MaxPrecision gt
+ tB j get aload pop tB i get aload pop tx@Dict begin Pyth2 end MaxPrecision gt and {
+ % keep the current parameter point
+ /j i def
+ tB i get tA i get
+ counttomark 2 idiv 1 add 1 roll
+ } if
+ } for
+ counttomark 2 idiv 1 add [ exch 1 roll ] % [ ... [tB]
+ counttomark 1 add 1 roll ] exch % [tA] [tB]
+ end
+} bind def
+/_IterateIntersection {
+ (_IterateIntersection) DebugBegin
+ CloneVec /domB exch def
+ CloneVec /domA exch def
+ CloneCurve /CurveB exch def
+ CloneCurve /CurveA exch def
+ /iter 0 def
+ /depth depth 1 add def
+ /dom null def
+ /counter counter 1 add def
+
+ CheckIT {
+(>> curve subdivision performed: dom(A) = ) domA CurveToString strcat
+(, dom(B) = ) strcat domB CurveToString strcat ( <<) strcat ==
+ } if
+ CurveA IsConstant CurveB IsConstant and {
+CurveA MiddlePoint ToVec
+CurveB MiddlePoint ToVec AreNear {
+ domA domB 4 -1 roll exch PutInterval PutInterval
+} {
+ pop pop
+} ifelse
+ }{
+counter 100 lt {
+ {
+/iter iter 1 add def
+iter 100 lt
+domA Extent precision ge
+domB Extent precision ge or and not {
+ iter 100 ge {
+false
+ } {
+CurveA MiddlePoint ToVec
+CurveB MiddlePoint ToVec AreNear {
+ domA domB true
+}{
+ false
+} ifelse
+ } ifelse
+ exit
+} if
+CheckIT {
+ (counter: ) counter 20 string cvs strcat
+ (, iter: ) iter 20 string cvs strcat strcat
+ (, depth: ) depth 20 string cvs strcat strcat ==
+} if
+
+CurveA CurveB ClipCurve /dom exch def
+
+CheckIT {(dom : ) dom CurveToString strcat == } if
+dom IsEmptyInterval {
+ CheckIT { (empty interval, exit) == } if
+ false exit
+} if
+dom aload pop 2 copy min 3 1 roll max gt {
+ CheckIT {
+(dom[0] > dom[1], invalid!) ==
+ } if
+ false exit
+} if
+
+domB dom MapTo /domB exch def
+CurveB dom Portion
+
+CurveB IsConstant CurveA IsConstant and {
+ CheckIT {
+ (both curves are constant: ) ==
+(C1: [ ) CurveA { CurveToString ( ) strcat strcat } forall (]) strcat ==
+(C2: [ ) CurveB { CurveToString ( ) strcat strcat } forall (]) strcat ==
+ } if
+ CurveA MiddlePoint ToVec
+ CurveB MiddlePoint ToVec AreNear {
+domA domB true
+ } {
+false
+ } ifelse
+ exit
+} if
+dom Extent MinClippedSizeThreshold gt {
+ CheckIT {
+(clipped less than 20% : ) ==
+(angle(A) = ) CurveA dup length 1 sub get aload pop
+ CurveA 0 get aload pop VecSub
+ exch 2 copy 0 eq exch 0 eq and {
+ pop pop (NaN)
+ } {
+ atan 20 string cvs
+ } ifelse strcat ==
+ (angle(B) = ) CurveB dup length 1 sub get aload pop
+ CurveB 0 get aload pop VecSub
+ exch 2 copy 0 eq exch 0 eq and {
+ pop pop (NaN)
+ } {
+ atan 20 string cvs
+ } ifelse strcat ==
+ (dom : ) == dom == (domB :) == domB ==
+ } if
+ CurveA CurveB domA domB iter
+ 7 -2 roll 2 copy 9 2 roll 2 copy
+ domA Extent domB Extent gt {
+CurveA CloneCurve dup H1Interval Portion % pC1
+CurveA CloneCurve dup H2Interval Portion % pC2
+domA H1Interval MapTo % dompC1
+domA H2Interval MapTo % dompC2
+3 -1 roll exch % /domsA /domsB /domsA /domsB pC1 dompC1 pC2 dompC2
+CurveB exch domB 8 4 roll % /domsA /domsB pC2 CurveB dompC2 domB /domsA /domsB pC1 dompC1
+CurveB exch domB % /domsA /domsB pC2 CurveB dompC2 domB /domsA /domsB pC1 CurveB dompC1 domB
+ } {
+CurveB CloneCurve dup H1Interval Portion % pC1
+CurveB CloneCurve dup H2Interval Portion % pC2
+domB H1Interval MapTo % dompC1
+domB H2Interval MapTo % dompC2
+8 -2 roll exch 8 2 roll 6 -2 roll exch 6 2 roll % /domsB /domsA /domsB /domsA pC1 pC2 dompC1 dompC2
+3 -1 roll exch % /domsB /domsA /domsB /domsA pC1 dompC1 pC2 dompC2
+CurveA exch domA 8 4 roll % /domsB /domsA pC2 CurveA dompC2 domA /domsB /domsA pC1 dompC1
+CurveA exch domA % /domsB /domsA pC2 CurveA dompC2 domA /domsB /domsA pC1 CurveA dompC1 domA
+ } ifelse
+
+ _IterateIntersection
+ _IterateIntersection
+ /iter exch def
+ /domB exch def
+ /domA exch def
+ /CurveB exch def
+ /CurveA exch def
+ false exit
+} if
+CurveA CurveB /CurveA exch def /CurveB exch def
+domA domB /domA exch def /domB exch def
+exch
+ } loop
+ {
+4 -1 roll exch PutInterval PutInterval
+CheckIT {
+ (found an intersection ============================) ==
+} if
+ } { pop pop } ifelse
+} {
+ pop pop
+} ifelse
+ } ifelse
+ /depth depth 1 sub def
+ DebugEnd
+} bind def
+/PutInterval {
+ CloneVec [ exch 3 -1 roll dup 4 1 roll load aload pop ] def
+} bind def
+/IsEmptyInterval {
+ aload pop 0 eq exch 1 eq and
+} bind def
+/ToUnitInterval {
+ ToUnitRange exch ToUnitRange 2 copy gt {
+exch
+ } if
+ ToVec
+} bind def
+/ToUnitRange {
+ dup 0 lt {
+pop 0
+ }{
+dup 1 gt {
+ pop 1
+} if
+ } ifelse
+} bind def
+/CloneCurve {
+ [ exch {
+CloneVec
+ } forall ]
+} bind def
+/CloneVec {
+ aload pop ToVec
+} bind def
+/MapTo {
+ (MapTo) DebugBegin
+ exch aload 0 get 3 1 roll exch sub 2 copy % [I] J0 Jextent J0 Jextent
+ 5 -1 roll aload aload pop % J0 Jextent J0 Jextent I0 I1 I0 I1
+ min 4 -1 roll mul % J0 Jextent J0 I0 I1 min(I0,I1)*Jextent
+ 4 -1 roll add [ exch % J0 Jextent I0 I1 [ J0new
+ 6 2 roll max mul add ]
+ DebugEnd
+} bind def
+/Portion {
+ (Portion) DebugBegin
+ dup Min 0 eq { % [CurveB] [I]
+Max dup 1 eq {% [CurveB] I.max()
+ % I.max() == 1
+ pop pop
+} { % [CurveB] I.max()
+ LeftPortion
+} ifelse
+ } { % [CurveB] [I]
+2 copy Min % [CurveB] [I] [CurveB] I.min()
+RightPortion
+dup Max 1 eq {
+ % I.max() == 1
+ pop pop
+} {% [CurveB] [I]
+ dup aload pop exch sub 1 3 -1 roll Min sub div % [CurveB] (I1-I0)/(1-I.min())
+ LeftPortion
+} ifelse
+ } ifelse
+ DebugEnd
+} bind def
+/LeftPortion {
+ (LeftPortion) DebugBegin
+ exch dup length 1 sub dup 4 1 roll % L-1 t [CurveB] L-1
+ 1 1 3 -1 roll { % L-1 t [CurveB] i
+4 -1 roll dup 5 1 roll % L-1 t [CurveB] i L-1
+-1 3 -1 roll % L-1 t [CurveB] L-1 -1 i
+{ % L-1 t [CurveB] j
+ 2 copy 5 copy % L-1 t [CurveB] j [CurveB] j t [CurveB] j [CurveB] j
+ 1 sub get 3 1 roll get % L-1 t [CurveB] j [CurveB] j t B[j-1] B[j]
+ Lerp put pop % L-1 t [CurveB]
+} for
+ } for
+ pop pop pop
+ DebugEnd
+} bind def
+/RightPortion {
+ (RightPortion) DebugBegin
+ exch dup length 1 sub dup 4 1 roll % L-1 t [CurveB] L-1
+ 1 1 3 -1 roll {% L-1 t [CurveB] i
+4 -1 roll dup 5 1 roll % L-1 t [CurveB] i L-1
+exch sub 0 1 3 -1 roll % L-1 t [CurveB] 0 1 L-i-1
+{% L-1 t [CurveB] j
+ 2 copy 5 copy
+ get 3 1 roll 1 add get Lerp put pop
+} for
+ } for
+ pop pop pop
+ DebugEnd
+} bind def
+/Lerp {
+ (Lerp) DebugBegin
+ 3 -1 roll dup 1 exch sub 3 1 roll % [A] (1-t) [B] t
+ exch aload pop 3 -1 roll VecScale % [A] (1-t) B.x*t B.y*t
+ 4 2 roll
+ exch aload pop 3 -1 roll VecScale VecAdd ToVec % [A.x*(1-t)+B.x*t A.y*(1-t)+B.y*t]
+ DebugEnd
+} bind def
+/IsConstant {
+ aload length [ exch 1 roll ] true 3 1 roll
+ {
+exch dup 4 1 roll
+AreNear and exch
+ } forall
+ pop
+} bind def
+/AreNear {
+ (AreNear) DebugBegin
+ aload pop 3 -1 roll aload pop
+ 4 copy abs 3 { exch abs max } repeat Epsilon mul
+ dup 6 2 roll VecSub abs 4 -1 roll lt exch abs 3 -1 roll lt and
+ DebugEnd
+} bind def
+/Min {
+ aload pop min
+} bind def
+/Max {
+ aload pop max
+} bind def
+/Extent {
+ aload pop exch sub
+} bind def
+/MiddlePoint {
+ dup dup length 1 sub get aload pop
+ 3 -1 roll 0 get aload pop
+ VecAdd 0.5 VecScale
+} bind def
+/OrthogonalOrientationLine {
+ (OrthogonalOrientationLine) DebugBegin
+ dup dup length 1 sub get aload pop 3 -1 roll 0 get aload pop VecSub
+ neg exch
+ 4 2 roll 2 copy 6 2 roll VecAdd
+ ImplicitLine
+ DebugEnd
+} bind def
+/PickOrientationLine {
+ (PickOrientationLine) DebugBegin
+ dup dup length 1 sub exch 0 get% [Curve] L-1 P0
+ exch -1 1 {% [Curve] P0 i
+3 -1 roll dup 4 1 roll exch get % [Curve] P0 Pi
+2 copy AreNear {
+ pop
+} {
+ exit
+} ifelse
+ } for
+ 3 -1 roll pop
+ exch aload pop 3 -1 roll aload pop ImplicitLine
+ DebugEnd
+} bind def
+/ImplicitLine {
+ 4 copy % Xi Yi Xj Yj Xi Yi Xj Yj
+ 3 -1 roll sub 7 1 roll sub 5 1 roll % Yj-Yi Xi-Xj Xi Yi Xj Yj
+ % Yi*Xj - Xi*Yj
+ 4 -1 roll mul neg % Yj-Yi Xi-Xj Yi Xj -Yj*Xi
+ 3 1 roll mul add % Yj-Yi Xi-Xj Yi*Xj-Yj*Xi | l0 l1 l2
+ 3 1 roll 2 copy tx@Dict begin Pyth end dup dup % l2 l0 l1 L L L
+ 5 -1 roll exch % l2 l1 L L l0 L
+ div 5 1 roll % l0/L l2 l1 L L
+ 3 1 roll div % l0/L l2 L l1/L
+ 3 1 roll div % l0/L l1/L l2/L
+} bind def
+/distance {
+ 5 1 roll 3 -1 roll mul 3 1 roll mul add add
+} bind def
+/ArrayToPointArray {
+ aload length dup 2 idiv {
+3 1 roll [ 3 1 roll ] exch
+dup 1 sub 3 1 roll 1 roll
+ } repeat 1 add [ exch 1 roll ]
+} bind def
+/PointArrayToArray {
+ aload length dup {
+1 add dup 3 -1 roll aload pop 4 -1 roll 1 add 2 roll
+ } repeat 1 add [ exch 1 roll ]
+} bind def
+/ClipCurve {
+ (ClipCurve) DebugBegin
+ 4 dict begin
+ /CurveB exch def /CurveA exch def
+ CurveA IsConstant {
+ CurveA MiddlePoint CurveB OrthogonalOrientationLine
+ } {
+CurveA PickOrientationLine
+ } ifelse
+ CheckIT {
+3 copy exch 3 -1 roll (OrientationLine : )
+3 { exch 20 string cvs ( ) strcat strcat } repeat ==
+ } if
+ CurveA FatLineBounds
+ CheckIT { dup (FatLineBounds : ) exch aload pop exch 20 string cvs (, ) strcat exch 20 string cvs strcat strcat == } if
+ CurveB ClipCurveInterval
+ end
+ DebugEnd
+} bind def
+/FatLineBounds {
+ (FatLineBounds) DebugBegin
+ /dmin 0 def /dmax 0 def
+ {
+4 copy aload pop 5 2 roll distance
+dup dmin lt { dup /dmin exch def } if
+dup dmax gt { dup /dmax exch def } if
+pop pop
+ } forall
+ [dmin dmax]
+ DebugEnd
+} bind def
+/ClipCurveInterval {
+ (ClipCurveInterval) DebugBegin
+ 15 dict begin
+ /curve exch def
+ aload pop 2 copy min /boundMin exch def max /boundMax exch def
+ [ 4 1 roll ] cvx /fatline exch def
+ % number of sub-intervals
+ /n curve length 1 sub def
+ % distance curve control points
+ /D n 1 add array def
+ 0 1 n { % i
+dup curve exch get aload pop % i Pi.x Pi.y
+fatline distance % distance d of Point i from the orientation line, on stack; i d
+exch dup n div % d i i/n
+[ exch 4 -1 roll ] % i [ i/n d ]
+D 3 1 roll put
+ } for
+ D ConvexHull /D exch def
+ /getX { D exch get 0 get } def
+ /getY { D exch get 1 get } def
+ /tmin 1 def /tmax 0 def
+ 0 getY dup
+ boundMin lt /plower exch def
+ boundMax gt /phigher exch def
+ plower phigher or not {
+tmin 0 getX gt { /tmin 0 getX def } if
+tmax 0 getX lt { /tmax 0 getX def } if
+ } if
+ 1 1 D length 1 sub {
+/i exch def
+/clower i getY boundMin lt def
+/chigher i getY boundMax gt def
+clower chigher or not {
+ tmin i getX gt { /tmin i getX def } if
+ tmax i getX lt { /tmax i getX def } if
+} if
+clower plower eq not {
+ boundMin i 1 sub i D Intersect % t on stack
+ dup tmin lt { dup /tmin exch def } if
+ dup tmax gt { dup /tmax exch def } if
+ pop
+ /plower clower def
+} if
+chigher phigher eq not {
+ boundMax i 1 sub i D Intersect
+ dup tmin lt { dup /tmin exch def } if
+ dup tmax gt { dup /tmax exch def } if
+ pop
+ /phigher chigher def
+} if
+ } for
+ /i D length 1 sub def
+ /clower 0 getY boundMin lt def
+ /chigher 0 getY boundMax gt def
+ clower plower eq not {
+boundMin i 0 D Intersect
+dup tmin lt { dup /tmin exch def } if
+dup tmax gt { dup /tmax exch def } if
+pop
+ } if
+ chigher phigher eq not {
+boundMax i 0 D Intersect
+dup tmin lt { dup /tmin exch def } if
+dup tmax gt { dup /tmax exch def } if
+pop
+ } if
+ [tmin tmax]
+ end
+ DebugEnd
+} bind def
+/Intersect {
+ dup 4 -1 roll get aload pop
+ 4 2 roll exch get aload pop
+ 4 2 roll 2 copy 6 2 roll VecSub
+ 5 2 roll
+ neg 3 -1 roll add
+ 3 -1 roll div
+ 3 -1 roll mul add
+} bind def
+/IsPath {
+ dup length 1 sub get type /nametype eq { true } { false } ifelse
+} bind def
+/ShowFullPath {
+ 4 dict begin
+ /movetype /moveto load def
+ /linetype /lineto load def
+ /curvetype /curveto load def
+ mark exch aload pop
+ {
+ counttomark 0 eq { exit } if
+ load exec
+ } loop
+ pop
+ end
+} bind def
+/ShowPathPortion {
+ 6 dict begin
+ exch dup 0 lt { pop 0 } if /tstart exch def
+ % if tstart is < 0, use the array length
+ dup 0 lt { pop dup length } if /tstop exch def
+ tstop tstart gt {
+ /movetype /moveto load def
+ /linetype /lineto load def
+ /curvetype /curveto load def
+ /n 0 def
+ mark exch aload pop
+ {
+ counttomark 0 eq { pop exit } if
+ dup /movetype eq not { /n n 1 add def } if
+ % current section is after tstart
+ n tstop sub 1 ge { cleartomark exit } if
+
+ dup /movetype eq {
+ load exec
+ } {
+ tstart n gt {
+ % current path section is before tstart
+ /curvetype eq { 6 2 roll 4 { pop } repeat } if
+ movetype
+ } {
+ tstart n 1 sub gt tstop n lt or {
+ % draw a truncated section
+ tstart n sub 1 add tstop n sub 1 add
+ ToUnitInterval exch
+ /linetype eq {
+ 3 1 roll ToVec currentpoint ToVec exch ToVec
+ dup 3 -1 roll Portion
+ aload pop exch
+ tstart n 1 sub gt { aload pop moveto } { pop } ifelse
+ aload pop lineto
+ } {
+ 7 1 roll [ currentpoint 9 3 roll ] ArrayToPointArray
+ dup 3 -1 roll Portion
+ { aload pop } forall
+ 8 -2 roll
+ tstart n 1 sub gt { moveto } { pop pop } ifelse
+ curveto
+ } ifelse
+ }{
+ load exec
+ } ifelse
+ } ifelse
+ } ifelse
+ } loop
+ } if
+ end
+} bind def
+ % Graham Scal algorithm to compute the convex hull of a set of
+ % points. Code written by Bill Casselman,
+ % http://www.math.ubc.ca/~cass/graphics/text/www/
+ %
+ % [[X1 Y1] [X2 Y2] ... [Xn Yn]] hull -> [[...] ... [...]]
+ %
+/hulldict 32 dict def
+hulldict begin
+
+ % u - v
+/vsub { 2 dict begin
+/v exch def
+/u exch def
+[
+ u 0 get v 0 get sub
+ u 1 get v 1 get sub
+]
+end } def
+
+ % u - v rotated 90 degrees
+/vperp { 2 dict begin
+/v exch def
+/u exch def
+[
+ v 1 get u 1 get sub
+ u 0 get v 0 get sub
+]
+end } def
+
+/dot { 2 dict begin
+/v exch def
+/u exch def
+ v 0 get u 0 get mul
+ v 1 get u 1 get mul
+ add
+end } def
+
+ % P Q
+ % tests whether P < Q in lexicographic order
+ % i.e xP < xQ, or yP < yQ if xP = yP
+/comp { 2 dict begin
+/Q exch def
+/P exch def
+P 0 get Q 0 get lt
+ P 0 get Q 0 get eq
+ P 1 get Q 1 get lt
+ and
+or
+end } def
+
+end
+
+ % args: an array of points C
+ % effect: returns the array of points on the boundary of
+ % the convex hull of C, in clockwise order
+
+/ConvexHull {
+(ConvexHull) DebugBegin
+hulldict begin
+/C exch def
+/comp C quicksort
+/n C length def
+ % Q might circle around to the start
+/Q n 1 add array def
+Q 0 C 0 get put
+Q 1 C 1 get put
+/i 2 def
+/k 2 def
+ % i is next point in C to be looked at
+ % k is next point in Q to be added
+ % [ Q[0] Q[1] ... ]
+ % scan the points to make the top hull
+n 2 sub {
+ % P is the current point at right
+ /P C i get def
+ /i i 1 add def
+ {
+ % if k = 1 then just add P
+ k 2 lt { exit } if
+ % now k is 2 or more
+ % look at Q[k-2] Q[k-1] P: a left turn (or in a line)?
+ % yes if (P - Q[k-1])*(Q[k-1] - Q[k-2])^perp >= 0
+ P Q k 1 sub get vsub
+ Q k 1 sub get Q k 2 sub get vperp
+ dot 0 lt {
+ % not a left turn
+ exit
+ } if
+ /k k 1 sub def
+ } loop
+ Q k P put
+ /k k 1 add def
+} repeat
+
+ % done with top half
+ % K is where the right hand point is
+/K k 1 sub def
+
+/i n 2 sub def
+Q k C i get put
+/i i 1 sub def
+/k k 1 add def
+n 2 sub {
+ % P is the current point at right
+ /P C i get def
+ /i i 1 sub def
+ {
+ % in this pass k is always 2 or more
+ k K 2 add lt { exit } if
+ % look at Q[k-2] Q[k-1] P: a left turn (or in a line)?
+ % yes if (P - Q[k-1])*(Q[k-1] - Q[k-2])^perp >= 0
+ P Q k 1 sub get vsub
+ Q k 1 sub get Q k 2 sub get vperp
+ dot 0 lt {
+ % not a left turn
+ exit
+ } if
+ /k k 1 sub def
+ } loop
+ Q k P put
+ /k k 1 add def
+} repeat
+
+ % strip Q down to [ Q[0] Q[1] ... Q[k-2] ]
+ % excluding the doubled initial point
+[ 0 1 k 2 sub {
+ Q exch get
+} for ]
+end
+DebugEnd
+} def
+
+/qsortdict 8 dict def
+
+qsortdict begin
+
+ % args: /comp a L R x
+ % effect: effects a partition into two pieces [L j] [i R]
+ % leaves i j on stack
+
+/partition { 8 dict begin
+/x exch def
+/j exch def
+/i exch def
+/a exch def
+dup type /nametype eq { load } if /comp exch def
+{
+ {
+ a i get x comp exec not {
+ exit
+ } if
+ /i i 1 add def
+ } loop
+ {
+ x a j get comp exec not {
+ exit
+ } if
+ /j j 1 sub def
+ } loop
+
+ i j le {
+ % swap a[i] a[j]
+ a j a i get
+ a i a j get
+ put put
+ /i i 1 add def
+ /j j 1 sub def
+ } if
+ i j gt {
+ exit
+ } if
+} loop
+i j
+end } def
+
+ % args: /comp a L R
+ % effect: sorts a[L .. R] according to comp
+/subsort {
+ % /c a L R
+[ 3 1 roll ] 3 copy
+ % /c a [L R] /c a [L R]
+aload aload pop
+ % /c a [L R] /c a L R L R
+add 2 idiv
+ % /c a [L R] /c a L R (L+R)/2
+3 index exch get
+ % /c a [L R] /c a L R x
+partition
+ % /c a [L R] i j
+ % if j > L subsort(a, L, j)
+dup
+ % /c a [L R] i j j
+3 index 0 get gt {
+ % /c a [L R] i j
+ 5 copy
+ % /c a [L R] i j /c a [L R] i j
+ exch pop
+ % /c a [L R] i j /c a [L R] j
+ exch 0 get exch
+ % ... /c a L j
+ subsort
+} if
+ % /c a [L R] i j
+pop dup
+ % /c a [L R] i i
+ % if i < R subsort(a, i, R)
+2 index 1 get lt {
+ % /c a [L R] i
+ exch 1 get
+ % /c a i R
+ subsort
+}{
+ 4 { pop } repeat
+} ifelse
+} def
+
+end % qsortdict
+
+ % args: /comp a
+ % effect: sorts the array a
+ % comp returns truth of x < y for entries in a
+
+/quicksort { qsortdict begin
+dup length 1 gt {
+ % /comp a
+dup
+ % /comp a a
+length 1 sub
+ % /comp a n-1
+0 exch subsort
+} {
+pop pop
+} ifelse
+end } def
+/debug {
+ dup 1 add copy {==} repeat pop
+} bind def
+/DebugIT false def
+/CheckIT false def
+/DebugDepth 0 def
+/DebugBegin {
+ DebugIT {
+ /DebugProcName exch def
+ DebugDepth 2 mul string
+ 0 1 DebugDepth 2 mul 1 sub {
+ dup 2 mod 0 eq { (|) }{( )} ifelse
+ 3 -1 roll dup 4 2 roll
+ putinterval
+ } for
+ DebugProcName strcat ==
+ /DebugDepth DebugDepth 1 add def
+ }{
+ pop
+ } ifelse
+} bind def
+/DebugEnd {
+ DebugIT {
+ /DebugDepth DebugDepth 1 sub def
+ DebugDepth 2 mul 2 add string
+ 0 1 DebugDepth 2 mul 1 sub {
+ dup 2 mod 0 eq { (|) }{ ( ) } ifelse
+ 3 -1 roll dup 4 2 roll
+ putinterval
+ } for
+ dup DebugDepth 2 mul (+-) putinterval
+ ( done) strcat ==
+ } if
+} bind def
+/strcat {
+ exch 2 copy
+ length exch length add
+ string dup dup 5 2 roll
+ copy length exch
+ putinterval
+} bind def
+/nametostr {
+ dup length string cvs
+} bind def
+/ShowCurve {
+ { aload pop } forall
+ 8 -2 roll moveto curveto
+} bind def
+/CurveToString {
+ (CurveToString) DebugBegin
+ aload pop ([) 3 -1 roll 20 string cvs strcat (, ) strcat exch 20 string cvs strcat (]) strcat
+ DebugEnd
+} bind def
+end % tx@IntersectDict