diff options
Diffstat (limited to 'Master')
| -rw-r--r-- | Master/texmf-dist/doc/latex/pst-intersect/Changes | 3 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/pst-intersect/README | 24 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/pst-intersect/pst-intersect-DE.pdf | bin | 0 -> 102356 bytes | |||
| -rw-r--r-- | Master/texmf-dist/doc/latex/pst-intersect/pst-intersect.pdf | bin | 0 -> 100306 bytes | |||
| -rw-r--r-- | Master/texmf-dist/dvips/pst-intersect/pst-intersect.pro | 1069 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/pst-intersect/Makefile | 74 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/pst-intersect/pst-intersect.dtx | 3094 | ||||
| -rw-r--r-- | Master/texmf-dist/source/latex/pst-intersect/pst-intersect.ins | 98 | ||||
| -rw-r--r-- | Master/texmf-dist/tex/generic/pst-intersect/pst-intersect.tex | 295 | ||||
| -rw-r--r-- | Master/texmf-dist/tex/latex/pst-intersect/pst-intersect.sty | 50 | ||||
| -rwxr-xr-x | Master/tlpkg/bin/tlpkg-ctan-check | 2 | ||||
| -rw-r--r-- | Master/tlpkg/tlpsrc/collection-pstricks.tlpsrc | 1 | ||||
| -rw-r--r-- | Master/tlpkg/tlpsrc/pst-intersect.tlpsrc | 0 |
13 files changed, 4709 insertions, 1 deletions
diff --git a/Master/texmf-dist/doc/latex/pst-intersect/Changes b/Master/texmf-dist/doc/latex/pst-intersect/Changes new file mode 100644 index 00000000000..a7c17260959 --- /dev/null +++ b/Master/texmf-dist/doc/latex/pst-intersect/Changes @@ -0,0 +1,3 @@ +0.1 2014-02-19 + * First CTAN version + diff --git a/Master/texmf-dist/doc/latex/pst-intersect/README b/Master/texmf-dist/doc/latex/pst-intersect/README new file mode 100644 index 00000000000..a53b15d999c --- /dev/null +++ b/Master/texmf-dist/doc/latex/pst-intersect/README @@ -0,0 +1,24 @@ +------------------------------------------------------------------------ +The pst-intersect package --- Intersecting arbitrary curves +Maintained by Christoph Bersch +E-mail: usenet@bersch.net +Released under the LaTeX Project Public License v1.3c or later +See http://www.latex-project.org/lppl.txt +------------------------------------------------------------------------ + +The package pst-intersect computes the intersections between arbitrary +Postscript paths or Bézier curves using the Bézier clipping algorithm. + +Installation +------------ + +The package is supplied in dtx format and as a pre-extracted zip file, +pst-intersect.tds.zip. The later is most convenient for most users: +simply unzip this in your local texmf directory and run texhash to +update the database of file locations. If you want to unpack the dtx +yourself you must run "tex pst-intersect.ins", to typeset the +documentation run "latex pst-intersect.dtx", or preferably use the +provided Makefile. + +The package requires recent versions of pstricks, pst-node, and +pst-func. diff --git a/Master/texmf-dist/doc/latex/pst-intersect/pst-intersect-DE.pdf b/Master/texmf-dist/doc/latex/pst-intersect/pst-intersect-DE.pdf Binary files differnew file mode 100644 index 00000000000..cf2c3cbb936 --- /dev/null +++ b/Master/texmf-dist/doc/latex/pst-intersect/pst-intersect-DE.pdf diff --git a/Master/texmf-dist/doc/latex/pst-intersect/pst-intersect.pdf b/Master/texmf-dist/doc/latex/pst-intersect/pst-intersect.pdf Binary files differnew file mode 100644 index 00000000000..9c62a7b3f33 --- /dev/null +++ b/Master/texmf-dist/doc/latex/pst-intersect/pst-intersect.pdf 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 diff --git a/Master/texmf-dist/source/latex/pst-intersect/Makefile b/Master/texmf-dist/source/latex/pst-intersect/Makefile new file mode 100644 index 00000000000..43463f8ada8 --- /dev/null +++ b/Master/texmf-dist/source/latex/pst-intersect/Makefile @@ -0,0 +1,74 @@ +.SUFFIXES : .tex .ltx .dvi .ps .pdf .eps + +PACKAGE = pst-intersect + +LATEX = latex + +ARCHNAME = $(PACKAGE)-$(shell date +"%y%m%d") +ARCHNAME_TDS = $(PACKAGE).tds + +ARCHFILES = $(PACKAGE).dtx $(PACKAGE).ins Makefile \ + README Changes $(PACKAGE).pdf $(PACKAGE)-DE.pdf + +PS2PDF = GS_OPTIONS=-dPDFSETTINGS=/prepress ps2pdf + +all : doc doc-DE + +doc : $(PACKAGE).pdf +doc-DE : $(PACKAGE)-DE.pdf + +dist : doc Changes + mkdir -p $(PACKAGE) + cp $(ARCHFILES) $(PACKAGE) + tar chvzf $(ARCHNAME).tar.gz $(PACKAGE) + rm -rf $(PACKAGE) + @ echo + @ echo $(ARCHNAME).tar.gz + +$(PACKAGE).dvi: L = english +$(PACKAGE)-DE.dvi: L = ngerman +%.dvi: $(PACKAGE).dtx $(PACKAGE).sty $(PACKAGE).tex $(PACKAGE).pro + $(LATEX) -jobname=$(basename $@) '\newcommand*{\mainlang}{$(L)}\input{$(PACKAGE).dtx}' + $(LATEX) -jobname=$(basename $@) '\newcommand*{\mainlang}{$(L)}\input{$(PACKAGE).dtx}' + +%.ps: %.dvi + dvips $< +%.pdf: %.ps + $(PS2PDF) $< $@ + +$(PACKAGE).sty $(PACKAGE).pro $(PACKAGE).tex: $(PACKAGE).ins $(PACKAGE).dtx + tex $< + +Changes: Changes.py $(PACKAGE).dtx + python $< + +arch : Changes + zip $(ARCHNAME).zip $(ARCHFILES) + +arch-tds : Changes + $(RM) $(ARCHNAME_TDS).zip + mkdir -p tds/tex/latex/$(PACKAGE) + mkdir -p tds/tex/generic/$(PACKAGE) + mkdir -p tds/doc/latex/$(PACKAGE) + mkdir -p tds/source/latex/$(PACKAGE) + mkdir -p tds/dvips/$(PACKAGE) + cp $(PACKAGE).sty tds/tex/latex/$(PACKAGE)/ + cp $(PACKAGE).tex tds/tex/generic/$(PACKAGE)/ + cp $(PACKAGE).pro tds/dvips/$(PACKAGE)/ + cp Changes $(PACKAGE).pdf $(PACKAGE)-DE.pdf README tds/doc/latex/$(PACKAGE)/ + cp $(PACKAGE).dtx $(PACKAGE).ins Makefile \ + tds/source/latex/$(PACKAGE)/ + cd tds ; zip -r ../$(ARCHNAME_TDS).zip tex doc source dvips + cd .. + rm -rf tds + +ctan : dist arch-tds + tar cf $(PACKAGE).tar $(ARCHNAME_TDS).zip $(ARCHNAME).tar.gz + +clean : + $(RM) $(foreach prefix, $(PACKAGE) $(PACKAGE)-DE, \ + $(addprefix $(prefix), .dvi .ps .log .aux .bbl .blg .out .tmp \ + .toc .hd)) + +veryclean : clean + $(RM) $(addprefix $(PACKAGE), .pdf .tex .sty .pro) $(PACKAGE)-DE.pdf Changes diff --git a/Master/texmf-dist/source/latex/pst-intersect/pst-intersect.dtx b/Master/texmf-dist/source/latex/pst-intersect/pst-intersect.dtx new file mode 100644 index 00000000000..7bc9b753edb --- /dev/null +++ b/Master/texmf-dist/source/latex/pst-intersect/pst-intersect.dtx @@ -0,0 +1,3094 @@ +% \iffalse meta-comment +% +% Copyright (C) 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. +% \fi +% +% \iffalse +%<*driver> +\ProvidesFile{pst-intersect.dtx} +%</driver> +%<stylefile>\NeedsTeXFormat{LaTeX2e}[1999/12/01] +%<stylefile>\ProvidesPackage{pst-intersect} +%<*stylefile> + [2014/02/19 v0.1 package wrapper for pst-intersect.tex] +%</stylefile> +% +%<*driver> +\documentclass[a4paper, DIV=9, oneside, toc=index, parskip=half-]{scrreprt} +\usepackage{doc} +\setcounter{IndexColumns}{2} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{lmodern} +\usepackage{amsmath, marvosym} +\usepackage{bera} +\providecommand*\mainlang{} +\usepackage[ngerman, english,\mainlang]{babel} +\usepackage{prettyref} +\usepackage[dvipsnames,x11names,svgnames]{xcolor} +\usepackage{array,booktabs,paralist,tabularx} +\usepackage{ragged2e, calc} +\newlength{\PITcaptionmargin} +\newlength{\PITcaptionheight} +\usepackage[labelfont={color=DOrange}, + singlelinecheck=false, + justification=raggedright]{caption} +\DeclareCaptionFormat{pitnocaption}{% + \setlength{\PITcaptionmargin}{\widthof{#1}+7pt}% + \setlength{\PITcaptionheight}{\heightof{#1}+3pt}% + \hspace*{-\PITcaptionmargin}#1\par\vspace*{-\PITcaptionheight}% +}% +\DeclareCaptionFormat{pitcaption}{% + \setlength{\PITcaptionmargin}{\widthof{#1}+7pt}% + \hspace*{-\PITcaptionmargin}#1#2#3\par +}% +\captionsetup[lstlisting]{format=pitnocaption} +\usepackage{nicefrac, multido} +\usepackage{pst-intersect} +\usepackage{hypdoc} +\hypersetup{% + colorlinks=true, + urlcolor=DOrange, + linkcolor=pdflinkcolor, + breaklinks, + linktocpage=true} +\usepackage{breakurl} +\definecolor{DOrange}{rgb}{1,.4,.2}% +\definecolor{DDOrange}{rgb}{0.7, 0.23, 0.07}% +\colorlet{pdflinkcolor}{DOrange} +\colorlet{DGreen}{green!90!black} +\usepackage{showexpl} +\makeatletter\renewcommand*\SX@Info{}\makeatother +\usepackage{etoolbox} +\undef{\cs}\undef{\cmd} +\usepackage{ltxdockit} +\newcommand{\poeTR}[1]{\TR{\ttfamily\color{DOrange}#1}} +\definecolor{colKeys}{rgb}{0,0,0} +\definecolor{colIdentifier}{rgb}{0,0,0} +\colorlet{colComments}{green!60!black} +\definecolor{colString}{rgb}{0,0.5,0} +\newlength{\codeoverhang} +\setlength{\codeoverhang}{0.5\marginparwidth+\marginparsep} +\lstset{% + language=[LaTeX]TeX, identifierstyle=\color{colIdentifier}, + keywordstyle=\color{colKeys}, + keywordstyle = [21]\color{DOrange}, + keywordstyle = [22]\color{DOrange}, + stringstyle=\color{colString}, + commentstyle=\color{colComments}, + alsoletter={12}, + float=hbp, + basicstyle=\ttfamily\small, + columns=flexible, + tabsize=4, + showspaces=false, + showstringspaces=false, + breaklines=true, + breakautoindent=true, + breakatwhitespace=true, + captionpos=t, + belowcaptionskip=0pt, + abovecaptionskip=0pt, + xleftmargin=1em, + prebreak = {\raisebox{-0.5ex}[\ht\strutbox]{\kern0.5ex\large\Righttorque}}, + rulecolor=\color{black!20}, + texcsstyle = [20]\color{DDOrange}, + moretexcs = [20]{pssavebezier, pssavepath, pstracecurve, psintersect}, + explpreset={% + pos=l, width=-99pt, hsep=5mm, overhang=\codeoverhang, varwidth, + vsep=\bigskipamount, rframe={}}, extendedchars=true +}% +\lstdefinestyle{example}{explpreset={% + escapechar=*, pos=l, width=-99pt, hsep=5mm, overhang=\codeoverhang, + varwidth, vsep=\bigskipamount, rframe={}}} +\makeatletter +\providecommand\ON{% + \gdef\lst@alloverstyle##1{\textcolor{black!50}{\strut##1}% +}} +\providecommand\OFF{\xdef\lst@alloverstyle##1{##1}} +\makeatother +\colorlet{sectioncolor}{DOrange} +\addtokomafont{sectioning}{\color{sectioncolor}} +\usepackage[automark,nouppercase]{scrpage2} +\pagestyle{scrheadings} +\clearscrheadings +\clearscrplain +\ohead{\pagemark} +\ihead{\headmark} +\ofoot[\pagemark]{} +\automark[subsection]{section} +\setheadsepline{.4pt}[\color{DOrange}] +\setheadwidth[0pt]{text} +\setfootwidth[0pt]{text} +\makeatletter +\patchcmd{\l@chapter}{1.5em}{2em}{}{} +\renewcommand*\l@section{\bprot@dottedtocline{1}{1.5em}{3.0em}} +\renewcommand*\l@subsection{\bprot@dottedtocline{2}{3.8em}{4.0em}} +\newrobustcmd*{\fnurl}[1][]{\hyper@normalise\ltd@fnurl{#1}} +\def\ltd@fnurl#1#2{\footnote{#1\hyper@linkurl{\Hurl{#2}}{#2}}} +\newrobustcmd*{\arxivurl}[1]{\href{http://arxiv.org/abs/#1}{arXiv:#1}} +\newrobustcmd*{\doiurl}[1]{\href{http://dx.doi.org/#1}{DOI:#1}} +\makeatother +\usepackage{csquotes} +\MakeAutoQuote{«}{»} +%^^A spot is used in ltxdockit.sty +\colorlet{spot}{sectioncolor} +%^^A Fonts definitions used in ltxdockit.sty +\renewcommand*{\verbatimfont}{\ttfamily} +\renewcommand*{\displayverbfont}{\ttfamily} +\renewcommand*{\marglistfont}{\spotcolor\sffamily\small} +\renewcommand*{\margnotefont}{\sffamily\small} +\renewcommand*{\optionlistfont}{\spotcolor\sffamily\displayverbfont} +\renewcommand*{\ltxsyntaxfont}{\ttfamily} +\renewcommand*{\ltxsyntaxlabelfont}{\spotcolor\displayverbfont} +\renewcommand*{\changelogfont}{\normalfont} +\renewcommand*{\changeloglabelfont}{\spotcolor\sffamily\bfseries} + +\makeatletter +\renewenvironment*{ltxsyntax} + {\list{}{% + \setlength{\labelwidth}{\marglistwidth}% + \setlength{\labelsep}{0pt}% + \setlength{\leftmargin}{0pt}% + \renewcommand*{\makelabel}[1]{% + \hss\ltxsyntaxfont\ltxsyntaxlabelfont##1}}% + \let\cmditem\PIT@cmditem} + {\endlist} + +\def\ltd@optionlist{% + \let\optitem\PIT@optitem + \let\valitem\PIT@valitem + \let\choitem\PIT@choitem + \let\boolitem\PIT@boolitem + \let\intitem\PIT@intitem + \let\numitem\PIT@numitem + \let\psnumitem\PIT@psnumitem + \let\pititem\ltd@item + \let\typeitem\PIT@typeitem} + +\def\PIT@typeitem#1#2{% + \item[{#1}]% + \label{prm:#1}% + \begingroup\raggedright + #2% + \settowidth\@tempdimb{\prm{psstyle}}% + \settowidth\@tempdimc{#1}% + \@tempdimc=\dimexpr\@tempdimc+\labelsep-\labelwidth\relax + \ifdim\@tempdimc>0pt% + \@tempdima=\dimexpr\linewidth-\@tempdimb-\@tempdimc-1em\relax + \else + \@tempdima=\dimexpr\linewidth-\@tempdimb-1em\relax + \fi + \par\endgroup} + +\def\PIT@option#1#2#3{% + \item[#1]% + \begingroup\raggedright + \ltd@textverb{=}% + \settowidth\@tempdimb{\ltd@textverb{=}}% + \settowidth\@tempdimc{#1}% + \@tempdimc=\dimexpr\labelwidth-\@tempdimc\relax + \ifdim\@tempdimc<0pt + \@tempdima=\dimexpr\linewidth-\@tempdimb+\@tempdimc-2em\relax + \else + \@tempdima=\dimexpr\linewidth-\@tempdimb-2em\relax + \fi + \ifblank{#3} + {} + {\settowidth\@tempdimb{default: #3}% + \@tempdima=\dimexpr\@tempdima-\@tempdimb-2em\relax}% + \parbox[t]{\@tempdima}{\raggedright #2}% + \ifblank{#3} + {} + {\hfill default:~#3}% + \par\endgroup + \nobreak\vspace{\itemsep}} + +\def\PIT@optitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@optitem@i} + {\booltrue{@tempswa}\PIT@optitem@i}} +\newcommand*{\PIT@optitem@i}[3][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{#3}{}} + {\PIT@option{#2}{#3}{\ltd@textverb{#1}}}}% + +\def\PIT@valitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@valitem@i} + {\booltrue{@tempswa}\PIT@valitem@i}} +\newcommand*{\PIT@valitem@i}[3][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{\prm{#3}}{}} + {\PIT@option{#2}{\prm{#3}}{\ltd@textverb{#1}}}}% + +\def\PIT@choitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@choitem@i} + {\booltrue{@tempswa}\PIT@choitem@i}} +\newcommand*{\PIT@choitem@i}[3][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{\ltd@verblist{#3}}{}} + {\PIT@option{#2}{\ltd@verblist{#3}}{\ltd@textverb{#1}}}}% + +\def\PIT@boolitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@boolitem@i} + {\booltrue{@tempswa}\PIT@boolitem@i}} +\newcommand*{\PIT@boolitem@i}[2][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{\ltd@verblist{true,false}}{}} + {\PIT@option{#2}{\ltd@verblist{true,false}}{\ltd@textverb{#1}}}}% + +\def\PIT@intitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@intitem@i} + {\booltrue{@tempswa}\PIT@intitem@i}} +\newcommand*{\PIT@intitem@i}[2][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{\prm{int}}{}} + {\PIT@option{#2}{\prm{int}}{\ltd@textverb{#1}}}}% + +\def\PIT@numitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@numitem@i} + {\booltrue{@tempswa}\PIT@numitem@i}} +\newcommand*{\PIT@numitem@i}[2][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{\prm{num}}{}} + {\PIT@option{#2}{\prm{num}}{\ltd@textverb{#1}}}}% + +\def\PIT@psnumitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@psnumitem@i} + {\booltrue{@tempswa}\PIT@psnumitem@i}} +\newcommand*{\PIT@psnumitem@i}[2][]{% + \ifbool{@tempswa}% + {\label{prm:#2}\xdefLkeyword{#2}}% + {\xLkeyword{#2}}% + \ifblank{#1} + {\PIT@option{#2}{\prm{psnum}}{}} + {\PIT@option{#2}{\prm{psnum}}{\ltd@textverb{#1}}}}% + +\def\ltd@csitem{% + \@ifstar + {\boolfalse{@tempswa}\ltd@csitem@i} + {\booltrue{@tempswa}\ltd@csitem@i}} +\def\ltd@csitem@i#1{% + \ifbool{@tempswa} + {\ltd@item@ii{\textbackslash#1\hspace\marglistsep}{#1}} + {\ltd@item@ii{\textbackslash#1\hspace\marglistsep}{}}} + +\def\PIT@cmditem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@cmditem@i} + {\booltrue{@tempswa}\PIT@cmditem@i}} +\def\PIT@cmditem@i#1{% + \ifbool{@tempswa} + {\PIT@cmditem@ii{\textbackslash#1}{cs:#1}} + {\PIT@cmditem@ii{\textbackslash#1}{}}} +\def\PIT@compitem{% + \@ifstar + {\boolfalse{@tempswa}\PIT@compitem@i} + {\booltrue{@tempswa}\PIT@compitem@i}} +\def\PIT@compitem@i#1{% + \ifbool{@tempswa} + {\PIT@cmditem@ii{\textbackslash#1}{comp:#1}} + {\PIT@cmditem@ii{\textbackslash#1}{}}} +\def\PIT@cmditem@ii#1#2{% + \ltd@itemsave + \ifhmode + \itemsep-\topsep + \else + \ltd@itembreak + \fi + \item[#1]% + \ltd@itemrest + \ifblank{#2}{}{\label{#2}}% + \begingroup + \ltd@syntaxsetup + \ltxsyntaxfont + \let\@tempa\@empty + \ltd@parseargs} + +\def\ltd@csitem@ii#1#2{% + \ltd@itemsave + \ifhmode + \itemsep-\topsep + \else + \ltd@itembreak + \fi + \item[#1]% + \ltd@itemrest + \ifblank{#2}{}{\label{cs:#2}}% + \begingroup + \ltd@syntaxsetup + \ltxsyntaxfont + \let\@tempa\@empty + \ltd@parseargs} + + +\let\plainllap\llap +\newrobustcmd\macro@llap[1]{{\global\let\llap\plainllap + \setbox0=\hbox\bgroup \macro@font\small\saved@macroname\egroup + \ifdim\wd0>30mm + \hbox to\z@ \bgroup\hss \hbox to30mm{\unhcopy0\hss}\egroup + \edef\@tempa{\hskip\dimexpr\the\wd0-30mm}\global\everypar\expandafter{\the\expandafter\everypar + \@tempa \global\everypar{}}% + \else \llap{\unhbox0}\fi}} + \AtBeginEnvironment{macro}{\let\llap\macro@llap} +\makeatother + +\newcommand*{\PSstring}[1]{{\normalfont\small\ttfamily(#1)}} +\newcommand*{\PSarray}[1]{{\normalfont\small\ttfamily[#1]}} +\newcommand*{\PSname}[1]{{\normalfont\small\ttfamily/#1}} +\newcommand*{\PSproc}[1]{{\normalfont\small\ttfamily\textbraceleft #1\textbraceright}} +\newcommand*{\PSvar}[1]{{\normalfont\small\ttfamily #1}} +\newcommand*{\PSop}[1]{{\normalfont\small\ttfamily\color{DOrange}\hskip 3pt #1\hskip 3pt}} + +\newcommand*{\compref}[1]{\ref{comp:#1}} +\newcommand*{\hyperpagedef}[1]{\textbf{\hyperpage{#1}}} +\newcommand*{\nodename}[1]{\emph{#1}} +\newcommand*{\param}[1]{\normalfont\texttt{#1}} +\newcommand*{\paramvalue}[1]{\texttt{#1}} +\newcommand*{\styleshape}[1]{\texttt{#1}} +\newcommand{\docindex}[1]{\sindex[doc]{#1|hyperpage}} +\newcommand{\docindexdef}[1]{\sindex[doc]{#1|hyperpagedef}} +\makeatletter +\def\Lcs{\@ifstar{\Lcs@nobm}{\Lcs@bm}} +\def\Lcs@nobm#1{\nxLcs{#1}\xLcs{#1}} +\def\Lcs@bm#1{\hyperref[cs:#1]{\Lcs@nobm{#1}}} +\def\xLcs#1{} +\def\nxLcs#1{\texttt{\textbackslash#1}} + +\def\Lcomp{\@ifstar{\Lcomp@nobm}{\Lcomp@bm}} +\def\Lcomp@nobm#1{\nxLcomp{#1}\xLcomp{#1}} +\def\Lcomp@bm#1{\hyperref[comp:#1]{\Lcomp@nobm{#1}}} +\def\xLcomp#1{} +\def\nxLcomp#1{\texttt{\textbackslash#1}} + +\def\LPack#1{\nxLPack{#1}} +\def\nxLPack#1{\texttt{#1}} + +\def\Lenv{\@ifstar{\Lenv@nobm}{\Lenv@bm}} +\def\Lenv@nobm#1{\nxLenv{#1}\xLenv{#1}} +\def\Lenv@bm#1{\hyperref[env:#1]{\Lenv@nobm{#1}}} +\def\xLenv#1{} +\def\nxLenv#1{\texttt{#1}} +\let\orig@ltd@envitem\ltd@envitem +\def\ltd@envitem#1{\orig@ltd@envitem{#1}\label{env:#1}\xLenv{#1}} + +\def\Lkeyword{\@ifstar{\Lkeyword@nobm}{\Lkeyword@bm}} +\def\Lkeyword@nobm#1{\nxLkeyword{#1}\xLkeyword{#1}} +\def\Lkeyword@bm#1{\hyperref[prm:#1]{\Lkeyword@nobm{#1}}} +\def\xLkeyword#1{} +\def\xdefLkeyword#1{} +\def\nxLkeyword#1{\texttt{#1}} + +\def\xLoption#1{} +\def\Loption#1{\texttt{#1}\xLoption{#1}} +\def\nxLoption#1{\texttt{#1}} + +\def\Lstyle{\@ifstar{\Lstyle@nobm}{\Lstyle@bm}} +\def\Lstyle@nobm#1{\nxLstyle{#1}\xLstyle{#1}} +\def\Lstyle@bm#1{\hyperref[sty:#1]{\Lstyle@nobm{#1}}} +\def\xLstyle#1{} +\def\xdefLstyle#1{} +\def\nxLstyle#1{\texttt{#1}} + +\makeatother + +\newcommand{\dipoledesc}[1]{% + \xLdipole{#1}% + \compitem{#1}[options](in)(out){label}% +} +\newcommand{\tripoledesc}[1]{% + \xLtripole{#1}% + \compitem{#1}[options](in)(center)(out){label}% +} + +\newcommand{\fiberdipoledesc}[1]{% + \xLfdipole{#1}% + \compitem{#1}[options](in)(out){label}% +} + +\newenvironment*{pssyntax} + {\list{}{\small + \setlength{\labelsep}{0pt}% + \setlength{\leftmargin}{10pt}% + \item[]}} + {\endlist} + +\newcommand{\psarglistfont}{\small} +\newenvironment*{psarglist} + {\list{}{% + \setlength{\labelwidth}{10pt}% + \setlength{\labelsep}{0pt}% + \setlength{\leftmargin}{0pt}% + \setlength{\itemsep}{\parsep}% + \setlength{\parsep}{0pt}% + \renewcommand*{\makelabel}[1]{\hss\psarglistfont##1}}} + {\endlist} + +\makeatletter +\renewenvironment{theglossary}{\GlossaryParms \let\item\@idxitem \ignorespaces}{} +\makeatother +\def\psargitem#1{\item[#1]\hfill\par\nobreak} + +\addtopsstyle{Fiber}{linecolor=DOrange,linewidth=1.5\pslinewidth} +\addtopsstyle{Beam}{linewidth=1.5\pslinewidth} +\EnableCrossrefs +\CodelineIndex +\OnlyDescription +\begin{document} + \DocInput{pst-intersect.dtx} +\end{document} +%</driver> +% \fi +% +% \CheckSum{0} +% +% \CharacterTable +% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z +% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z +% Digits \0\1\2\3\4\5\6\7\8\9 +% Exclamation \! Double quote \" Hash (number) \# +% Dollar \$ Percent \% Ampersand \& +% Acute accent \' Left paren \( Right paren \) +% Asterisk \* Plus \+ Comma \, +% Minus \- Point \. Solidus \/ +% Colon \: Semicolon \; Less than \< +% Equals \= Greater than \> Question mark \? +% Commercial at \@ Left bracket \[ Backslash \\ +% Right bracket \] Circumflex \^ Underscore \_ +% Grave accent \` Left brace \{ Vertical bar \| +% Right brace \} Tilde \~} +% +% \GetFileInfo{pst-intersect.dtx} +% +% \newif\ifGERMAN \GERMANfalse +% \newif\ifENGLISH \ENGLISHfalse +% \iflanguage{ngerman}{\GERMANtrue}{% +% \iflanguage{german}{\GERMANtrue}{\GERMANfalse}} +% \iflanguage{english}{\ENGLISHtrue}{\ENGLISHfalse} +% +% \ifGERMAN +% \newrefformat{chap}{Kap.~\ref{#1}} +% \newrefformat{sec}{Kap.~\ref{#1}} +% \newrefformat{l}{Zeile~\ref{#1}} +% \newrefformat{ex}{Bsp.~\ref{#1}} +% \newrefformat{tab}{Tab.~\ref{#1}} +% \newrefformat{fig}{Abb.~\ref{#1}} +% \newcommand{\PITindexMacro}{Makros} +% \newcommand{\PITindexKeyword}{Parameter} +% \newcommand{\PITindexEnv}{Umgebungen} +% \newcommand{\PITindexPack}{Pakete} +% \renewcommand*\lstlistingname{Bsp.} +% \fi +% \ifENGLISH +% \newrefformat{chap}{Sec.~\ref{#1}} +% \newrefformat{sec}{Sec.~\ref{#1}} +% \newrefformat{l}{Line~\ref{#1}} +% \newrefformat{ex}{Ex.~\ref{#1}} +% \newrefformat{tab}{Tab.~\ref{#1}} +% \newrefformat{fig}{Fig.~\ref{#1}} +% \newcommand{\PITindexMacro}{macros} +% \newcommand{\PITindexKeyword}{parameters} +% \newcommand{\PITindexEnv}{environments} +% \newcommand{\PITindexPack}{packages} +% \renewcommand*\lstlistingname{Ex.} +% \fi +% +% \makeatletter +% \renewcommand\maketitle{^^A +% \thispagestyle{empty}^^A +% \begin{titlepage} +% \begin{pspicture}(1.6in,0.685in)(10,21.7) +% \psframe[fillstyle=solid,linecolor=lightgray,fillcolor=lightgray,linestyle=solid](0,-5.75)(21.5,10) +% \psframe[fillstyle=solid,linecolor=Orange!85!Red,fillcolor=Orange!85!Red,linestyle=solid](0,10)(21.5,10.5) +% \psframe[fillstyle=solid,linecolor=Orange!85!Red,fillcolor=Orange!85!Red,linestyle=solid](0,21.1)(21.5,21.2) +% \rput[lb](3,22){\Huge\sffamily\color{Orange!65!Red}\psscalebox{2}{\textbf{PSTricks}}} +% \rput[lb](3,14.1){\parbox{15cm}{\sffamily\RaggedRight\bfseries\huge\@title}} +% \rput[lb](3,7.6){\parbox{13cm}{\sffamily\@date}} +% \rput[lb](3,-2.6){\parbox[b]{17cm}{\sffamily\RaggedRight +% ~\hfill\makebox[7cm][l]{\ifGERMAN Paketautor:\fi\ifENGLISH Package author:\fi}\\ +% ~\hfill\makebox[7cm][l]{^^A +% \bfseries\tabular[t]{@{}l@{}}\@author\endtabular}}} +% \rput[C](11,4){\bgImage} +% \end{pspicture}^^A +% \end{titlepage}} +% \makeatother +% +% \ifGERMAN +% \title{\texttt{pst-intersect}\\ Berechnen der Schnittpunkte beliebiger Kurven\\[0.5ex] \small \fileversion} +% \hypersetup{pdftitle={Berechnen der Schnittpunkte beliebiger Kurven}} +% \fi +% \ifENGLISH +% \title{\texttt{pst-optexp}\\ Intersecting arbitrary curves\\[0.5ex] \small \fileversion} +% \hypersetup{pdftitle={Intersecting arbitrary curves}} +% \fi +% \author{Christoph Bersch} +% \date{\filedate} +% \def\bgImage{} +% +% \maketitle +% +% \clearpage +% \tableofcontents +% \clearpage +% +% \ifGERMAN +% \chapter{Einführung} +% \fi +% \ifENGLISH +% \chapter{Introduction} +% \fi +% +% \ifGERMAN +% \section{Über das Paket} +% +% \LPack{pst-intersect} ist ein PSTricks-Paket zur +% Berechnung der Schnittpunkte von Bézier-Kurven und beliebigen +% Postscript-Pfaden. +% \fi +% \ifENGLISH +% \section{About the package} +% \LPack{pst-intersect} is a PSTricks package to calculate +% the intersections of Bezier curves and arbitrary Postscript paths. +% \fi +% +% \ifGERMAN +% \section{Anforderungen} +% \LPack{pst-intersect} benötigt aktuelle Versionen der +% Pakete \LPack{pstricks}, \LPack{pst-node} und \LPack{pst-func}. +% +% Alle PSTricks-Pakete machen regen Gebrauch von der Postscript-Sprache, so +% dass der typische Arbeitsfluss \opt{latex}, \opt{dvips} und +% ggf. \opt{ps2pdf} umfasst. Es gibt viele alternative Methoden um die +% Dokumente zu +% kompilieren.\fnurl{http://tug.org/PSTricks/main.cgi?file=pdf/pdfoutput} +% \fi +% \ifENGLISH +% \section{Requirements} +% \LPack{pst-intersect} requires recent versions of +% \LPack{pstricks}, \LPack{pst-node}, and \LPack{pst-func}. +% +% All PSTricks package rely heavily on the Postscript language so that the +% typical workflow involves \opt{latex}, \opt{dvips}, and \opt{ps2pdf}. Of +% course there are several alternative ways to compile your +% documents.\fnurl{http://tug.org/PSTricks/main.cgi?file=pdf/pdfoutput} +% \fi +% +% \ifGERMAN +% \section{Verbreitung und Installation} +% Dieses Paket ist auf +% CTAN\fnurl{http://mirror.ctan.org/help/Catalogue/entries/pst-intersect.html} +% erhältlich. +% +% Das \LPack{pst-intersect}-Paket umfasst die zwei Hauptdateien +% \texttt{pst-intersect.ins} und \texttt{pst-intersect.dtx}. Durch Aufrufen +% von \texttt{tex pst-intersect.ins} werden die drei folgenden +% Dateien erzeugt: +% \begin{itemize} +% \item \texttt{pst-intersect.pro}: die Postscript Prologdatei +% \item \texttt{pst-intersect.sty}: die \LaTeX-Stildatei +% \item \texttt{pst-intersect.tex}: die \TeX-Datei +% \end{itemize} +% Speichern Sie diese Dateien in einem Verzeichnis der Teil Ihres +% lokalen \TeX-Baums ist. +% +% Vergessen Sie nicht \texttt{texhash} aufzurufen um den Baum zu +% aktualisieren. MiK\TeX{}-Benutzer müssen die Dateinamen-Datenbank +% (FNDB) aktualisieren. +% +% Detailliertere Information finden Sie in der Dokumentation Ihrer +% \LaTeX-Distribution über die Installation in den lokalen +% \TeX{}-Baum. +% \fi +% \ifENGLISH +% \section{Distribution and installation} +% This package is available on +% CTAN\fnurl{http://mirror.ctan.org/help/Catalogue/entries/pst-intersect.html}. +% +% The \LPack{pst-intersect} package consists of the two main files +% \texttt{pst-intersect.ins} and \texttt{pst-intersect.dtx}. By running \texttt{tex +% pst-intersect.ins} the following derived files are generated: +% \begin{itemize} +% \item \texttt{pst-intersect.pro}: the Postscript prolog file +% \item \texttt{pst-intersect.sty}: the \LaTeX{} style file +% \item \texttt{pst-intersect.tex}: the \TeX{} file +% \end{itemize} +% Save the files in a directory which is part of your local \TeX{} tree. +% +% Do not forget to run \texttt{texhash} to update this tree. For MiK\TeX{} +% users, do not forget to update the file name database (FNDB). +% +% For more detailed information see the documentation of your personal +% \LaTeX{} distribution on installing packages to your local \TeX{} +% system. +% \fi +% +% \ifGERMAN\section{Lizenz}\fi +% \ifENGLISH\section{License}\fi +% \ifGERMAN +% Es wird die Erlaubnis gewährt, dieses Dokument zu kopieren, zu verteilen +% und\slash oder zu modifizieren, unter den Bestimmungen der \LaTeX{} Project +% Public License, Version +% 1.3c.\fnurl{http://www.latex-project.org/lppl.txt}. Dieses +% Paket wird vom Autor betreut (author-maintained). +% \fi +% \ifENGLISH +% Permission is granted +% to copy, distribute and\slash or modify this software under the terms of the +% \LaTeX{} Project Public License, version +% 1.3c.\fnurl{http://www.latex-project.org/lppl.txt} This +% package is author-maintained. +% \fi +% +% \ifGERMAN +% \section{Danksagung} +% \fi +% \ifENGLISH +% \section{Acknowledgements} +% \fi +% \ifGERMAN +% Ich danke Marco Cecchetti, dessen +% \opt{lib2geom}-Bibliothek\fnurl{http://lib2geom.sourceforge.net/} +% mir als Vorlage für einen Großteil des Postscript-Kodes für den +% Bézier-Clipping-Algorithmus diente. Außerdem gilt mein Dank William +% A. Casselman, für seine Erlaubnis, den Quicksort-Kode und den Kode zur +% Berechung der konvexen Hüllen aus seinem Buch «Mathematical +% Illustration» verwenden zu +% dürfen\fnurl{http://www.math.ubc.ca/~cass/graphics/text/www/}. Der +% Dokumentationsstil ist eine Mischung aus der \opt{pst-doc} Klasse +% (Herbert Voß) und dem \opt{ltxdockit} Paket für die \opt{biblatex} +% Dokumentation (Philipp Lehmann). +% \fi +% \ifENGLISH +% I thank Marco Cecchetti, for his +% \opt{lib2geom}-library\fnurl{http://lib2geom.sourceforge.net/} from +% which I derived great parts of the Postscript code for the Bézier +% clipping algorithm. Also I want to thank William A. Casselman for the +% Postscript code of the quicksort procedure and the procedure for +% calculating the convex hull from his book «Mathematical +% Illustration»\fnurl{http://www.math.ubc.ca/~cass/graphics/text/www/}, +% and the permission to use it. The documentation style is a mixture of +% the \opt{pst-doc} class (Herbert Voß) and the \opt{ltxdockit} package +% for the \opt{biblatex} documentation (Philipp Lehman). +% \fi +% +% +% \ifGERMAN +% \chapter{Benutzung} +% \fi +% \ifENGLISH +% \chapter{Usage} +% \fi +% +% \ifGERMAN +% Das \LPack{pst-intersect}-Paket kann Schnittpunkte von beliebigen +% Postscript-Pfaden berechnen. Diese setzen sich nur aus drei primitiven +% Operation zusammen: Linien (\opt{lineto}), Bézier-Kurven dritter +% Ordnung (\opt{curveto}) und Sprüngen (\opt{moveto}). Speziellere +% Konstruktionen, wie z.B. Kreise werden intern zu +% \opt{curveto}-Anweisungen umgewandelt. Über diese Kommandos hinaus +% kann \LPack{pst-intersect} auch Bézier-Kurven bis neunter Ordnung +% verwenden. Das diese keine primitiven Postscript-Pfadelemente +% darstellen, müssen sie gesondert behandelt werden. +% +% Der allgemeine Arbeitsablauf besteht darin eine oder mehrere Kurven +% oder Pfade zu speichern, und danach die Schnittpunkte zu +% berechnen. Anschließend können die Schnittpunkte als normale +% PSTricks-Knoten verwendet werden, oder Abschnitte der Kurven und Pfade +% nachgezogen werden (z.B. zwischen zwei Schnittpunkten). +% \fi +% \ifENGLISH +% The \LPack{pst-intersect} package can compute the intersections of +% arbitrary Postscript paths. These are composed of three primitive +% operations: lines (\opt{lineto}), third order Bézier curves +% (\opt{curveto}) and jumps (\opt{moveto}). More specialized +% constructions, like circles, are converted internally to \opt{curveto} +% operations. Besides these three path operations, the +% \LPack{pst-intersect} supports Bézier curves up to nineth order. As +% these aren't primitive Postscript path elements, they require separate +% handling. +% +% The general workflow consists in defining and saving paths and curves, +% and then compute the intersections between them. Following, those +% intersection points can be used as normal PSTricks nodes, or portions +% of the curves and paths can be retraced (e.g. between two +% intersections). +% \fi +% +% \ifGERMAN +% \section{Speichern von Pfaden und Kurven} +% \fi +% \ifENGLISH +% \section{Saving paths and curves} +% \fi +% +% \ifGERMAN +% +% \fi +% +% \begin{ltxsyntax} +% \cmditem{pssavepath}[options]{curvename}{commands} +% +% \ifGERMAN +% Speichert den gesamten Pfad, der durch \prm{commands} erstellt wird, +% unter Verwendung des Namens \prm{curvename}. Das Makro funktioniert +% genauso wie \cs{pscustom}, und kann daher auch nur die darin +% erlaubten Kommandos verarbeiten. +% +% In den Standardeinstellungen wird der entsprechende Pfad auch gleich +% gezeichnet, was mit \prm{options} beeinflusst werden kann. Mit +% \opt{linestyle=none} wird das unterbunden. +% \fi +% \ifENGLISH +% Saves the complete path, which is generated by \prm{commands}, under +% the name \prm{curvename}. The macro is a modification of +% \cs{pscustom}, and does, therefore, supports only the same commands. +% +% By default, the path is also drawn, which can be changed over the +% \prm{options}, e.g. with \opt{linestyle=none}. +% \fi +% \end{ltxsyntax} +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(3,2) + \pssavepath[linecolor=DOrange]{MyPath}{% + \pscurve(0,2)(0,0.5)(3,1) + }% +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \begin{ltxsyntax} +% \cmditem{pssavebezier}[options]{curvename}($X_0$)\ldots(\prm{$X_n$}) +% +% \ifGERMAN +% Die Postscript-Sprache unterstützt nur Bézier-Kurven dritter +% Ordnung. Mit dem Makro \Lcs{pssavebezier} können Bézier-Kurven +% bis neunter Ordnung definiert werden. Die angegebenen Knoten sind die +% Kontrollpunkte der Kurve, für eine Kurve $n$-ter Ordnung werden +% $(n+1)$ Kontrollpunkte benötigt. Die Darstellung der Kurve erfolgt +% mit dem Makro \cs{psBezier} aus dem \LPack{pst-func}-Paket. +% \fi +% \ifENGLISH +% The Postscript language supports only third-order Bézier +% curves. With the macro \Lcs{pssavebezier} you can define Bézier +% curves up to nineth order. The specified nodes are the control +% points of the curve, for an $n$-th order curve $n+1$ control points +% are required. The drawing of the curve is done with the +% \cs{psBezier} macro from the \LPack{pst-func} package. +% \fi +% \end{ltxsyntax} +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(3,2) + \pssavebezier[showpoints]{MyBez}(0,0)(0,1)(1,2)(3,2)(1,0)(3,0) +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \ifGERMAN +% \section{Schnittpunkte berechnen} +% \fi +% \ifENGLISH +% \section{Calculating intersections} +% \fi +% +% \begin{ltxsyntax} +% \cmditem{psintersect}{curveA}{curveB} +% +% \ifGERMAN +% Nachdem Sie nun Pfade oder Kurven gespeichert haben, können Sie +% deren Schnittpunkte berechnen. Das geschieht mit dem Makro +% \Lcs{psintersect}. Dieses benötigt als Argumente zwei Namen von +% Pfaden oder Kurven (Das Argument \prm{curvename} der beiden +% \cs{pssave*} Makros). +% \fi +% \ifENGLISH +% After having saved some paths and curves, you can now calculate the +% intersections. That is done with the \Lcs{psintersect} macro. This +% needs as arguments two names of paths or curves (the \prm{curvename} +% argument of the two \cs{pssave*} macros). +% \fi +% \end{ltxsyntax} +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(3,2) + \pssavepath[linecolor=DOrange]{MyPath}{\pscurve(0,2)(0,0.5)(3,1)} + \pssavebezier{MyBez}(0,0)(0,1)(1,2)(3,2)(1,0)(3,0) + \psintersect[showpoints]{MyPath}{MyBez} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \ifGERMAN +% Der PSTricks-Parameter \opt{showpoints} steuert dabei, ob die +% Schnittpunkte angezeigt werden. +% \fi +% \ifENGLISH +% The \opt{showpoints} PSTricks parameter determines, if the +% intersections are drawn directly. +% \fi +% +% \begin{optionlist} +% \valitem[@tmp]{name}{string} +% \ifGERMAN +% Die berechneten Schnittpunkte können unter einem hier angegebenen +% Namen gespeichert und zu einem späteren Zeitpunkt verwendet werden +% (siehe \prettyref{sec:pstracecurve-int}). +% \fi +% \ifENGLISH +% The calculated intersections can be saved for later use under this +% name (see \prettyref{sec:pstracecurve-int}). +% \fi +% +% \boolitem[true]{saveintersections} +% \ifGERMAN +% Ist dieser Schalter gesetzt, dann werden die Schnittpunkte als +% PSTricks-Knoten unter den Namen \prm{name}1, \prm{name}2 \ldots +% gespeichert. Die Nummerierung erfolgt aufsteigend nach dem Wert der +% $x$-Koordinate. +% \fi +% \ifENGLISH +% If this option is set, the intersections are saved as PSTricks nodes +% with the names \prm{name}1, \prm{name}2 \ldots. The numbering is +% ascending according to the value of their $x$-coordinate. +% \fi +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(5,5) + \pssavebezier[linecolor=DOrange]{A}% + (0,0)(0,5)(5,5)(5,1)(1,1.5) + \pssavebezier{B}(0,5)(0,0)(5,0)(5,5)(0,2) + \psintersect[name=C, showpoints]{A}{B} + \uput[150](C1){1} + \uput[85](C2){2} + \uput[90](C3){3} + \uput[-20](C4){4} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% \end{optionlist} +% +% \ifGERMAN +% \section{Darstellung gespeicherter Pfade} +% \fi +% \ifENGLISH +% \section{Visualization of saved paths} +% \fi +% +% \begin{ltxsyntax} +% \cmditem{pstracecurve}[options]{curvename} +% +% \ifGERMAN +% Gespeicherte Pfade und Kurven können mit diesem Makro nachträglich +% gezeichnet werden. +% \fi +% \ifENGLISH +% Saved paths and curves can be drawn again with this macro. +% \fi +% \end{ltxsyntax} +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(2,2) + \pssavepath{Circle}{\pscircle(1,1){1}} + \pstracecurve[linestyle=dashed, linecolor=green]{Circle} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \begin{optionlist} +% \numitem{tstart} +% \numitem{tstop} +% +% \ifGERMAN Unter Verwendung dieser beiden Parameter können auch +% Abschnitte von Pfaden und Kurven gezeichnet werden. Bei Bézier-Kurven +% ist der Parameterbereich $[0, 1]$, wobei $0$ dem Anfang der Kurve, +% also dem ersten bei \Lcs{pssavebezier} angegebenen Knoten entspricht. +% \fi +% \ifENGLISH +% With these parameters also parts of paths and curves can be drawn. For +% Bézier curves the allowed range is $[0, 1]$, where $0$ corresponds to +% the start of the curve, which is given by the first node given to +% \Lcs{pssavebezier}. +% \fi +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(5,5) + \psset{showpoints} + \pssavebezier{B}(0,5)(0,0)(5,0)(5,5)(0,2) + \pstracecurve[linestyle=dashed, linecolor=blue!50, + tstart=0, tstop=0.5]{B} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \medskip +% \ifGERMAN +% Pfaden können aus mehr als einem Abschnitt bestehen, der Bereich ist +% also $[0, n]$, wobei $n$ die Anzahl der Pfadabschnitte ist. Dabei ist +% zu beachten, dass z.B. \cs{pscurve}-Pfade oder auch Kreise und +% Kreisbögen aus mehreren Abschnitten bestehen. +% \fi +% \ifENGLISH +% Paths can be composed of more than one segmet, and the range is $[0, +% n]$, where $n$ is the number of path segments. For this you must keep +% in mind, that also e.g \cs{pscurve} paths, circles or arcs consist of +% several segments. +% \fi +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(2,2) + \pssavepath[linestyle=none]{Circle}{\pscircle(1,1){1}} + \pstracecurve[tstart=0, tstop=1, linecolor=green]{Circle} + \pstracecurve[tstart=2, tstop=3, linecolor=red]{Circle} + \pstracecurve[tstart=1.25, tstop=1.75, linecolor=blue]{Circle} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \end{optionlist} +% +% \ifGERMAN +% Beachten Sie, dass in der Version 0.1 die Reihenfolge von +% \Lkeyword{tstart} und \Lkeyword{tstop} noch keine Rolle spielt. Für +% kommende Versionen ist geplant, dass bei \Lkeyword{tstart} +% \textgreater{} \Lkeyword{tstop} die Pfadrichtung umgekehrt wird. Zur +% Zeit werden auch noch keine Pfeile für \Lcs{pstracecurve} unterstützt. +% \fi +% \ifENGLISH +% Please note, that as of version 0.1 the order of \Lkeyword{tstart} and +% \Lkeyword{tstop} doesn't play a role. But for upcoming versions it is +% planned that \Lkeyword{tstart} \textgreater{} \Lkeyword{tstop} +% reverses the path direction. At the moment arrows aren't supported +% either. +% \fi +% +% \ifGERMAN +% \section{Darstellung gespeicherter Schnitte} +% \fi +% \ifENGLISH +% \section{Visualization of saved intersections} +% \fi +% \label{sec:pstracecurve-int} +% +% \begin{ltxsyntax} +% \cmditem*{pstracecurve}[options]{intersection}{curvename} +% \end{ltxsyntax} +% +% \begin{optionlist} +% \numitem{istart} +% \numitem{istop} +% +% \ifGERMAN +% Dieser beiden Parameter können auch verwendet werden um Abschnitte von +% Pfaden und Kurven zwischen Schnittpunkten zu zeichnen. Die +% Schnittpunkte werden dabei angefangen bei $1$ in aufsteigender +% Reihenfolge entlang der Kurve durchnummeriert. +% \fi +% \ifENGLISH +% These two parameters can be used to draw path or curve segments +% between intersections. The intersections are numbered starting at $1$ +% in ascending order along the curve. +% \fi +% \end{optionlist} +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(5.2,5.2) +\pssavebezier[linewidth=0.5\pslinewidth, linestyle=dashed, arrows=->]{A}(0,0)(0,5)(5,2)(5,5) +\pssavebezier[linewidth=0.5\pslinewidth, linestyle=dashed, arrows=->]{B}(0,2.5)(2.5,2.5)(4.5, 3)(2,4) +\psintersect[linecolor=green!70!black, name=C]{A}{B} +\pstracecurve[linecolor=red, istart=1, istop=2]{C}{A} +\pstracecurve[linecolor=blue, istart=1, istop=2]{C}{B} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \ifGERMAN +% Wird nur ein Wert angegeben, beispielsweise \Lkeyword{istop}, dann +% wird die Kurve vom Anfang bis zum entsprechenden Schnittpunkt +% gezeichnet. Wird nur \Lkeyword{istart} angegeben, dann endet die Kurve +% am Ende. Die Parameter \Lkeyword{istart} bzw. \Lkeyword{istop} können +% mit \Lkeyword{tstart} bzw. \Lkeyword{tstop} kombiniert werden. +% \fi +% \ifENGLISH +% If only one value is specified, e.g. \Lkeyword{istop}, the curve is +% drawn from the start to the respective intersection. If only +% \Lkeyword{istart} is given, the curve is drawn from this intersection +% to the curve end. The parameters \Lkeyword{istart} and +% \Lkeyword{istop} can be combined with \Lkeyword{tstart} and +% \Lkeyword{tstop}. +% \fi +% +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample} +\begin{pspicture}(5.2,5.2) +\pssavebezier[linewidth=0.5\pslinewidth, linestyle=dashed, arrows=->]{A}(0,0)(0,5)(5,2)(5,5) +\pssavebezier[linewidth=0.5\pslinewidth, linestyle=dashed, arrows=->]{B}(0,2.5)(2.5,2.5)(4.5, 3)(2,4) +\psintersect[linecolor=green!70!black, name=C]{A}{B} +\pstracecurve[linecolor=red, istop=2]{C}{A} +\pstracecurve[linecolor=blue, istart=1]{C}{B} +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +% \ifGERMAN +% \chapter{Beispiele} +% \fi +% \ifENGLISH +% \chapter{Examples} +% \fi +%\iffalse +%<*ignore> +%\fi +\begin{LTXexample}[caption={caption}] +\begin{pspicture}(5,5) + \pssavebezier{A}(0,0)(0,5)(5,5)(5,1)(1,1.5) + \multido{\i=100+-20,\r=1+-0.2}{5}{% + \pstracecurve[linecolor=red!\i, tstop=\r, arrows=-|, showpoints]{A} + }% +\end{pspicture} +\end{LTXexample} +%\iffalse +%</ignore> +%\fi +% +%\iffalse +%<*ignore> +%\fi +\begingroup +\captionsetup[lstlisting]{format=pitcaption} +\begin{LTXexample}[pos=t, caption={% +\ifGERMAN Mit diesem Paket können auch die Schnittpunkte von + Funktionen berechnet werden, die mit \cs{psplot} gezeichnet + werden. Dabei ist zu beachten, dass beide einzelnen Kurven aus + \opt{plotpoints} Abschnitten bestehen, von denen jeder mit jedem + geschnitten wird, was zu langen Berechnungen führen kann. + \fi + \ifENGLISH + The package can also calculate the intersections of functions which are + drawn with \cs{psplot}. Here you must keep in mind, that such curves + consists of \opt{plotpoints} segments, which must all be considered for + intersections, what can result in long calculations. + \fi}] +\begin{pspicture}(10,4.4) + \pssavepath{A}{\psplot[plotpoints=200]{0}{10}{x 180 mul sin 1 add 2 mul}} + \pssavepath{B}{\psplot[plotpoints=50]{0}{10}{2 x neg 0.5 mul exp 4 mul}} + \psintersect[name=C, showpoints]{A}{B} + \multido{\i=1+2,\ii=2+2}{5}{\uput[120](C\i){\i}\uput[60](C\ii){\ii}} +\end{pspicture} +\end{LTXexample} +\endgroup +%\iffalse +%</ignore> +%\fi +% +% \appendix +% +% \ifGERMAN +% \chapter{Versionsgeschichte} +% +% Diese Versionsgeschichte ist eine Liste von Änderungen, die für den Nutzer des +% Pakets von Bedeutung sind. Änderungen, die eher technischer Natur sind und für +% den Nutzer des Pakets nicht relevant sind und das Verhalten des Pakets nicht +% ändern, werden nicht aufgeführt. Wenn ein Eintrag der Versionsgeschichte ein +% Feature als \emph{improved} oder \emph{extended} bekannt gibt, so bedeutet +% dies, dass eine Modifikation die Syntax und das Verhalten des Pakets nicht +% beeinflusst, oder das es für ältere Versionen kompatibel ist. Einträge, die +% als \emph{deprecated}, \emph{modified}, \emph{renamed}, oder \emph{removed} +% deklariert sind, verlangen besondere Aufmerksamkeit. Diese bedeuten, dass eine +% Modifikation Änderungen in existierenden Dokumenten mit sich ziehen kann. +% \fi +% \ifENGLISH +% \chapter{Revision history} +% +% This revision history is a list of changes relevant to users of this +% package. Changes of a more technical nature which do not affect the +% user interface or the behavior of the package are not included in the +% list. If an entry in the revision history states that a feature has +% been \emph{improved} or \emph{extended}, this indicates a modification +% which either does not affect the syntax and behavior of the package or +% is syntactically backwards compatible (such as the addition of an +% optional argument to an existing command). Entries stating that a +% feature has been \emph{deprecated}, \emph{modified}, \emph{fixed}, +% \emph{renamed}, or \emph{removed} demand attention. They indicate a +% modification which may require changes to existing documents. +% \fi +% +% \begin{changelog} +%\patchcmd{\release}{\setlength{\itemsep}{0pt}}{\setlength{\itemsep}{0pt}\setlength{\parsep}{0pt}}{}{} +% \begin{release}{0.1}{2014-02-19} +% \item First CTAN version +% \end{release} +% \end{changelog} +% +% \StopEventually{} +% +% \begin{otherlanguage}{english} +% \printindex[idx] +% \end{otherlanguage} +% +% \chapter{The \LaTeX\ wrapper} +%<*stylefile> +% \begin{macrocode} +\NeedsTeXFormat{LaTeX2e}[1999/12/01] +\ProvidesPackage{pst-intersect}% + [2014/02/06 v0.1alpha package wrapper for pst-intersect.tex] +\RequirePackage{pstricks} +\RequirePackage{pst-xkey} +\RequirePackage{pst-node} +\RequirePackage{multido} +\RequirePackage{pst-func} +\input{pst-intersect.tex} +\IfFileExists{pst-intersect.pro}{% + \ProvidesFile{pst-intersect.pro} + [2014/02/06 PostScript prologue file] + \@addtofilelist{pst-intersect.pro}}{}% +% \end{macrocode} +%</stylefile> +% +% \chapter{The \TeX\ implementation} +% +%<*texfile> +% \begin{macrocode} +\csname PSTintersectLoaded\endcsname +\let\PSTintersectLoaded\endinput + +\ifx\PSTricksLoaded\endinput\else\input pstricks.tex \fi +\ifx\PSTXKeyLoaded\endinput\else \input pst-xkey.tex \fi +\ifx\PSTnodesLoaded\endinput\else\input pst-node.tex \fi +\ifx\PSTfuncLoaded\endinput\else \input pst-func.tex \fi + +\edef\PstAtCode{\the\catcode`\@} \catcode`\@=11\relax + +\pst@addfams{intersect} +\pstheader{pst-intersect.pro} + +\def\pst@intersectdict{tx@IntersectDict begin } +\def\PIT@dict#1{\pst@intersectdict #1 end} +\def\PIT@Verb#1{\pst@Verb{\PIT@dict{#1} }}% + +\def\pssavebezier{\pst@object{pssavebezier}} +\def\pssavebezier@i#1{% + \begin@OpenObj + \PIT@checkname{#1}% + \addto@pscode{ /\PIT@name{#1} }% + \pst@getcoors[\pssavebezier@ii%] +}% +\def\pssavebezier@ii{% + \addto@pscode{% + % only 10 points allowed, remove the rest + counttomark 20 gt { counttomark 20 sub { pop } repeat } if + % reverse the point order + counttomark -2 4 { 2 roll } for + %\addto@pscode{% + %counttomark 2 add -1 roll pop % remove the path name + counttomark 2 idiv 1 sub dup 9 gt { pop 9 } if + \psk@plotpoints\space exch + \txFunc@BezierCurve + \ifshowpoints \txFunc@BezierShowPoints \else pop \fi + tx@FuncDict begin Points aload pop end + }% + \let\use@pscode\PIT@use@pscode + \end@OpenObj + \PIT@Verb{% + [ count 1 sub 1 roll ] ArrayToPointArray def + }% +\ignorespaces}% +\define@key[psset]{intersect}{tstart}{% + \pst@checknum{#1}\PIT@key@tstart +} +\define@key[psset]{intersect}{tstop}{% + \pst@checknum{#1}\PIT@key@tstop +} +\define@key[psset]{intersect}{istart}{% + \pst@checknum{#1}\PIT@key@istart +} +\define@key[psset]{intersect}{istop}{% + \pst@checknum{#1}\PIT@key@istop +} +\define@key[psset]{intersect}{name}{% + \def\PIT@key@name{#1}% +}% +\newif\PIT@saveintersections +\define@boolkey[psset]{intersect}[PIT@]{saveintersections}[true]{} +\psset[intersect]{% + tstart=-1, + tstop=-1, + istart=-1, + istop=-1, + name={}, + saveintersections +}% +\def\PIT@use@pscode{% + \pstverb{% + \pst@dict + \tx@STP + \pst@newpath + \psk@origin + \psk@swapaxes + \pst@code + end + count /ocount exch def + }% + \gdef\pst@code{}% +}% +\let\PIT@pst@stroke@orig\pst@stroke +\def\PIT@save@path{% + \PIT@pst@stroke@orig + \addto@pscode{% + clear mark + { /movetype counttomark 3 roll } + { /linetype counttomark 3 roll } + { /curvetype counttomark 7 roll }{} pathforall + counttomark 1 add -1 roll pop count }% +}% +\def\PIT@name@default{@tmp}% +\def\PIT@name#1{PIT@#1}% +\def\PIT@checkname#1{% + \ifx\@empty#1\@empty + \@pstrickserr{Unexpected empty argument!}\@ehpb + \fi +}% +\def\pssavepath{\pst@object{pssavepath}}% +\long\def\pssavepath@i#1#2{% + \begin@SpecialObj + \PIT@checkname{#1}% + \let\pst@stroke\PIT@save@path + \let\use@pscode\PIT@use@pscode + \pscustom{#2}% + \PIT@Verb{% + /\PIT@name{#1} + [ 3 -1 roll 2 add 2 roll ] def }% + \end@SpecialObj +}% +\def\pstracecurve{\pst@object{pstracecurve}}% +\def\pstracecurve@i#1{% + \addbefore@par{plotpoints=200}% + \begin@OpenObj + \@ifnextchar\bgroup + {\PIT@traceintersection{#1}}% + {\PIT@tracecurve{#1}}% +}% +\def\PIT@tracecurve#1{% + \PIT@checkname{#1}% + \addto@pscode{% + \pst@intersectdict + \PIT@name{#1} dup IsPath { + \PIT@key@tstart\space\PIT@key@tstop\space + ShowPathPortion + }{ + [exch dup + \PIT@key@tstart\space\PIT@key@tstop\space + dup 0 lt { pop 1 } if + ToUnitInterval Portion + { aload pop } forall + counttomark 2 sub 2 idiv + \psk@plotpoints + exch + \txFunc@BezierCurve + \ifshowpoints \txFunc@BezierShowPoints \else pop \fi + } ifelse + end + }% + \end@OpenObj +}% +\def\PIT@traceintersection#1#2{% + \PIT@checkname{#2}% + \addto@pscode{% + \pst@intersectdict + \ifx\\#1\\% + /\PIT@name{\PIT@name@default} + \else + /\PIT@name{#1} + \fi + dup currentdict exch known not { + \ifx\\#1\\% + (You haven't defined an intersection!) == + \else + (You haven't defined the intersection '#1') == + \fi + } if + load + dup dup type /dicttype eq exch /\PIT@name{#2} known and not { + (You haven't defined the intersection '#2') == + } if + dup /\PIT@name{#2} get + exch /\PIT@name{#2}@t get + dup length \PIT@key@istart\space ge 0 \PIT@key@istart\space lt and { + dup \PIT@key@istart\space cvi 1 sub get + } { + \PIT@key@tstart + } ifelse + exch % [curve] t_istart|tstart [ts] + % + dup length \PIT@key@istop\space ge 0 \PIT@key@istop\space lt and { + \PIT@key@istop\space cvi 1 sub get + } { + pop \PIT@key@tstop + } ifelse + 2 copy 2 copy gt 3 1 roll -1 gt exch -1 gt and and { exch } if + 3 -1 roll dup + IsPath { + 3 1 roll + ShowPathPortion + }{ + [ exch dup 5 -2 roll + dup 0 lt { pop 1 } if + ToUnitInterval Portion + { aload pop } forall + counttomark 2 sub 2 idiv + \psk@plotpoints + exch + \txFunc@BezierCurve + \ifshowpoints \txFunc@BezierShowPoints \else pop \fi + } ifelse + end + }% + \end@OpenObj +}% +% +% \begin{macro}{\psintersect} +% \begin{macrocode} +\def\psintersect{\pst@object{psintersect}} +\def\psintersect@i#1#2{% + \PIT@checkname{#1}% + \PIT@checkname{#2}% + \begin@SpecialObj + \def\PIT@@name{% + \ifx\PIT@key@name\@empty + \PIT@name{\PIT@name@default} + \else + \PIT@name{\PIT@key@name} + \fi}% + \PIT@Verb{% + currentdict /\PIT@name{#1} known not { + (You haven't defined the curve or path '#1') == + } if + currentdict /\PIT@name{#2} known not { + (You haven't defined the curve or path '#2') == + } if + \PIT@name{#1} \PIT@name{#2} + \PIT@name{#1} IsPath { + \PIT@name{#2} IsPath { + IntersectPaths + }{ + IntersectPathCurve + } ifelse + }{ + \PIT@name{#2} IsPath { + IntersectCurvePath + }{ + IntersectBeziers + 4 copy LoadIntersectionPoints 5 1 roll + } ifelse + } ifelse + /\PIT@@name\space /\PIT@name{#1} /\PIT@name{#2} 8 3 roll + SaveIntersection + }% + \ifPIT@saveintersections + \pst@Verb{% + \pst@intersectdict + \PIT@@name\space /Points get + ArrayToPointArray + end + tx@NodeDict begin + dup length 1 1 3 -1 roll { + 2 copy 1 sub get cvx + false 3 -1 roll (N@\PIT@key@name) exch 20 string cvs + \pst@intersectdict strcat end cvn + 10 {InitPnode} /NodeScale {} def NewNode + } for + end + pop + }% + \fi + \ifshowpoints + \addto@pscode{% + \pst@intersectdict + [ \PIT@@name\space /Points get aload pop + end + }% + \psdots@ii + \else + \end@SpecialObj + \fi +}% +% \end{macrocode} +% \end{macro} +% +% \begin{macrocode} +\catcode`\@=\PstAtCode\relax +% \end{macrocode} +%</texfile> +% +% \chapter{The Postscript header file} +% \makeatletter +%^^A Copied this definition from doc.sty and changed it not to add a +%^^A backslash to the Postscript procedure name in the index. +% \def\SpecialIndex@#1#2{% +% \@SpecialIndexHelper@#1\@nil +% \def\@tempb{ }% +% \ifcat \@tempb\@gtempa +% \special@index{\quotechar\space\actualchar +% \string\verb\quotechar*\verbatimchar +% \quotechar\space\verbatimchar#2}% +% \else +% \def\@tempb##1##2\relax{\ifx\relax##2\relax +% \def\@tempc{\special@index{\quotechar##1\actualchar +% \string\verb\quotechar*\verbatimchar +% \quotechar##1\verbatimchar#2}}% +% \else +% \def\@tempc{\special@index{##1##2\actualchar +% \string\verb\quotechar*\verbatimchar##1##2\verbatimchar#2}}% +% \fi}% +% \expandafter\@tempb\@gtempa\relax +% \@tempc +% \fi} +% \makeatother +% +%<*prolog> +% \begin{macrocode} +/tx@IntersectDict 200 dict def +tx@IntersectDict begin +% \end{macrocode} +% These are some helper procedures for vector operations. +% +% \begin{macro}{VecAdd} +% Addition of two vectors. +% \begin{pssyntax} +% \PSvar{Xa Ya Xb Yb} \PSop{VecAdd} \PSvar{Xa+Xb Ya+Yb} +% \end{pssyntax} +% \begin{macrocode} +/VecAdd { + 3 -1 roll add 3 1 roll add exch +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{VecSub} +% Subtraction of two vectors. +% \begin{pssyntax} +% \PSvar{Xa Ya Xb Yb} \PSop{VecSub} \PSvar{Xa-Xb Ya-Yb} +% \end{pssyntax} +% \begin{macrocode} +/VecSub { + neg 3 -1 roll add 3 1 roll neg add exch +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{VecScale} +% Scale a vector by a factor \PSvar{fac}. +% \begin{pssyntax} +% \PSvar{Xa Ya fac} \PSop{VecScale} \PSvar{fac}$\cdot$\PSvar{Xa} \PSvar{fac}$\cdot$\PSvar{Ya} +% \end{pssyntax} +% \begin{macrocode} +/VecScale { + dup 4 -1 roll mul 3 1 roll mul +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ToVec} +% Convert two numbers to a procedure holding the two values. This +% representation is used to save coordinate values of nodes and vectors. +% \begin{pssyntax} +% \PSvar{X Y} \PSop{ToVec} \PSarray{X Y} +% \end{pssyntax} +% \begin{macrocode} +/ToVec { + [ 3 1 roll ] +} bind def +% \end{macrocode} +% \end{macro} +% +% \PSvar{MaxPrecision} gives the precision of the curve parameter t for the +% intersection. This shouldn't be lower than $10^{-6}$, because +% PostScript uses single precision. +% \begin{macrocode} +/MaxPrecision 1e-6 def +% \end{macrocode} +% +% \PSvar{Epsilon} gives the allowed relative error of the intersection point. +% \begin{macrocode} +/Epsilon 1e-4 def +% \end{macrocode} +% +% The threshold for curve subdivision, see below. +% \begin{macrocode} +/MinClippedSizeThreshold 0.8 def +% \end{macrocode} +% +% The predefined intervals for the subdivision of the curves. +% \begin{macrocode} +/H1Interval [0 0.5] def +/H2Interval [0.5 MaxPrecision add 1] def +% \end{macrocode} +% +% \begin{macro}{IntersectBeziers} +% The main procedure, which computes the intersection of two bezier +% curves of arbitrary order. This, and most of the following +% procedures operate on curves, which are stored as arrays of points, +% the points are also arrays with two elements -- \PSvar{X} and +% \PSvar{Y}. A Bezier curve of $n$-th order is then givesn by +% \PSarray{\PSarray{X0 Y0} \PSarray{X1 Y1} \ldots \PSarray{XN YN}}. +% +% \begin{pssyntax} +% \PSarray{curveA} \PSarray{curveB} \PSop{IntersectBeziers} +% \PSarray{curveA} \PSarray{tA} \PSarray{curveB} \PSarray{tB} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{IntersectLines} +% +% \begin{pssyntax} +% \PSarray{lineA} \PSarray{lineB} \PSop{IntersectLines} +% \PSarray{lineA} \PSarray{tA} \PSarray{lineB} \PSarray{tB} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% \begin{macro}{IntersectPaths} +% \begin{pssyntax} +% \PSarray{pathA} \PSarray{pathB} \PSop{IntersectPaths} +% \PSarray{intersections} \PSarray{pathA} \PSarray{tA} \PSarray{pathB} \PSarray{tB} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{IntersectCurvePath} +% \begin{pssyntax} +% \PSarray{curveA} \PSarray{pathB} \PSop{IntersectCurvePath} +% \PSarray{intersections} \PSarray{curveA} \PSarray{tA} \PSarray{pathB} \PSarray{tB} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{SaveIntersection} +% \begin{pssyntax} +% \PSname{isectname} \PSname{nameA} \PSname{nameB} +% \PSarray{intersectionpoints} \PSarray{A} \PSarray{tA} \PSarray{B} \PSarray{tB} +% \PSop{SaveIntersection} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{TArray} +% The curve parameters \PSvar{t} as determined by +% \PSvar{IntersectBeziers} are given in a special array +% construct. \PSvar{TArray} creates a simple array with the +% \PSvar{t}-values given in ascending order. +% +% \begin{pssyntax} +% \PSarray{\PSarray{t0a t0b} \ldots \PSvar{null}\ldots \PSvar{integer}} +% \PSop{TArray} \PSarray{t0 t1 \ldots tN} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% We can save arbitrary paths using \PSvar{pathforall}. The saved path +% contains the commands \PSname{movetype}, \PSname{linetype} and +% \PSname{curvetype}. By default, these are defined as the respective +% original procedures. +% \begin{macrocode} +/movetype { /moveto load } bind def +/linetype { /lineto load } bind def +/curvetype { /curveto load } bind def +% \end{macrocode} +% +% [ ... /movetype ... /linetype .../curvetype ] +% \begin{macrocode} +/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 +% \end{macrocode} +% +% \begin{macro}{LoadLineIntersectionPoints} +% Prepare \PSarray{Curve} for use with tx@Func +% \begin{pssyntax} +% \PSarray{curve} \PSarray{t} \PSop{LoadLineIntersectionPoints} +% \PSarray{I0.x I0.y \ldots IN.x YN.x} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{LoadCurveIntersectionPoints} +% Load the intersection points. This loads the same intersection point +% from both curves, and chooses the one with the lowest error. +% \begin{pssyntax} +% \PSarray{curveA} \PSarray{tA} \PSArray{curveB} \PSarray{tB} +% \PSop{LoadCurveIntersectionPoints} +% \PSarray{I0.x I0.y \ldots IN.x YN.x} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{LoadIntersectionPoints} +% \begin{macrocode} +/LoadIntersectionPoints { + (LoadIntersectionPoints) DebugBegin + 4 copy pop exch pop length 2 eq exch length 2 eq and { + pop pop LoadLineIntersectionPoints + }{ + LoadCurveIntersectionPoints + } ifelse + DebugEnd +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{IterateIntersection} +% Iteration procedure to compute all intersections of CurveA and CurveB. +% This contains the +% +% \begin{pssyntax} +% \PSarray{CurveA} \PSarray{CurveB} \PSarray{intervalA} \PSarray{intervalB} +% \PSop{IterateIntersection} \PSarray{domsA} \PSarray{domsB} +% \end{pssyntax} +% \begin{macrocode} +/IterateIntersection { + (IterateIntersection) DebugBegin + 11 dict begin + /precision MaxPrecision def +% \end{macrocode} +% in order to limit recursion +% \begin{macrocode} + /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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{_IterateIntersection} +% This is the iteration part which is called recursively. +% +% \begin{pssyntax} +% \PSname{domsA} \PSname{domsB} \PSarray{CurveA} \PSarray{CurveB} +% \PSarray{domA} \PSarray{domB} \PSop{_IterateIntersection} +% \end{pssyntax} +% \begin{macrocode} +/_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 { +% \end{macrocode} +% Use a loop to simulate some kind of return to exit at different positions. +% \begin{macrocode} + { + /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 +% \end{macrocode} +% iter < 100 && (dompA.extent() >= precision || dompB.extent() >= precision) +% \begin{macrocode} + 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 +% \end{macrocode} +% dom[0] > dom[1], invalid. +% \begin{macrocode} + 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 +% \end{macrocode} +% If we have clipped less than 20%, we need to subdivide the +% curve with the largest domain into two sub-curves. +% \begin{macrocode} + 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 +% \end{macrocode} +% Leave those five values on the stack to revert to the current state after the recursive calls. +% \begin{macrocode} + CurveA CurveB domA domB iter + 7 -2 roll 2 copy 9 2 roll 2 copy +% \end{macrocode} +% On the stack: /domsA /domsB CurveA CurveB domA domB iter /domsA /domsB /domsA /domsB +% \begin{macrocode} + 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 +% \end{macrocode} +% Need on the stack: /domsA /domsB pC2 CurveB dompC2 domB /domsA /domsB pC1 CurveB dompC1 domB +% \begin{macrocode} + 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 +% \end{macrocode} +% Need on the stack: /domsB /domsA pC2 CurveA dompC2 domA /domsB /domsA pC1 CurveA dompC1 domA +% \begin{macrocode} + 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 +% \end{macrocode} +% Restore the state before the recursive calls. +% \begin{macrocode} + /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 +% \end{macrocode} +% exchange /domsA and /domsB on the stack! +% \begin{macrocode} + exch + } loop +% \end{macrocode} +% boolean on stack +% \begin{macrocode} + { + 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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{PutInterval} +% Add a new interval \PSarray{newinterval} to the array stored in +% \PSname{/Intervals}. The new interval is "cloned" before storing it. +% \begin{pssyntax} +% \PSname{Intervals} \PSarray{newinterval} \PSop{PutInterval} +% \end{pssyntax} +% \begin{macrocode} +/PutInterval { + CloneVec [ exch 3 -1 roll dup 4 1 roll load aload pop ] def +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{IsEmptyInterval} +% Check if an interval is empty, which is represented by a [1 0] interval. +% \begin{pssyntx} +% \PSarray{interval} \PSop{IsEmptyInterval} \PSvar{boolean} +% \begin{macrocode} +/IsEmptyInterval { + aload pop 0 eq exch 1 eq and +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ToUnitInterval} +% Limit an interval \PSvar{a b} to the unit interval \PSarray{0 1}. +% \begin{pssyntax} +% \PSvar{a b} \PSop{ToUnitInterval} \PSarray{a|0 b|1} +% \end{pssyntax} +% \begin{macrocode} +/ToUnitInterval { + ToUnitRange exch ToUnitRange 2 copy gt { + exch + } if + ToVec +} bind def +% \end{macrocode} +% \end{macro} +% \begin{macro}{ToUnitRange} +% Limit a number to the range \PSarray{0 1}. +% \begin{macrocode} +/ToUnitRange { + dup 0 lt { + pop 0 + }{ + dup 1 gt { + pop 1 + } if + } ifelse +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{CloneCurve} +% Does a deep copy of the array \PSarray{Curve}. This also involved deep copies of the contained point arrays. +% \begin{pssyntax} +% \PSarray{Curve} \PSop{CloneCurve} \PSarray{newCurve} +% \begin{macrocode} +/CloneCurve { + [ exch { + CloneVec + } forall ] +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{CloneVec} +% Does a deep copy of the vector \PSarray{X Y} +% \begin{pssyntax} +% \PSarray{X Y} \PSop{CloneVec} \PSarray{Xnew Ynew} +% \end{pssyntax} +% \begin{macrocode} +/CloneVec { + aload pop ToVec +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{MapTo} +% Map the sub-interval \PSarray{I} in \PSarray{0 1} into the interval \PSarray{J}. Returns a new array. +% \begin{pssyntax} +% \PSarray{J} \PSarray{I} \PSop{MapTo} \PSarray{Jnew} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{Portion} +% Compute the portion of the Bezier curve \PSarray{CurveB} wrt the interval \PSarray{I}. +% \begin{pssyntax} +% \PSarray{CurveB} \PSarray{I} \PSop{Portion} \PSarray{CurvePartB} +% \end{pssyntax} +% \begin{macrocode} +/Portion { + (Portion) DebugBegin + dup Min 0 eq { % [CurveB] [I] + % I.min() == 0 + 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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{LeftPortion} +% Compute the portion of the Bezier curve \PSarray{CurveB} wrt the +% interval \PSarray{0 t}. +% \begin{pssyntax} +% \PSarray{CurveB} \PSvar{t} \PSop{LeftPortion} \PSarray{CurvePartB} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{RightPortion} +% Compute the portion of the Bezier curve \PSarray{CurveB} wrt the +% interval \PSarray{t 1}. +% \begin{pssyntax} +% \PSarray{CurveB} \PSvar{t} \PSop{RightPortion} \PSarray{CurvePartB} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{Lerp} +% Given two points and a parameter \PSvar{t} $\in$ \PSarray{0 1}, return a point +% proportionally from \PSarray{A} to \PSarray{B} by \PSvar{t}. Akin to 1 degree Bezier. +% \begin{pssyntax} +% \PSvar{t} \PSarray{A} \PSarray{B} \PSop{Lerp} \PSarray{newpoint} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{IsConstant} +% Test if all points of a curve are near to each other. This is used as termination criterium for the intersection procedure. +% \begin{pssyntax} +% \PSarray{Curve} \PSop{IsConstant} \PSvar{boolean} +% \end{pssyntax} +% \begin{macrocode} +/IsConstant { + aload length [ exch 1 roll ] true 3 1 roll + { + exch dup 4 1 roll + AreNear and exch + } forall + pop +} bind def +% \end{macrocode} +% \end{macro} +% \begin{macro}{AreNear} +% Test if two points are near to each other. +% \begin{pssyntax} +% \PSarray{P1} \PSarray{P2} \PSop{AreNear} \PSvar{boolean} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{Min} +% Get the minimum value of the vector \PSarray{P}. +% \begin{pssyntax} +% \PSarray{P} \PSop{Min} \PSvar{minimum} +% \end{pssyntax} +% \begin{macrocode} +/Min { + aload pop min +} bind def +% \end{macrocode} +% \end{macro} +% \begin{macro}{Min} +% Get the maximum value of the vector \PSarray{P}. +% \begin{pssyntax} +% \PSarray{P} \PSop{Max} \PSvar{maximum} +% \end{pssyntax} +% \begin{macrocode} +/Max { + aload pop max +} bind def +% \end{macrocode} +% \end{macro} +% \begin{macro}{Min} +% Get the extent of the interval \PSarray{I}. +% \begin{pssyntax} +% \PSarray{I} \PSop{Extent} \PSvar{I1-I0} +% \end{pssyntax} +% \begin{macrocode} +/Extent { + aload pop exch sub +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{MiddlePoint} +% Compute the middle point of the first and last point of \PSarray{Curve}. +% \begin{pssyntax} +% \PSarray{Curve} \PSop{MiddlePoint} \PSvar{X Y} +% \end{pssyntax} +% \begin{macrocode} +/MiddlePoint { + dup dup length 1 sub get aload pop + 3 -1 roll 0 get aload pop + VecAdd 0.5 VecScale +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{OrthogonalOrientationLine} +% \begin{pssyntax} +% \PSvar{MiddlePointA} \PSarray{CurveB} \PSop{OrthogonalOrientationLine} \PSvar{A B C} +% \end{pssyntax} +% \begin{macrocode} +/OrthogonalOrientationLine { + (OrthogonalOrientationLine) DebugBegin + dup dup length 1 sub get aload pop 3 -1 roll 0 get aload pop VecSub +% \end{macrocode} +% rotate by +90 degrees +% \begin{macrocode} + neg exch + 4 2 roll 2 copy 6 2 roll VecAdd + ImplicitLine + DebugEnd +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{PickOrientationLine} +% Pick an orientation line for a Bezier curve. This uses the first +% point and the lastmost point, which is not near to it. +% \begin{pssyntax} +% \PSarray{Curve} \PSop{PickOrientationLine} \PSvar{A B C} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ImplicitLine} +% Compute the coefficients \PSvar{A}, \PSvar{B}, \PSvar{C} of the normalized implicit equation +% of the line which goes through the points \PSarray{Xi Yi} and \PSarray{Xj Yj}. +% +% \begin{pssyntax} +% \PSvar{Xi Yi Xj Yj} \PSop{ImplicitLine} \PSvar{A B C} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{distance} +% Compute the distance of point \PSarray{X Y} from the implicit line given +% by $Ax + By + C = 0,\quad (A^2+B^2 = 1)$. +% \begin{pssyntax} +% \PSvar{X Y A B C} \PSop{distance} \PSvar{d} +% \end{pssyntax} +% \begin{macrocode} +/distance { + 5 1 roll 3 -1 roll mul 3 1 roll mul add add +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ArrayToPointArray} +% \begin{pssyntax} +% \PSarray{A.x A.y ... N.x N.y} \PSop{ArrayToPointArray} \PSarray{\PSarray{A.x A.y} \ldots \PSarray{N.x N.y}} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{PointArrayToArray} +% \begin{pssyntax} +% \PSarray{\PSarray{A.x A.y} \ldots \PSarray{N.x N.y}} \PSop{PointArrayToArray} \PSarray{A.x A.y ... N.x N.y} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ClipCurve} +% Clip the Bezier curve B with respect to the Bezier curve A for +% individuating intersection points. The new parameter interval for the +% clipped curve is pushed on the stack. +% \begin{pssyntax} +% \PSarray{CurveA} \PSarray{CurveB} \PSop{ClipCurve} \PSarray{newinterval} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{FatLineBounds} +% Compute the boundary of the fat line given by \PSvar{A B C} +% \begin{pssyntax} +% \PSvar{A B C} \PSarray{Curve} \PSop{FatLineBounds} \PSvar{A B C} \PSarray{dmin dmax} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ClipCurveInterval} +% Clip the Bezier curve wrt the fat line defined by the orientation +% line (given by \PSvar{A B C}) and the interval range +% \PSarray{bound}. The new parameter interval \PSarray{newinterval} +% for the clipped curve is pushed on the stack. +% \begin{pssyntax} +% \PSvar{A B C} \PSarray{bound} \PSarray{curve} \PSop{ClipCurveInterval} \PSarray{newinterval} +% \end{pssyntax} +% \begin{macrocode} +/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 +% \end{macrocode} +% get the x-coordinate of the i-th point, i getX -> D[i][X] +% \begin{macrocode} + /getX { D exch get 0 get } def +% \end{macrocode} +% get the y-coordinate of the i-th point, i getY -> D[i][Y] +% \begin{macrocode} + /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 { +% \end{macrocode} +% inside the fat line +% \begin{macrocode} + 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 { +% \end{macrocode} +% inside the fat line +% \begin{macrocode} + tmin i getX gt { /tmin i getX def } if + tmax i getX lt { /tmax i getX def } if + } if + clower plower eq not { +% \end{macrocode} +% cross the lower bound +% \begin{macrocode} + 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 { +% \end{macrocode} +% cross the upper bound +% \begin{macrocode} + 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 +% \end{macrocode} +% we have to test the closing segment for intersection +% \begin{macrocode} + /i D length 1 sub def + /clower 0 getY boundMin lt def + /chigher 0 getY boundMax gt def + clower plower eq not { +% \end{macrocode} +% cross the lower bound +% \begin{macrocode} + 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 { +% \end{macrocode} +% cross the lower bound +% \begin{macrocode} + 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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{Intersect} +% Get the x component of the intersection point between the line +% passing through $i$-th and $j$-th points of \PSarray{Curve} and the +% horizonal line through \PSvar{y}. +% \begin{pssyntax} +% \PSvar{y i j} \PSarray{Curve} \PSop{Intersect} \PSvar{Xisect} +% \end{pssyntax} +% \begin{macrocode} +/Intersect { + dup 4 -1 roll get aload pop + 4 2 roll exch get aload pop +% \end{macrocode} +% On the stack: \PSvar{y Xi Yi Xj Yj}, Compute (Xj - Xi) * (y - Yi)/(Yj - Yi) + Xi +% +% We are sure, that Yi != Yj, because this procedure is called only +% when the lower or upper bound is crossed. +% \begin{macrocode} + 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 +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{IsPath} +% Check if an array is a path. A path is represented as array, which +% contains other arrays which represent native Postscript +% operations. Those can be \PSarray{X Y /@m}, \PSarray{X Y /@l}, or +% \PSarray{X1 Y1 X2 Y2 X3 Y3 /@c}. +% +% \begin{pssyntax} +% \PSarray{array} \PSop{IsPath} \PSvar{boolean} +% \end{pssyntax} +% \begin{macrocode} +/IsPath { + dup length 1 sub get type /nametype eq { true } { false } ifelse +} bind def +% \end{macrocode} +% \end{macro} +% +% \begin{macro}{ShowFullPath} +% \begin{macrocode} +/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 +% \end{macrocode} +% \end{macro} +% +% \begin{macrocode} + % 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 +% \end{macrocode} +% +% Debugging stuff +% \begin{macrocode} +/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 +% \end{macrocode} +%</prolog> +% \Finale +% \endinput diff --git a/Master/texmf-dist/source/latex/pst-intersect/pst-intersect.ins b/Master/texmf-dist/source/latex/pst-intersect/pst-intersect.ins new file mode 100644 index 00000000000..936fc96b5e4 --- /dev/null +++ b/Master/texmf-dist/source/latex/pst-intersect/pst-intersect.ins @@ -0,0 +1,98 @@ +%% +%% Copyright (C) 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. +%% +%% Distribution: +%% CTAN:graphics/pstricks/contrib/pst-intersect/README +%% CTAN:graphics/pstricks/contrib/pst-intersect/Changes +%% CTAN:graphics/pstricks/contrib/pst-intersect/pst-intersect.ins +%% CTAN:graphics/pstricks/contrib/pst-intersect/pst-intersect.dtx +%% CTAN:graphics/pstricks/contrib/pst-intersect/pst-intersect.pdf +%% +%% Unpacking: +%% tex pst-intersect.ins +%% +%% Documentation: +%% make doc +%% +%% Installation: +%% TDS:tex/latex/pst-intersect/pst-intersect.sty +%% TDS:tex/generic/pst-intersect/pst-intersect.tex +%% TDS:dvips/pst-intersect/pst-intersect.pro +%% TDS:doc/latex/pst-intersect/README +%% TDS:doc/latex/pst-intersect/Changes +%% TDS:doc/latex/pst-intersect/pst-intersect.pdf +%% TDS:source/latex/pst-intersect/pst-intersect.ins +%% TDS:source/latex/pst-intersect/pst-intersect.dtx +%% +\input docstrip.tex +\keepsilent + +\preamble + +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. + +\endpreamble + +\askforoverwritefalse + +\generate{\file{pst-intersect.sty}{\from{pst-intersect.dtx}{stylefile}} + \file{pst-intersect.tex}{\from{pst-intersect.dtx}{texfile}} + \usepostamble\empty% + \file{pst-intersect.pro}{\from{pst-intersect.dtx}{prolog}}} + +\obeyspaces +\Msg{*************************************************************} +\Msg{* *} +\Msg{* To finish the installation you have to move the following *} +\Msg{* file into a directory searched by TeX: *} +\Msg{* *} +\Msg{* pst-intersect.sty *} +\Msg{* pst-intersect.tex *} +\Msg{* pst-intersect.pro *} +\Msg{* *} +\Msg{* To produce the documentation run the file *} +\Msg{* pst-intersect.dtx through LaTeX, preferably using the *} +\Msg{* Makefile. *} +\Msg{* *} +\Msg{* Happy TeXing! *} +\Msg{* *} +\Msg{*************************************************************} + +\endbatchfile diff --git a/Master/texmf-dist/tex/generic/pst-intersect/pst-intersect.tex b/Master/texmf-dist/tex/generic/pst-intersect/pst-intersect.tex new file mode 100644 index 00000000000..74c6fafc7f3 --- /dev/null +++ b/Master/texmf-dist/tex/generic/pst-intersect/pst-intersect.tex @@ -0,0 +1,295 @@ +%% +%% This is file `pst-intersect.tex', +%% generated with the docstrip utility. +%% +%% The original source files were: +%% +%% pst-intersect.dtx (with options: `texfile') +%% +%% 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. +%% +\csname PSTintersectLoaded\endcsname +\let\PSTintersectLoaded\endinput + +\ifx\PSTricksLoaded\endinput\else\input pstricks.tex \fi +\ifx\PSTXKeyLoaded\endinput\else \input pst-xkey.tex \fi +\ifx\PSTnodesLoaded\endinput\else\input pst-node.tex \fi +\ifx\PSTfuncLoaded\endinput\else \input pst-func.tex \fi + +\edef\PstAtCode{\the\catcode`\@} \catcode`\@=11\relax + +\pst@addfams{intersect} +\pstheader{pst-intersect.pro} + +\def\pst@intersectdict{tx@IntersectDict begin } +\def\PIT@dict#1{\pst@intersectdict #1 end} +\def\PIT@Verb#1{\pst@Verb{\PIT@dict{#1} }}% + +\def\pssavebezier{\pst@object{pssavebezier}} +\def\pssavebezier@i#1{% + \begin@OpenObj + \PIT@checkname{#1}% + \addto@pscode{ /\PIT@name{#1} }% + \pst@getcoors[\pssavebezier@ii%] +}% +\def\pssavebezier@ii{% + \addto@pscode{% + % only 10 points allowed, remove the rest + counttomark 20 gt { counttomark 20 sub { pop } repeat } if + % reverse the point order + counttomark -2 4 { 2 roll } for + %\addto@pscode{% + %counttomark 2 add -1 roll pop % remove the path name + counttomark 2 idiv 1 sub dup 9 gt { pop 9 } if + \psk@plotpoints\space exch + \txFunc@BezierCurve + \ifshowpoints \txFunc@BezierShowPoints \else pop \fi + tx@FuncDict begin Points aload pop end + }% + \let\use@pscode\PIT@use@pscode + \end@OpenObj + \PIT@Verb{% + [ count 1 sub 1 roll ] ArrayToPointArray def + }% +\ignorespaces}% +\define@key[psset]{intersect}{tstart}{% + \pst@checknum{#1}\PIT@key@tstart +} +\define@key[psset]{intersect}{tstop}{% + \pst@checknum{#1}\PIT@key@tstop +} +\define@key[psset]{intersect}{istart}{% + \pst@checknum{#1}\PIT@key@istart +} +\define@key[psset]{intersect}{istop}{% + \pst@checknum{#1}\PIT@key@istop +} +\define@key[psset]{intersect}{name}{% + \def\PIT@key@name{#1}% +}% +\newif\PIT@saveintersections +\define@boolkey[psset]{intersect}[PIT@]{saveintersections}[true]{} +\psset[intersect]{% + tstart=-1, + tstop=-1, + istart=-1, + istop=-1, + name={}, + saveintersections +}% +\def\PIT@use@pscode{% + \pstverb{% + \pst@dict + \tx@STP + \pst@newpath + \psk@origin + \psk@swapaxes + \pst@code + end + count /ocount exch def + }% + \gdef\pst@code{}% +}% +\let\PIT@pst@stroke@orig\pst@stroke +\def\PIT@save@path{% + \PIT@pst@stroke@orig + \addto@pscode{% + clear mark + { /movetype counttomark 3 roll } + { /linetype counttomark 3 roll } + { /curvetype counttomark 7 roll }{} pathforall + counttomark 1 add -1 roll pop count }% +}% +\def\PIT@name@default{@tmp}% +\def\PIT@name#1{PIT@#1}% +\def\PIT@checkname#1{% + \ifx\@empty#1\@empty + \@pstrickserr{Unexpected empty argument!}\@ehpb + \fi +}% +\def\pssavepath{\pst@object{pssavepath}}% +\long\def\pssavepath@i#1#2{% + \begin@SpecialObj + \PIT@checkname{#1}% + \let\pst@stroke\PIT@save@path + \let\use@pscode\PIT@use@pscode + \pscustom{#2}% + \PIT@Verb{% + /\PIT@name{#1} + [ 3 -1 roll 2 add 2 roll ] def }% + \end@SpecialObj +}% +\def\pstracecurve{\pst@object{pstracecurve}}% +\def\pstracecurve@i#1{% + \addbefore@par{plotpoints=200}% + \begin@OpenObj + \@ifnextchar\bgroup + {\PIT@traceintersection{#1}}% + {\PIT@tracecurve{#1}}% +}% +\def\PIT@tracecurve#1{% + \PIT@checkname{#1}% + \addto@pscode{% + \pst@intersectdict + \PIT@name{#1} dup IsPath { + \PIT@key@tstart\space\PIT@key@tstop\space + ShowPathPortion + }{ + [exch dup + \PIT@key@tstart\space\PIT@key@tstop\space + dup 0 lt { pop 1 } if + ToUnitInterval Portion + { aload pop } forall + counttomark 2 sub 2 idiv + \psk@plotpoints + exch + \txFunc@BezierCurve + \ifshowpoints \txFunc@BezierShowPoints \else pop \fi + } ifelse + end + }% + \end@OpenObj +}% +\def\PIT@traceintersection#1#2{% + \PIT@checkname{#2}% + \addto@pscode{% + \pst@intersectdict + \ifx\\#1\\% + /\PIT@name{\PIT@name@default} + \else + /\PIT@name{#1} + \fi + dup currentdict exch known not { + \ifx\\#1\\% + (You haven't defined an intersection!) == + \else + (You haven't defined the intersection '#1') == + \fi + } if + load + dup dup type /dicttype eq exch /\PIT@name{#2} known and not { + (You haven't defined the intersection '#2') == + } if + dup /\PIT@name{#2} get + exch /\PIT@name{#2}@t get + dup length \PIT@key@istart\space ge 0 \PIT@key@istart\space lt and { + dup \PIT@key@istart\space cvi 1 sub get + } { + \PIT@key@tstart + } ifelse + exch % [curve] t_istart|tstart [ts] + % + dup length \PIT@key@istop\space ge 0 \PIT@key@istop\space lt and { + \PIT@key@istop\space cvi 1 sub get + } { + pop \PIT@key@tstop + } ifelse + 2 copy 2 copy gt 3 1 roll -1 gt exch -1 gt and and { exch } if + 3 -1 roll dup + IsPath { + 3 1 roll + ShowPathPortion + }{ + [ exch dup 5 -2 roll + dup 0 lt { pop 1 } if + ToUnitInterval Portion + { aload pop } forall + counttomark 2 sub 2 idiv + \psk@plotpoints + exch + \txFunc@BezierCurve + \ifshowpoints \txFunc@BezierShowPoints \else pop \fi + } ifelse + end + }% + \end@OpenObj +}% +\def\psintersect{\pst@object{psintersect}} +\def\psintersect@i#1#2{% + \PIT@checkname{#1}% + \PIT@checkname{#2}% + \begin@SpecialObj + \def\PIT@@name{% + \ifx\PIT@key@name\@empty + \PIT@name{\PIT@name@default} + \else + \PIT@name{\PIT@key@name} + \fi}% + \PIT@Verb{% + currentdict /\PIT@name{#1} known not { + (You haven't defined the curve or path '#1') == + } if + currentdict /\PIT@name{#2} known not { + (You haven't defined the curve or path '#2') == + } if + \PIT@name{#1} \PIT@name{#2} + \PIT@name{#1} IsPath { + \PIT@name{#2} IsPath { + IntersectPaths + }{ + IntersectPathCurve + } ifelse + }{ + \PIT@name{#2} IsPath { + IntersectCurvePath + }{ + IntersectBeziers + 4 copy LoadIntersectionPoints 5 1 roll + } ifelse + } ifelse + /\PIT@@name\space /\PIT@name{#1} /\PIT@name{#2} 8 3 roll + SaveIntersection + }% + \ifPIT@saveintersections + \pst@Verb{% + \pst@intersectdict + \PIT@@name\space /Points get + ArrayToPointArray + end + tx@NodeDict begin + dup length 1 1 3 -1 roll { + 2 copy 1 sub get cvx + false 3 -1 roll (N@\PIT@key@name) exch 20 string cvs + \pst@intersectdict strcat end cvn + 10 {InitPnode} /NodeScale {} def NewNode + } for + end + pop + }% + \fi + \ifshowpoints + \addto@pscode{% + \pst@intersectdict + [ \PIT@@name\space /Points get aload pop + end + }% + \psdots@ii + \else + \end@SpecialObj + \fi +}% +\catcode`\@=\PstAtCode\relax +\endinput +%% +%% End of file `pst-intersect.tex'. diff --git a/Master/texmf-dist/tex/latex/pst-intersect/pst-intersect.sty b/Master/texmf-dist/tex/latex/pst-intersect/pst-intersect.sty new file mode 100644 index 00000000000..b44496fb076 --- /dev/null +++ b/Master/texmf-dist/tex/latex/pst-intersect/pst-intersect.sty @@ -0,0 +1,50 @@ +%% +%% This is file `pst-intersect.sty', +%% generated with the docstrip utility. +%% +%% The original source files were: +%% +%% pst-intersect.dtx (with options: `stylefile') +%% +%% 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. +%% +\NeedsTeXFormat{LaTeX2e}[1999/12/01] +\ProvidesPackage{pst-intersect} + [2014/02/19 v0.1 package wrapper for pst-intersect.tex] +\NeedsTeXFormat{LaTeX2e}[1999/12/01] +\ProvidesPackage{pst-intersect}% + [2014/02/06 v0.1alpha package wrapper for pst-intersect.tex] +\RequirePackage{pstricks} +\RequirePackage{pst-xkey} +\RequirePackage{pst-node} +\RequirePackage{multido} +\RequirePackage{pst-func} +\input{pst-intersect.tex} +\IfFileExists{pst-intersect.pro}{% + \ProvidesFile{pst-intersect.pro} + [2014/02/06 PostScript prologue file] + \@addtofilelist{pst-intersect.pro}}{}% +\endinput +%% +%% End of file `pst-intersect.sty'. diff --git a/Master/tlpkg/bin/tlpkg-ctan-check b/Master/tlpkg/bin/tlpkg-ctan-check index aa326020450..2264e0d0d38 100755 --- a/Master/tlpkg/bin/tlpkg-ctan-check +++ b/Master/tlpkg/bin/tlpkg-ctan-check @@ -382,7 +382,7 @@ my @TLP_working = qw( pst-electricfield pst-eps pst-eucl pst-eucl-translation-bg pst-exa pst-fill pst-fit pst-fr3d pst-fractal pst-fun pst-func pst-gantt pst-geo pst-gr3d pst-grad pst-graphicx - pst-infixplot pst-jtree pst-knot pst-labo pst-layout + pst-infixplot pst-intersect pst-jtree pst-knot pst-labo pst-layout pst-lens pst-light3d pst-magneticfield pst-math pst-mirror pst-node pst-ob3d pst-ode pst-optexp pst-optic pst-osci pst-ovl diff --git a/Master/tlpkg/tlpsrc/collection-pstricks.tlpsrc b/Master/tlpkg/tlpsrc/collection-pstricks.tlpsrc index 7a46ae4c2e1..25a89398757 100644 --- a/Master/tlpkg/tlpsrc/collection-pstricks.tlpsrc +++ b/Master/tlpkg/tlpsrc/collection-pstricks.tlpsrc @@ -46,6 +46,7 @@ depend pst-gr3d depend pst-grad depend pst-graphicx depend pst-infixplot +depend pst-intersect depend pst-jtree depend pst-knot depend pst-labo diff --git a/Master/tlpkg/tlpsrc/pst-intersect.tlpsrc b/Master/tlpkg/tlpsrc/pst-intersect.tlpsrc new file mode 100644 index 00000000000..e69de29bb2d --- /dev/null +++ b/Master/tlpkg/tlpsrc/pst-intersect.tlpsrc |