From 342bbfe61b1247316d2b382c836cbb22a0fbcfe1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Dec 2009 08:53:00 +0100 Subject: [PATCH] Pridana druha prednaska o geometrii. --- 8-geom2/8-geom2.mp | 65 ++++ 8-geom2/8-geom2.tex | 125 ++++++++ 8-geom2/8-geom2_0_bear.eps | 391 +++++++++++++++++++++++++ 8-geom2/8-geom2_1_usecky.eps | 124 ++++++++ 8-geom2/8-geom2_2_polorovina.eps | 70 +++++ 8-geom2/8-geom2_3_voroneho_diagram.eps | 203 +++++++++++++ 8-geom2/Makefile | 3 + 8-geom2/lib.mp | 82 ++++++ 8 files changed, 1063 insertions(+) create mode 100644 8-geom2/8-geom2.mp create mode 100644 8-geom2/8-geom2.tex create mode 100644 8-geom2/8-geom2_0_bear.eps create mode 100644 8-geom2/8-geom2_1_usecky.eps create mode 100644 8-geom2/8-geom2_2_polorovina.eps create mode 100644 8-geom2/8-geom2_3_voroneho_diagram.eps create mode 100644 8-geom2/Makefile create mode 100644 8-geom2/lib.mp diff --git a/8-geom2/8-geom2.mp b/8-geom2/8-geom2.mp new file mode 100644 index 0000000..3720dc0 --- /dev/null +++ b/8-geom2/8-geom2.mp @@ -0,0 +1,65 @@ +input lib + +figname("8-geom2_"); +figtag("usecky"); +beginfig(1); + def drawusecka(expr p,q) = draw vertex(p); draw vertex(q); draw p--q; enddef; + pair A[],B[]; + A0 := origin; B0 := (4cm,1.5cm); + A1 := (0.5cm,1.5cm); B1 := (1cm,0); + A2 := (2cm,1.3cm); B2 := (3cm, -0.9cm); + A3 := (1cm,-1.3cm); B3 := (3.5cm,0); + z0 = whatever[A0,B0]; z0 = whatever[A1,B1]; + z1 = whatever[A0,B0]; z1 = whatever[A2,B2]; + z2 = whatever[A2,B2]; z2 = whatever[A3,B3]; + + for i:=0 upto 2: fill fullcircle scaled 7pt shifted z[i]; drawemptyvertex(z[i]); endfor + for i:=0 upto 3: drawusecka(A[i], B[i]); endfor +endfig; + +figtag("polorovina"); +beginfig(2); + pair A,B; + A := origin; + B := (1.7cm,0.5cm); + an := angle(B-A); + path p; p := from(.5[A,B],an+90,3cm)--from(.5[A,B],an-90,3cm); + fill p--reverse(p shifted (A-0.8[A,B]))--cycle withcolor 0.8white; + %fill p{dir (an+180)}..-0.35[A,B]..{dir an}cycle withcolor 0.8white; + draw p withpen boldpen; + + draw A--B dashed evenly; + drawemptyvertex(A); drawemptyvertex(B); + label.llft(btex $a$ etex, A); + label.urt(btex $b$ etex, B); +endfig; + +figtag("voroneho_diagram"); +beginfig(3); + u := 1.35cm; + pair A[],B[]; + A0 := origin; A1 := (-u,-u); A2 := (1.3u,-u); A3 := (1.5u,0.7u); A4 := (0.6u,0.8u); A5 := (0.2u,1.9u); A6 := (-1.3u,1u); + def osa(expr a, b, an,l) = from(.5[a,b], angle(b-a)+an, l) enddef; + vardef prusecik_os(expr p,q,r) = + save b; pair b; + b = whatever[osa(p,q, 90,1cm), osa(p,q,-90,1cm)]; + b = whatever[osa(q,r, 90,1cm), osa(q,r,-90,1cm)]; + b + enddef; + B[0] := prusecik_os(A0,A1,A2); B[1] := prusecik_os(A0,A1,A6); B[2] := prusecik_os(A0,A4,A6); B[3] := prusecik_os(A4,A5,A6); + B[4] := prusecik_os(A3,A4,A5); B[5] := prusecik_os(A0,A3,A4); B[6] := prusecik_os(A0,A2,A3); + draw osa(A1,A2,-90,2cm)--B[0]--B[1]--osa(A1,A6,90,1.3cm) withpen boldpen; + draw B[1]--B[2]--B[3]--osa(A6,A5,90,2cm) withpen boldpen; + draw B[3]--B[4]--osa(A3,A5,-90,2.7cm) withpen boldpen; + draw B[4]--B[5]--B[2] withpen boldpen; + draw B[5]--B[6]--osa(A2,A3,-90,1.3cm) withpen boldpen; + draw B[6]--B[0] withpen boldpen; + + draw A0--A1--A2--A0--A6--A1 dashed evenly; + draw A6--A5--A4--A0--A3--A2 dashed evenly; + draw A3--A5 dashed evenly; draw A6--A4--A3 dashed evenly; + + for i:=0 upto 6: draw vertex(B[i]); endfor + for i:=0 upto 6: drawemptyvertex(A[i]); endfor +endfig; +end diff --git a/8-geom2/8-geom2.tex b/8-geom2/8-geom2.tex new file mode 100644 index 0000000..5718249 --- /dev/null +++ b/8-geom2/8-geom2.tex @@ -0,0 +1,125 @@ +\input lecnotes.tex + +\prednaska{8}{Geometrie vrací úder}{(sepsal Pavel Klavík)} + +\>Kdy¾ s geometrickými problémy poøádnì nezametete, ony vám to vrátí! Ale kdy¾ u¾ zametat, tak urèitì ne pod koberec a místo smetáku si na nì vezmìte +pøímku. V této pøedná¹ce nás spolu s dvìma geometrickými problémy samozøejmì èeká pokraèování pohádky o ledních medvìdech. + +{\I Medvìdi vyøe¹ili rybí problém a hlad je ji¾ netrápí. Av¹ak na severu ne¾ijí sami, za sousedy mají Eskymáky. Proto¾e je rozhodnì lep¹í se sousedy +dobøe vycházet, jsou medvìdi a Eskymáci velcí pøátelé. Skoro ka¾dý se svými pøáteli rád schází. Av¹ak to je musí nejprve nalézt~\dots} + +\h{Hledání prùseèíkù úseèek} + +Zkusíme nejprve Eskymákùm vyøe¹it lokalizaci ledních medvìdù. + +{\I Kdy¾ takový medvìd nemá co na práci, rád se prochází. Na místech, kde se trasy protínají, je zvý¹ená ¹ance, ¾e se dva medvìdi potkají a zapovídají +-- ostatnì co byste èekali od medvìdù. To jsou ta správná místa pro Eskymáka, který chce potkat medvìda. Jenom¾e jak tato køí¾ení najít?} + +Pro zjednodu¹ení pøedpokládejme, ¾e medvìdi chodí po úseèkách tam a zpìt. Budeme tedy chtít nalézt v¹echny prùseèíky úseèek v rovinì. + +\bigskip +\centerline{\epsfxsize=1.5in\epsfbox{8-geom2_0_bear.eps}\hskip 4em\epsfxsize2in\epsfbox{8-geom2_1_usecky.eps}} +\smallskip +\centerline{Problém Eskymákù: Kde v¹ude se køí¾í medvìdí trasy?} +\bigskip + +Pro $n$ úseèek mù¾eme mít a¾ $\Omega(n^2)$ prùseèíkù.\foot{Zkuste takový pøíklad zkonstruovat.} Tedy optimální slo¾itosti by dosáhl i algoritmus, který +by pro ka¾dou dvojici úseèek testoval, zda se protínají. Èasto se slo¾itost algoritmu posuzuje i vzhledem k velikosti výstupu $p$. Typické rozmístìní +úseèek mívá toti¾ prùseèíkù spí¹e po málu. Pro tento pøípad si uká¾eme podstatnì rychlej¹í algoritmus. + +Pro jednodu¹¹í popis pøedpokládejme, ¾e úseèky le¾í v obecné poloze. To znamená, ¾e ¾ádné tøi úseèky se neprotínají v jednom bodì a prùnikem ka¾dých +dvou úseèek je nejvý¹e jeden bod. Navíc pøedpokládejme, ¾e krajní bod ¾ádné úseèky nele¾í na jiné úseèce a také neexistují vodorovné úseèky. Na závìr si +uká¾eme, jak se s tìmito pøípady vypoøádat. + +Algoritmus funguje na principu zametání roviny, popsaném v minulé pøedná¹ce. Budeme posouvat vodorovnou pøímku odshora dolù. V¾dy, kdy¾ narazíme na +nový prùnik, ohlásíme jeho výskyt. Samozøejmì spojité posouvání nahradíme diskrétním a pøímku v¾dy posuneme do dal¹ího zajímavého bodu. + +Zajímavé události jsou {\I zaèátky úseèek}, {\I konce úseèek} a {\I prùseèíky úseèek}. Po utøídìní známe pro první dva typy událostí poøadí, v jakém +se objeví. Výskyty prùseèíkù budeme poèítat prùbì¾nì, jinak bychom celý problém nemuseli øe¹it. + +V ka¾dém kroku si pamatujeme prùøez $P$ -- posloupnost úseèek aktuálnì protnutých zametací pøímkou. Tyto úseèky máme utøídìné zleva doprava. Navíc si +udr¾ujeme kalendáø $K$ budoucích událostí. Z hlediska prùseèíkù budeme na úseèky nahlí¾et jako na polopøímky. Pro sousední dvojice úseèek si +udr¾ujeme, zda se jejich smìry nìkde protnou. Algoritmus pro hledání prùnikù úseèek funguje následovnì: + +\s{Algoritmus:} + +\algo + +\:$P \leftarrow \emptyset$. +\:Do $K$ vlo¾íme zaèátky a konce v¹ech úseèek. +\:Dokud $K \ne \emptyset$: +\::Odebereme nejvy¹¹í událost. +\::Pokud je to zaèátek úseèky, zatøídíme novou úseèku do $P$. +\::Pokud je to konec úseèky, odebereme úseèku z $P$. +\::Pokud je to prùseèík, nahlásíme ho a prohodíme úseèky v $P$. +\::Navíc v¾dy pøepoèítáme prùseèíkové události, v¾dy maximálnì dvì odebereme a dvì nové pøidáme. +\endalgo + +Zbývá rozmyslet si, jaké datové struktury pou¾ijeme, abychom prùseèíky nalezli dostateènì rychle. Pro kalendáø pou¾ijeme napøíklad haldu. Kalendáø +obsahuje v¾dy nejvý¹e $\O(n)$ událostí. Seznam úseèek si budeme udr¾ovat ve vyva¾ovaném stromì, který obsahuje nejvý¹e $\O(n)$ prvkù. Proto jednu +událost kalendáøe doká¾eme vyøe¹it v èase $\O(\log n)$. V¹ech událostí je $\O(n+p)$, a tedy celková slo¾itost algoritmu je $\O((n+p) \log n)$. + +Na závìr poznamenejme, ¾e Balaban vymyslel efektivnìj¹í algoritmus, který funguje v èase $\O(n \log n + p)$, ale je podstatnì komplikovanìj¹í. + +\h{Hledání nejbli¾¹ího bodu} + +Nyní se pokusíme vyøe¹it i problém druhé strany. + +{\I Eskymáci tráví vìt¹inu èasu doma, ve svém Iglù. Takový medvìd je na své toulce zasnì¾enou krajinou, kdy¾ tu se najednou rozhodne nav¹tívit nìjakého +Eskymáka. Proto se podívá do své medvìdí mapy a nalezne nejbli¾¹í Iglù. Má to ale jeden háèek, medvìdi toti¾ neumí èíst v mapách!} + +Popí¹eme si nejprve, jak vypadá medvìdí mapa. Medvìdí mapa je {\I Voroného diagram}, co¾ je pro zadané body $x_1, \ldots, x_n$ rozdìlení roviny na +oblasti $B_1, \ldots, B_n$, kde $B_i$ je mno¾ina bodù nejblí¾e k bodu $x_i$. Formálnì jsou tyto oblasti zadefinovány následovnì: +$$B_i = \left\{y \in {\bb R}^2\ \vert\ \forall j:\rho(x_i,y) \le \rho(x_j,y)\right\}.$$ + +Pro dva body $a$ a $b$, mno¾ina v¹ech bodù bli¾¹ích k $a$ ne¾ k $b$ tvoøí polorovinu ohranièenou osou úseèky $ab$. Ka¾dá z oblastí $B_i$ je tvoøena +prùnikem $n-1$ polorovin, tedy je to (mo¾ná neomezený) mnohostìn.\foot{Sly¹eli jste u¾ o lineárním programování? Jak název vùbec nenapoví, +{\I lineární programování} je teorii zabývající se øe¹ením a vlastnostmi soustav lineárních nerovnic. Lineární program je popsaný lineární funkcí, kterou chceme +maximalizovat za podmínek popsaných soustavou lineárních nerovnic. Ka¾dá nerovnice urèuje poloprostor, ve kterém se pøípustná øe¹ení nachází. +Proto¾e pøípustné øe¹ení splòuje v¹echny nerovnice zároveò, je mno¾ina v¹ech pøípustných øe¹ení (mo¾ná neomezený) mnohostìn. Mno¾iny $B_i$ lze +snadno popsat jako mno¾iny v¹ech pøípustných øe¹ení lineárního programù, pomocí vý¹e ukázaných polorovin. Na závìr poznamenejme, ¾e dlouho otevøená +otázka, zda lze nalézt optimální øe¹ení lineárního programu v polynomiálním èase, byla vyøe¹ena, je znám polynomiální algoritmu (kterému se øíká metoda +vnitøního bodu). Na druhou stranu, pokud chceme najít pøípustné celoèíselné øe¹ení, je úloha NP-úplná a je jednoduché na ni pøevést spoustu +optimalizaèních problémù. Dokázat v¹ak, ¾e tento problém le¾í v NP, není vùbec jednoduché.} +Voroneho diagram je naznaèen na obrázku, oblasti $B_i$ jsou ohranièené èernými èárami. + +\twofigures{8-geom2_2_polorovina.eps}{Body bli¾¹í k $a$ ne¾ $b$.}{1.25in} + {8-geom2_3_voroneho_diagram.eps}{Voroneho diagram.}{2.5in} + +Prùnik dvou oblastí mù¾e být, v závislosti na jejich sousedìní, prázdný, bod, úseèka, nebo polopøímka. V na¹em uva¾ování uzavøeme celý Voroneho diagram do +dostateènì velkého obdélníku. Proto¾e okraje mno¾in tvoøí rovinný graf, je podle Eulerovy formule (poèet hran je nejvý¹e $3n-6$) slo¾itost diagramu +$\O(n)$. Voroneho diagram lze zkonstruovat v èase $\O(n \log n)$. Tím se zabývat nebudeme,\foot{Pro zvídavé, kteøí nemají zkou¹ku druhý den ráno: +Detaily naleznete v zápiscích z loòského ADSka.} ale uká¾eme si, jak zadaný Voroneho diagram pou¾ít k rychlému nalezení nejbli¾¹ího bodu. + +Máme zadaný rozklad roviny na konvexní mnohoúhelníky. Chceme pro jednotlivé body rychle rozhodovat, do kterého mnohoúhelníku patøí. Na¹e øe¹ení budeme +optimalizovat pro jeden pevný rozklad a obrovské mno¾ství rùzných dotazù, které chceme co nejrychleji odpovìdìt.\foot{Pøedstavujme si to tøeba tak, ¾e +medvìdùm zprovozníme server. Ten jednou schroustá celou mapu a potom co nejrychleji odpovídá na jejich dotazy. Medvìdi sice neumí èíst v mapách, ale +pøipojit se na server hravì zvládnou!} Nejprve pøedzpracujeme Voroneho diagram a vytvoøíme strukturu, která nám umo¾ní rychlé dotazy na jednotlivé +body. + +Uka¾me si nejprve øe¹ení bez pøedzpracování. Rovinu budeme zametat pøímkou shora dolù. Podobnì jako pøi hledání prùseèíkù úseèek, udr¾ujeme si prùøez +pøímky. V¹imnìte si, ¾e tento prùøez se mìní jenom ve vrcholech mnohoúhelníkù. Ve chvíli, kdy narazíme na hledaný bod, podíváme se, do kterého +intervalu v prùøezu patøí, a ten nahlásíme. Prùøez budeme uchovávat ve vyhledávacím stromì. Takové øe¹ení má slo¾itost $\O(n \log n)$ na dotaz, co¾ je +hroznì pomalé. + +Pøedzpracování bude fungovat následovnì. Rozøe¾eme si celou rovinu na pásy, bìhem kterých se prùøez pøímkou nemìní. Pro ka¾dý z nich si budeme +pamatovat stav stromu, ve kterém se nacházel prùøez pøi procházení tímto pásem. Kdy¾ chceme lokalizovat nìjaký bod, nejprve pùlením nalezneme pás, v +kterém le¾í. Poté polo¾íme dotaz na pøíslu¹ný strom. Dotaz doká¾eme zodpovìdìt v èase $\O(\log n)$. + +Jenom¾e na¹e øe¹ení má jeden háèek: Jak zkonstruovat jednotlivé verze stromu dostateènì rychle? K tomu napomohou {\I èásteènì perzistentní} datové +struktury. Pod perzistencí se myslí, ¾e struktura si umo¾òuje uchovávat svoji historii. Èásteènì perzistentní struktury nemohou svoji historii +modifikovat. + +Popí¹eme si, jak vytvoøit perzistentní strom s pamìtí $\O(\log n)$ na zmìnu. Pokud provádíme operaci na stromì, mìní se jenom malá èást stromu. +Napøíklad pøi vkládání do stromu se mìní jenom prvky na jedné cestièce z koøene do listu (a pøípadnì rotací jejím nejbli¾¹ím okolí). Proto si ulo¾íme +upravenou cestièku a zbytek stromu budeme sdílet s pøedchozí verzí. Mimochodem zmìny ka¾dé operace se slo¾itostí $\O(k)$ lze zapsat v pamìti +$\O(k)$, prostì operace nemá tolik èasu, aby mohla pozmìnit pøíli¹ velikou èást stromu. + +Celková èasová slo¾itost je tedy $\O(n \log n)$ na pøedzpracování Voroneho diagramu a vytvoøení persistentního stromu. Kvùli persistenci potøebuje +toto pøedzpracování pamì» $\O(n \log n)$. Na dotaz spotøebujeme èas $\O(\log n)$, nebo» nejprve vyhledáme pùlením pøíslu¹ný pás a poté polo¾íme dotaz +na pøíslu¹nou verzi stromu. Rychleji ani celou operaci provést nepùjde, proto¾e potøebujeme utøídit souøadnice bodù. Na závìr poznamenejme, ¾e se umí +provést vý¹e uvedená persistence vyhledávacího stromu v amortizované pamìti $\O(1)$ na zmìnu. My¹lenka je, ¾e pou¾ijeme stromy, které pøi insertu a +deletu provádí amortizovanì jenom konstantnì mnoho úprav své struktury. To nám napøíklad zaruèí 2-4 stromy z pøedná¹ky a podobnou vlastnost lze +dokázat i o èervenoèerných stromech. Pøi zmìnì potom nebudeme upravovat celou cestu, ale upravíme jenom jednotlivé vrcholy, kterých se zmìna týká. + +\bye diff --git a/8-geom2/8-geom2_0_bear.eps b/8-geom2/8-geom2_0_bear.eps new file mode 100644 index 0000000..9e6ec74 --- /dev/null +++ b/8-geom2/8-geom2_0_bear.eps @@ -0,0 +1,391 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: Adobe Illustrator by AutoTrace version 0.31.1 +%%Title: /tmp/potraceguiTmp-r4ayx1 +%%CreationDate: Tue Dec 15 14:58:41 2009 +%%BoundingBox: 0 0 437 436 +%%DocumentData: Clean7Bit +%%EndComments +%%BeginProlog +/bd { bind def } bind def +/incompound false def +/m { moveto } bd +/l { lineto } bd +/c { curveto } bd +/F { incompound not {fill} if } bd +/f { closepath F } bd +/S { stroke } bd +/*u { /incompound true def } bd +/*U { /incompound false def f} bd +/k { setcmykcolor } bd +/K { k } bd +%%EndProlog +%%BeginSetup +%%EndSetup +0.000 0.000 0.000 0.000 k +*u +0.889 435 m +0 428 l +0 411 l +0 341 l +0 86 l +0 23 l +0 7 l +0.889 0.889 l +8 0 l +25 0 l +96 0 l +351 0 l +414 0 l +430 0 l +436 0.889 l +437 8 l +437 25 l +437 95 l +437 350 l +437 413 l +437 429 l +436 435 l +430 436 l +414 436 l +351 436 l +96 436 l +25 436 l +8 436 l +0.889 435 l +f +*U +0.000 0.000 0.000 1.000 k +*u +220 419.384 m +214.258 418.900 209.738 412.732 206 409 c +177 380 l +60 263 l +28 231 l +23.636 226.628 16.983 221.924 17.569 215 c +17.966 210.314 21.922 207 25 204 c +46 183 l +129 100 l +196 33 l +200.988 28 205.847 22.836 211 18 c +214 15 217.488 12.207 222 12.574 c +227.841 13 232.184 19.186 236 23 c +265 52 l +382 169 l +414 201 l +418.273 205.287 424.957 210.210 424.384 217 c +424 221.532 419.960 224.998 417 228 c +396 249 l +313 332 l +246 399 l +241.338 403.662 236.767 408.442 232 412.995 c +228.623 416.220 225 419.811 220 419.384 c +f +*U +0.000 0.000 0.000 0.000 k +*u +219 412 m +214.948 411.300 209.819 403.819 207 401 c +178 372 l +67 261 l +35 229 l +31.514 225.513 24 220.491 24.560 215 c +24.855 211.993 29 208.959 31 207 c +51 187 l +128 110 l +197 41 l +213 25 l +215.545 22.496 218 19.178 222 19.560 c +226.217 19.974 231.207 27.207 234 30 c +263 59 l +376 172 l +408 204 l +411.311 207.313 417.952 211.778 417.440 217 c +417 220 412.955 223 411 225 c +391 245 l +315 321 l +245 391 l +229 407 l +225.869 410 223.579 412.979 219 412 c +f +*U +0.000 0.000 0.000 1.000 k +*u +172.889 336 m +170.998 334.234 171.922 328.436 172 326 c +172 316 l +172 315.315 171.810 312.961 172.477 312.477 c +176 309.805 188.847 309.482 192.194 313.417 c +195.490 317.290 192.799 320.854 192.352 325 c +192 327.341 192.862 329.614 192.639 331.981 c +192.491 333.552 191.208 334 190.657 335.370 c +189.415 338 183 336.438 181 337 c +179.248 337.464 174.267 337.479 172.889 336 c +f +199.477 336 m +197.564 334.376 198 331.340 198 329 c +197.990 323.328 197.538 317.316 198.931 311.889 c +199.415 309.999 206.643 311.290 208 311 c +210 310.568 217 310 218.347 312.213 c +219 313.445 218 315.202 216.769 315.542 c +213.652 316.376 210.280 315.904 207 316.218 c +206 316.317 203 318.549 204.560 319.806 c +207.259 322 209.274 321.923 212.977 322 c +213.507 322 215.939 322 216 322.884 c +217.293 328.608 210.397 326.742 206.222 327.477 c +204 327.861 205.500 329.966 204.972 330.546 c +204.504 331 207.832 331.907 208 331.917 c +211.432 332 214.994 331.443 217.634 333.528 c +219.388 334.912 215.841 336.844 214.917 336.917 c +211.536 337.181 202 338.521 199.477 336 c +f +230.338 336 m +228.295 335 227.688 331.869 226.958 330 c +224.730 324.291 220.366 317 221.532 311.481 c +221.661 310.858 224.347 311.205 224.667 311.481 c +226.578 313 227.861 315.219 230 316.523 c +231.295 317.239 232.776 316.565 233.995 316.912 c +237.858 318 240.746 308.207 244.468 311.481 c +246.651 313.403 243.853 317.862 243 320 c +240.971 325 238.180 339.804 230.338 336 c +f +249.889 336 m +248.354 334.588 249 330.936 249 329 c +248.998 323.476 248.794 317.918 249.477 312.477 c +249.598 311.508 250.778 311.790 251 311.301 c +251.593 310.671 253.413 311.959 253.523 312.477 c +254.380 316.515 253.694 318.510 257 320.634 c +257.881 321 260.170 318.434 260.528 317.972 c +262 315.967 267.342 307.455 270.912 311.889 c +273.328 314.890 265 319.561 265.773 322.194 c +266.468 324.760 272.683 328.192 269.657 331.981 c +268.721 333 268.751 335.447 266.843 335.935 c +262.844 336.958 259.174 337 255 337 c +253.470 336.994 251 337.309 249.889 336 c +f +*U +0.000 0.000 0.000 0.000 k +*u +178.894 331 m +175.494 327.716 183.844 325.552 186 328.454 c +188.896 332 180.705 332.927 178.894 331 c +f +254.894 331 m +251.213 326.883 260.433 324.563 263 327.750 c +266.617 331.934 256.917 333.436 254.894 331 c +f +232.551 328.634 m +230.239 328 228.887 320 233.745 321.778 c +236.325 322.635 234.557 329 232.551 328.634 c +f +178.889 321 m +174.699 317.211 183.708 314.378 186.519 316.889 c +190.905 320.808 181.667 323.697 178.889 321 c +f +*U +0.000 0.000 0.000 1.000 k +*u +191 281.667 m +187.598 281.491 184.424 279.269 181 279 c +176.312 278.632 171.746 279.233 167 279 c +165 278.909 163.802 277.516 162 277.333 c +159 277 157.653 281.525 154 280.667 c +149.406 279.587 151.537 275.240 148.833 273 c +146 271 142.648 270.471 140 268 c +137.201 265.387 136 261.817 133.667 259 c +128 252.581 118 247.887 125.333 239 c +129 234.394 134.914 236.592 140 236 c +146 235.298 151.947 233.610 158 233 c +163.838 232.411 169.512 234.560 173.500 229 c +175 226.856 174 220.554 174 218 c +173.289 206.749 173.204 192.607 167 183 c +164.676 179.402 159.544 180.200 156 179.667 c +152.669 179 151 177.726 148.500 176 c +147.781 175.518 150 172.759 150.500 172.500 c +153.358 170.792 156.602 169.829 159.667 168.667 c +160.667 167.333 l +162.518 166.944 165 167.989 167 168 c +183 168 l +185.625 168 188.377 167.483 190.500 169.167 c +191.529 169.983 191.702 173.674 192.667 175 c +197.364 181.457 200.195 187.357 203.333 194.667 c +203.845 195.858 204.811 192.916 205.500 193.667 c +207 195.447 207.656 199.703 208.167 202 c +208.240 202.331 208.803 204 209.500 204 c +210.284 203.846 212.514 199.743 212.833 199 c +214 196 220.921 187.847 217.500 184.167 c +216 182.667 213.839 182.972 212 182.333 c +209.816 181.575 207.994 180 206 179 c +204.473 178 201.266 177 202.500 174.500 c +203.253 172.961 208.668 175 210 175 c +216.398 174.451 221.588 174.301 228 175 c +230.354 175.257 233.749 174 235.500 176.167 c +237.341 178.333 234.792 181.707 235 184 c +235.495 189.469 236.860 194.418 237 200 c +237 202.274 234.495 206.455 237 207.500 c +237.778 207.824 239.525 206.190 240 205.833 c +242 204.322 245 201.297 248 201.667 c +249.619 201.875 249.916 204 252 204 c +255.424 203.804 258.514 202.515 262 202.667 c +263.671 202.739 267.209 206.359 268.833 204.500 c +273.281 199.411 269.573 191.600 269 186 c +268.699 183 270.305 179.854 270.833 177 c +271 175.349 270 174.566 269.667 173.167 c +268.756 169.835 260.413 171 258 170.667 c +255.743 170.232 255.570 168.300 254.333 167.167 c +253.830 166.705 256.982 164.595 257.333 164.500 c +261.464 163.386 265.698 161.604 270 161 c +275 160.292 280.906 160.858 286 161 c +287.716 161 290.445 161.689 291.500 163.167 c +292.792 164.978 290.718 167 291 169 c +291.721 173.780 293.169 177 296 181 c +296.605 181.837 298.469 184 299.667 184 c +301.443 184 301.187 178.924 300.667 178 c +299.458 175.852 295.192 172.406 295 170 c +295 169.426 294.538 166.821 295.500 166.500 c +297.526 165.825 302 165.221 304 166.500 c +306.462 168 306.515 170.989 308.333 173 c +309.907 174.740 312.538 175.896 313.667 178 c +315.182 180.825 315.396 184 316.500 187 c +317.335 189.261 320.545 191.195 320 194 c +319.874 194.648 320.213 196.363 319.500 196.833 c +316.355 198.910 309.258 200.809 310 206 c +310.909 212.358 314 217.622 315.667 224 c +316.469 227.319 315.500 230.385 315.500 233.667 c +315.500 234 316.624 233.212 316.667 235 c +316.794 240.385 312.910 245.980 311.667 251 c +311 253 312.321 255.811 312 258 c +311.407 262 309.438 264.746 306.667 267.667 c +300.930 273.712 291.945 275 284 276.333 c +270.400 278.522 255.739 278.712 242 278.833 c +237 278.877 232.282 276.629 227 277 c +222.577 277.311 218.410 279.514 214 280 c +209.549 280.490 205.317 279.187 201 279 c +199.793 279 198.199 280.779 197 281 c +194.862 281.857 193 281.778 191 281.667 c +f +*U +0.000 0.000 0.000 0.000 k +*u +193.667 280.667 m +194.333 280.333 l +193.667 280.667 l +f +143.458 259.954 m +141.215 258.578 143 254.449 145.542 255.968 c +147.778 257.361 145.819 261.401 143.458 259.954 c +f +245 204 m +246 203 l +245 204 l +f +*U +0.000 0.000 0.000 1.000 k +*u +151 136.431 m +135.811 134.402 140 109.233 155.935 114.630 c +157.896 115.295 159 116.964 159.440 118.935 c +159.514 119.374 159.201 120.989 158.523 121 c +156.450 121 152.662 117.837 151 118.694 c +146.330 121 146.224 124.360 147.755 128.931 c +148.256 130.427 150 130.583 150.764 131.593 c +151.180 132 152.852 131.488 153.259 131.296 c +155.626 130.182 156.589 129.450 159 129.912 c +160.475 130.169 158.905 133.390 158.519 133.792 c +156.610 135.777 153.766 136.800 151 136.431 c +f +194 136.431 m +184.611 135.476 185 127 185.630 120 c +185.762 118.400 187.521 117.479 188 116.218 c +189.515 113.525 195.610 113.681 198 114 c +210.890 116.728 207.324 137.785 194 136.431 c +f +216 136.431 m +210.565 135.253 209 132.430 210 127.282 c +210.497 125.217 213.667 124.763 215 123.764 c +215.651 123.281 221 122 220 120 c +218.205 116.991 215.903 119.227 213.412 120.602 c +212.746 120.969 210.229 122.457 209.597 121 c +206.892 115.219 216.768 112.557 220.995 114.343 c +227.787 117.210 226.459 122.573 221.977 126.787 c +220.979 127.726 215.169 128 215.366 130 c +215.763 134.225 222.344 128.213 224.389 129.954 c +228.562 133.508 218.454 136.962 216 136.431 c +f +236 136.463 m +230.479 135 229.184 132.176 230.648 127 c +231.295 124.826 234.463 124.527 236 123.431 c +236.495 123 241.946 121.856 240.458 120 c +238 117.203 236.256 119 233.593 120.602 c +232.950 120.966 230.506 122.437 229.903 121 c +227 114.785 237.780 112.422 241.981 114.477 c +248.955 117.888 246.399 123.297 241.935 127 c +240.603 128.219 235.701 127.999 235.361 130.213 c +235.178 131.407 236.568 132 237.616 131.880 c +238.533 131.693 243 128.834 243.764 129.843 c +246.780 134 240.666 137.653 236 136.463 c +f +289 136.435 m +278 134.830 278.432 124.904 282.213 117 c +284 113.250 289 115.179 292 114 c +293 113.583 295.953 114.370 296.917 114.931 c +300.480 117 300.863 121.586 299 125 c +298.559 126.223 292.969 126.561 292.218 125.782 c +289.813 123.290 290.675 123.402 293.329 121.199 c +293.520 121 293.934 119.404 293.306 119.546 c +292.334 119.767 290.549 117.303 289 118.542 c +283.964 122.649 283 126.288 288 131 c +290 132.944 294 130 295.972 129.537 c +297.574 129 297.714 130.217 298.769 130.481 c +300 130.797 297 134.307 296.838 134.528 c +294.696 136 291.619 136.819 289 136.435 c +f +164.889 135 m +163.504 133.768 164 130.717 164 129 c +163.990 123.811 162.914 118 166 114.301 c +166.662 113.689 168.383 114.944 168.523 115.477 c +169.325 118.534 168.867 119.944 171.213 121.634 c +171.693 121.980 173.643 120 173.866 119.894 c +175.627 117.978 178.948 112.356 182.375 114.481 c +184.988 116 179.314 120.826 179.519 122.681 c +179.799 125.218 183.810 129.195 181.523 131.977 c +178 136.187 175.387 135.965 170 136 c +168.461 136 166 136.293 164.889 135 c +f +250.866 135 m +249.685 133.907 250 131.499 250 130 c +249.986 125.706 249.844 121.371 250 117 c +250 115.660 251.533 113.311 253 114.912 c +254.315 116 253.995 118.501 254 120 c +254 124.294 254 128.629 253.917 132.917 c +253.837 134.340 252.467 136.689 250.866 135 c +f +258.500 135.500 m +257.396 134.712 258 131 258 130 c +258 124.837 257.691 119.514 258.500 114.500 c +258.723 113 262 114.602 262.500 114.500 c +262.979 114.377 262.999 116.903 263 117 c +263 119.885 262.422 123.423 263.667 126 c +263.520 125.696 265.749 122.414 266 122 c +267.822 118.993 270.714 111.609 275.500 114.500 c +276.480 115 276 118 276 119 c +276 132 l +275.999 132.264 276 136.549 274.833 135.833 c +274.485 135.633 272.791 136.373 272.500 135.500 c +271.614 132.842 272 129.814 272 127 c +271.998 126.781 271.991 123.630 271 124 c +267.210 125.778 265.350 140.385 258.500 135.500 c +f +*U +0.000 0.000 0.000 0.000 k +*u +169.894 131 m +166.688 127.910 173.922 125.699 176 127.884 c +179.312 131 172 133.301 169.894 131 c +f +192.218 131 m +186.529 127 191 114 198.782 119.477 c +204.460 123.438 199.269 136 192.218 131 c +f +*U +%%Trailer +%%EOF diff --git a/8-geom2/8-geom2_1_usecky.eps b/8-geom2/8-geom2_1_usecky.eps new file mode 100644 index 0000000..4edc7e6 --- /dev/null +++ b/8-geom2/8-geom2_1_usecky.eps @@ -0,0 +1,124 @@ +%!PS +%%BoundingBox: -2 -39 116 45 +%%HiResBoundingBox: -1.99252 -38.843 115.37833 44.5122 +%%Creator: MetaPost 0.993 +%%CreationDate: 2009.12.16:0304 +%%Pages: 1 +%%BeginProlog +%%EndProlog +%%Page: 1 1 + 0 0 0 setrgbcolor +newpath 28.68358 9.44875 moveto +28.68358 10.37358 28.31613 11.2604 27.66223 11.91432 curveto +27.00832 12.56822 26.12149 12.93567 25.19666 12.93567 curveto +24.27182 12.93567 23.385 12.56822 22.73108 11.91432 curveto +22.07718 11.2604 21.70973 10.37358 21.70973 9.44875 curveto +21.70973 8.52391 22.07718 7.63708 22.73108 6.98317 curveto +23.385 6.32927 24.27182 5.96182 25.19666 5.96182 curveto +26.12149 5.96182 27.00832 6.32927 27.66223 6.98317 curveto +28.31613 7.63708 28.68358 8.52391 28.68358 9.44875 curveto closepath fill + 1 1 1 setrgbcolor +newpath 27.18918 9.44875 moveto +27.18918 9.97722 26.97922 10.48398 26.60556 10.85765 curveto +26.23189 11.23131 25.72513 11.44127 25.19666 11.44127 curveto +24.66818 11.44127 24.16142 11.23131 23.78775 10.85765 curveto +23.4141 10.48398 23.20413 9.97722 23.20413 9.44875 curveto +23.20413 8.92027 23.4141 8.41351 23.78775 8.03984 curveto +24.16142 7.66618 24.66818 7.45622 25.19666 7.45622 curveto +25.72513 7.45622 26.23189 7.66618 26.60556 8.03984 curveto +26.97922 8.41351 27.18918 8.92027 27.18918 9.44875 curveto closepath fill + 0 0 0 setrgbcolor 0 0.5 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinejoin 10 setmiterlimit +newpath 27.18918 9.44875 moveto +27.18918 9.97722 26.97922 10.48398 26.60556 10.85765 curveto +26.23189 11.23131 25.72513 11.44127 25.19666 11.44127 curveto +24.66818 11.44127 24.16142 11.23131 23.78775 10.85765 curveto +23.4141 10.48398 23.20413 9.97722 23.20413 9.44875 curveto +23.20413 8.92027 23.4141 8.41351 23.78775 8.03984 curveto +24.16142 7.66618 24.66818 7.45622 25.19666 7.45622 curveto +25.72513 7.45622 26.23189 7.66618 26.60556 8.03984 curveto +26.97922 8.41351 27.18918 8.92027 27.18918 9.44875 curveto closepath stroke +newpath 66.23433 23.53027 moveto +66.23433 24.45511 65.86688 25.34193 65.21298 25.99585 curveto +64.55907 26.64975 63.67224 27.0172 62.7474 27.0172 curveto +61.82257 27.0172 60.93575 26.64975 60.28183 25.99585 curveto +59.62793 25.34193 59.26048 24.45511 59.26048 23.53027 curveto +59.26048 22.60544 59.62793 21.71861 60.28183 21.0647 curveto +60.93575 20.4108 61.82257 20.04335 62.7474 20.04335 curveto +63.67224 20.04335 64.55907 20.4108 65.21298 21.0647 curveto +65.86688 21.71861 66.23433 22.60544 66.23433 23.53027 curveto closepath fill + 1 1 1 setrgbcolor +newpath 64.73993 23.53027 moveto +64.73993 24.05875 64.52997 24.5655 64.15631 24.93918 curveto +63.78264 25.31284 63.27588 25.5228 62.7474 25.5228 curveto +62.21893 25.5228 61.71217 25.31284 61.3385 24.93918 curveto +60.96484 24.5655 60.75488 24.05875 60.75488 23.53027 curveto +60.75488 23.0018 60.96484 22.49504 61.3385 22.12137 curveto +61.71217 21.74771 62.21893 21.53775 62.7474 21.53775 curveto +63.27588 21.53775 63.78264 21.74771 64.15631 22.12137 curveto +64.52997 22.49504 64.73993 23.0018 64.73993 23.53027 curveto closepath fill + 0 0 0 setrgbcolor +newpath 64.73993 23.53027 moveto +64.73993 24.05875 64.52997 24.5655 64.15631 24.93918 curveto +63.78264 25.31284 63.27588 25.5228 62.7474 25.5228 curveto +62.21893 25.5228 61.71217 25.31284 61.3385 24.93918 curveto +60.96484 24.5655 60.75488 24.05875 60.75488 23.53027 curveto +60.75488 23.0018 60.96484 22.49504 61.3385 22.12137 curveto +61.71217 21.74771 62.21893 21.53775 62.7474 21.53775 curveto +63.27588 21.53775 63.78264 21.74771 64.15631 22.12137 curveto +64.52997 22.49504 64.73993 23.0018 64.73993 23.53027 curveto closepath stroke +newpath 81.85646 -10.83827 moveto +81.85646 -9.91344 81.48901 -9.02661 80.83511 -8.3727 curveto +80.1812 -7.7188 79.29437 -7.35135 78.36954 -7.35135 curveto +77.4447 -7.35135 76.55788 -7.7188 75.90396 -8.3727 curveto +75.25006 -9.02661 74.88261 -9.91344 74.88261 -10.83827 curveto +74.88261 -11.7631 75.25006 -12.64993 75.90396 -13.30385 curveto +76.55788 -13.95775 77.4447 -14.3252 78.36954 -14.3252 curveto +79.29437 -14.3252 80.1812 -13.95775 80.83511 -13.30385 curveto +81.48901 -12.64993 81.85646 -11.7631 81.85646 -10.83827 curveto closepath fill + 1 1 1 setrgbcolor +newpath 80.36206 -10.83827 moveto +80.36206 -10.3098 80.1521 -9.80304 79.77844 -9.42937 curveto +79.40477 -9.05571 78.89801 -8.84575 78.36954 -8.84575 curveto +77.84106 -8.84575 77.3343 -9.05571 76.96063 -9.42937 curveto +76.58698 -9.80304 76.37701 -10.3098 76.37701 -10.83827 curveto +76.37701 -11.36674 76.58698 -11.8735 76.96063 -12.24718 curveto +77.3343 -12.62083 77.84106 -12.8308 78.36954 -12.8308 curveto +78.89801 -12.8308 79.40477 -12.62083 79.77844 -12.24718 curveto +80.1521 -11.8735 80.36206 -11.36674 80.36206 -10.83827 curveto closepath fill + 0 0 0 setrgbcolor +newpath 80.36206 -10.83827 moveto +80.36206 -10.3098 80.1521 -9.80304 79.77844 -9.42937 curveto +79.40477 -9.05571 78.89801 -8.84575 78.36954 -8.84575 curveto +77.84106 -8.84575 77.3343 -9.05571 76.96063 -9.42937 curveto +76.58698 -9.80304 76.37701 -10.3098 76.37701 -10.83827 curveto +76.37701 -11.36674 76.58698 -11.8735 76.96063 -12.24718 curveto +77.3343 -12.62083 77.84106 -12.8308 78.36954 -12.8308 curveto +78.89801 -12.8308 79.40477 -12.62083 79.77844 -12.24718 curveto +80.1521 -11.8735 80.36206 -11.36674 80.36206 -10.83827 curveto closepath stroke + 0 3.98505 dtransform truncate idtransform setlinewidth pop 1 setlinecap +newpath 0 0 moveto 0 0 rlineto stroke +newpath 113.3858 42.51968 moveto 0 0 rlineto stroke + 0 0.5 dtransform truncate idtransform setlinewidth pop +newpath 0 0 moveto +113.3858 42.51968 lineto stroke + 0 3.98505 dtransform truncate idtransform setlinewidth pop +newpath 14.17323 42.51968 moveto 0 0 rlineto stroke +newpath 28.34645 0 moveto 0 0 rlineto stroke + 0 0.5 dtransform truncate idtransform setlinewidth pop +newpath 14.17323 42.51968 moveto +28.34645 0 lineto stroke + 0 3.98505 dtransform truncate idtransform setlinewidth pop +newpath 56.6929 36.85048 moveto 0 0 rlineto stroke +newpath 85.03935 -25.51163 moveto 0 0 rlineto stroke + 0 0.5 dtransform truncate idtransform setlinewidth pop +newpath 56.6929 36.85048 moveto +85.03935 -25.51163 lineto stroke + 0 3.98505 dtransform truncate idtransform setlinewidth pop +newpath 28.34645 -36.85048 moveto 0 0 rlineto stroke +newpath 99.21259 0 moveto 0 0 rlineto stroke + 0 0.5 dtransform truncate idtransform setlinewidth pop +newpath 28.34645 -36.85048 moveto +99.21259 0 lineto stroke +showpage +%%EOF diff --git a/8-geom2/8-geom2_2_polorovina.eps b/8-geom2/8-geom2_2_polorovina.eps new file mode 100644 index 0000000..eae45e7 --- /dev/null +++ b/8-geom2/8-geom2_2_polorovina.eps @@ -0,0 +1,70 @@ +%!PS +%%BoundingBox: -39 -86 55 90 +%%HiResBoundingBox: -38.45198 -85.83585 54.56447 89.41768 +%%Creator: MetaPost 0.993 +%%CreationDate: 2009.12.16:0304 +%%Pages: 1 +%*Font: cmmi10 9.96265 9.96265 61:c +%%BeginProlog +%%EndProlog +%%Page: 1 1 + 0.8 0.8 0.8 setrgbcolor +newpath 0.09926 88.67047 moveto +48.08961 -74.49722 lineto +9.53838 -85.83585 lineto +-38.45198 77.33185 lineto + closepath fill + 0 0 0 setrgbcolor 0 1.4944 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit +newpath 0.09926 88.67047 moveto +48.08961 -74.49722 lineto stroke + 0 0.5 dtransform truncate idtransform setlinewidth pop + [3 3 ] 0 setdash +newpath 0 0 moveto +48.18887 14.17323 lineto stroke + 1 1 1 setrgbcolor +newpath 1.99252 0 moveto +1.99252 0.52847 1.78256 1.03523 1.4089 1.4089 curveto +1.03523 1.78256 0.52847 1.99252 0 1.99252 curveto +-0.52847 1.99252 -1.03523 1.78256 -1.4089 1.4089 curveto +-1.78256 1.03523 -1.99252 0.52847 -1.99252 0 curveto +-1.99252 -0.52847 -1.78256 -1.03523 -1.4089 -1.4089 curveto +-1.03523 -1.78256 -0.52847 -1.99252 0 -1.99252 curveto +0.52847 -1.99252 1.03523 -1.78256 1.4089 -1.4089 curveto +1.78256 -1.03523 1.99252 -0.52847 1.99252 0 curveto closepath fill + 0 0 0 setrgbcolor [] 0 setdash +newpath 1.99252 0 moveto +1.99252 0.52847 1.78256 1.03523 1.4089 1.4089 curveto +1.03523 1.78256 0.52847 1.99252 0 1.99252 curveto +-0.52847 1.99252 -1.03523 1.78256 -1.4089 1.4089 curveto +-1.78256 1.03523 -1.99252 0.52847 -1.99252 0 curveto +-1.99252 -0.52847 -1.78256 -1.03523 -1.4089 -1.4089 curveto +-1.03523 -1.78256 -0.52847 -1.99252 0 -1.99252 curveto +0.52847 -1.99252 1.03523 -1.78256 1.4089 -1.4089 curveto +1.78256 -1.03523 1.99252 -0.52847 1.99252 0 curveto closepath stroke + 1 1 1 setrgbcolor +newpath 50.1814 14.17323 moveto +50.1814 14.7017 49.97144 15.20847 49.59778 15.58214 curveto +49.2241 15.9558 48.71735 16.16576 48.18887 16.16576 curveto +47.6604 16.16576 47.15364 15.9558 46.77997 15.58214 curveto +46.40631 15.20847 46.19635 14.7017 46.19635 14.17323 curveto +46.19635 13.64476 46.40631 13.138 46.77997 12.76433 curveto +47.15364 12.39067 47.6604 12.18071 48.18887 12.18071 curveto +48.71735 12.18071 49.2241 12.39067 49.59778 12.76433 curveto +49.97144 13.138 50.1814 13.64476 50.1814 14.17323 curveto closepath fill + 0 0 0 setrgbcolor +newpath 50.1814 14.17323 moveto +50.1814 14.7017 49.97144 15.20847 49.59778 15.58214 curveto +49.2241 15.9558 48.71735 16.16576 48.18887 16.16576 curveto +47.6604 16.16576 47.15364 15.9558 46.77997 15.58214 curveto +46.40631 15.20847 46.19635 14.7017 46.19635 14.17323 curveto +46.19635 13.64476 46.40631 13.138 46.77997 12.76433 curveto +47.15364 12.39067 47.6604 12.18071 48.18887 12.18071 curveto +48.71735 12.18071 49.2241 12.39067 49.59778 12.76433 curveto +49.97144 13.138 50.1814 13.64476 50.1814 14.17323 curveto closepath stroke +-7.36609 -6.3895 moveto +(a) cmmi10 9.96265 fshow +50.28886 16.27322 moveto +(b) cmmi10 9.96265 fshow +showpage +%%EOF diff --git a/8-geom2/8-geom2_3_voroneho_diagram.eps b/8-geom2/8-geom2_3_voroneho_diagram.eps new file mode 100644 index 0000000..d32083e --- /dev/null +++ b/8-geom2/8-geom2_3_voroneho_diagram.eps @@ -0,0 +1,203 @@ +%!PS +%%BoundingBox: -82 -96 91 107 +%%HiResBoundingBox: -81.19815 -95.708 90.92032 106.73361 +%%Creator: MetaPost 0.993 +%%CreationDate: 2009.12.16:0304 +%%Pages: 1 +%%BeginProlog +%%EndProlog +%%Page: 1 1 + 0 0 0 setrgbcolor 0 1.4944 dtransform truncate idtransform setlinewidth pop + [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit +newpath 5.74025 -94.96078 moveto +5.74025 -44.00813 lineto +-39.01674 0.74886 lineto +-80.45094 -5.46661 lineto stroke +newpath -39.01674 0.74886 moveto +-13.44022 33.99786 lineto +-12.65121 41.49461 lineto +-50.21571 104.10237 lineto stroke +newpath -12.65121 41.49461 moveto +43.8882 62.05504 lineto +84.44029 105.9864 lineto stroke +newpath 43.8882 62.05504 moveto +36.59952 -3.53217 lineto +-13.44022 33.99786 lineto stroke +newpath 36.59952 -3.53217 moveto +36.70383 -3.7555 lineto +90.17311 -10.04572 lineto stroke +newpath 36.70383 -3.7555 moveto +5.74025 -44.00813 lineto stroke + 0 0.5 dtransform truncate idtransform setlinewidth pop + [3 3 ] 0 setdash +newpath 0 0 moveto +-38.26788 -38.26788 lineto +49.74837 -38.26788 lineto +0 0 lineto +-49.74837 38.26788 lineto +-38.26788 -38.26788 lineto stroke +newpath -49.74837 38.26788 moveto +7.65346 72.70874 lineto +22.96097 30.61443 lineto +0 0 lineto +57.40182 26.7874 lineto +49.74837 -38.26788 lineto stroke +newpath 57.40182 26.7874 moveto +7.65346 72.70874 lineto stroke +newpath -49.74837 38.26788 moveto +22.96097 30.61443 lineto +57.40182 26.7874 lineto stroke + 0 3.98505 dtransform truncate idtransform setlinewidth pop [] 0 setdash +newpath 5.74025 -44.00813 moveto 0 0 rlineto stroke +newpath -39.01674 0.74886 moveto 0 0 rlineto stroke +newpath -13.44022 33.99786 moveto 0 0 rlineto stroke +newpath -12.65121 41.49461 moveto 0 0 rlineto stroke +newpath 43.8882 62.05504 moveto 0 0 rlineto stroke +newpath 36.59952 -3.53217 moveto 0 0 rlineto stroke +newpath 36.70383 -3.7555 moveto 0 0 rlineto stroke + 1 1 1 setrgbcolor +newpath 1.99252 0 moveto +1.99252 0.52847 1.78256 1.03523 1.4089 1.4089 curveto +1.03523 1.78256 0.52847 1.99252 0 1.99252 curveto +-0.52847 1.99252 -1.03523 1.78256 -1.4089 1.4089 curveto +-1.78256 1.03523 -1.99252 0.52847 -1.99252 0 curveto +-1.99252 -0.52847 -1.78256 -1.03523 -1.4089 -1.4089 curveto +-1.03523 -1.78256 -0.52847 -1.99252 0 -1.99252 curveto +0.52847 -1.99252 1.03523 -1.78256 1.4089 -1.4089 curveto +1.78256 -1.03523 1.99252 -0.52847 1.99252 0 curveto closepath fill + 0 0 0 setrgbcolor 0 0.5 dtransform truncate idtransform setlinewidth pop +newpath 1.99252 0 moveto +1.99252 0.52847 1.78256 1.03523 1.4089 1.4089 curveto +1.03523 1.78256 0.52847 1.99252 0 1.99252 curveto +-0.52847 1.99252 -1.03523 1.78256 -1.4089 1.4089 curveto +-1.78256 1.03523 -1.99252 0.52847 -1.99252 0 curveto +-1.99252 -0.52847 -1.78256 -1.03523 -1.4089 -1.4089 curveto +-1.03523 -1.78256 -0.52847 -1.99252 0 -1.99252 curveto +0.52847 -1.99252 1.03523 -1.78256 1.4089 -1.4089 curveto +1.78256 -1.03523 1.99252 -0.52847 1.99252 0 curveto closepath stroke + 1 1 1 setrgbcolor +newpath -36.27536 -38.26788 moveto +-36.27536 -37.73941 -36.48532 -37.23265 -36.85898 -36.85898 curveto +-37.23265 -36.48532 -37.73941 -36.27536 -38.26788 -36.27536 curveto +-38.79636 -36.27536 -39.30312 -36.48532 -39.67679 -36.85898 curveto +-40.05045 -37.23265 -40.2604 -37.73941 -40.2604 -38.26788 curveto +-40.2604 -38.79636 -40.05045 -39.30312 -39.67679 -39.67679 curveto +-39.30312 -40.05045 -38.79636 -40.2604 -38.26788 -40.2604 curveto +-37.73941 -40.2604 -37.23265 -40.05045 -36.85898 -39.67679 curveto +-36.48532 -39.30312 -36.27536 -38.79636 -36.27536 -38.26788 curveto closepath + fill + 0 0 0 setrgbcolor +newpath -36.27536 -38.26788 moveto +-36.27536 -37.73941 -36.48532 -37.23265 -36.85898 -36.85898 curveto +-37.23265 -36.48532 -37.73941 -36.27536 -38.26788 -36.27536 curveto +-38.79636 -36.27536 -39.30312 -36.48532 -39.67679 -36.85898 curveto +-40.05045 -37.23265 -40.2604 -37.73941 -40.2604 -38.26788 curveto +-40.2604 -38.79636 -40.05045 -39.30312 -39.67679 -39.67679 curveto +-39.30312 -40.05045 -38.79636 -40.2604 -38.26788 -40.2604 curveto +-37.73941 -40.2604 -37.23265 -40.05045 -36.85898 -39.67679 curveto +-36.48532 -39.30312 -36.27536 -38.79636 -36.27536 -38.26788 curveto closepath + stroke + 1 1 1 setrgbcolor +newpath 51.74089 -38.26788 moveto +51.74089 -37.73941 51.53093 -37.23265 51.15727 -36.85898 curveto +50.7836 -36.48532 50.27684 -36.27536 49.74837 -36.27536 curveto +49.2199 -36.27536 48.71313 -36.48532 48.33946 -36.85898 curveto +47.9658 -37.23265 47.75584 -37.73941 47.75584 -38.26788 curveto +47.75584 -38.79636 47.9658 -39.30312 48.33946 -39.67679 curveto +48.71313 -40.05045 49.2199 -40.2604 49.74837 -40.2604 curveto +50.27684 -40.2604 50.7836 -40.05045 51.15727 -39.67679 curveto +51.53093 -39.30312 51.74089 -38.79636 51.74089 -38.26788 curveto closepath fill + 0 0 0 setrgbcolor +newpath 51.74089 -38.26788 moveto +51.74089 -37.73941 51.53093 -37.23265 51.15727 -36.85898 curveto +50.7836 -36.48532 50.27684 -36.27536 49.74837 -36.27536 curveto +49.2199 -36.27536 48.71313 -36.48532 48.33946 -36.85898 curveto +47.9658 -37.23265 47.75584 -37.73941 47.75584 -38.26788 curveto +47.75584 -38.79636 47.9658 -39.30312 48.33946 -39.67679 curveto +48.71313 -40.05045 49.2199 -40.2604 49.74837 -40.2604 curveto +50.27684 -40.2604 50.7836 -40.05045 51.15727 -39.67679 curveto +51.53093 -39.30312 51.74089 -38.79636 51.74089 -38.26788 curveto closepath + stroke + 1 1 1 setrgbcolor +newpath 59.39435 26.7874 moveto +59.39435 27.31587 59.18439 27.82263 58.81073 28.1963 curveto +58.43706 28.56996 57.9303 28.77992 57.40182 28.77992 curveto +56.87335 28.77992 56.3666 28.56996 55.99292 28.1963 curveto +55.61926 27.82263 55.4093 27.31587 55.4093 26.7874 curveto +55.4093 26.25893 55.61926 25.75217 55.99292 25.3785 curveto +56.3666 25.00484 56.87335 24.79488 57.40182 24.79488 curveto +57.9303 24.79488 58.43706 25.00484 58.81073 25.3785 curveto +59.18439 25.75217 59.39435 26.25893 59.39435 26.7874 curveto closepath fill + 0 0 0 setrgbcolor +newpath 59.39435 26.7874 moveto +59.39435 27.31587 59.18439 27.82263 58.81073 28.1963 curveto +58.43706 28.56996 57.9303 28.77992 57.40182 28.77992 curveto +56.87335 28.77992 56.3666 28.56996 55.99292 28.1963 curveto +55.61926 27.82263 55.4093 27.31587 55.4093 26.7874 curveto +55.4093 26.25893 55.61926 25.75217 55.99292 25.3785 curveto +56.3666 25.00484 56.87335 24.79488 57.40182 24.79488 curveto +57.9303 24.79488 58.43706 25.00484 58.81073 25.3785 curveto +59.18439 25.75217 59.39435 26.25893 59.39435 26.7874 curveto closepath stroke + 1 1 1 setrgbcolor +newpath 24.95349 30.61443 moveto +24.95349 31.1429 24.74353 31.64966 24.36987 32.02333 curveto +23.9962 32.39699 23.48944 32.60695 22.96097 32.60695 curveto +22.4325 32.60695 21.92574 32.39699 21.55206 32.02333 curveto +21.1784 31.64966 20.96844 31.1429 20.96844 30.61443 curveto +20.96844 30.08595 21.1784 29.5792 21.55206 29.20552 curveto +21.92574 28.83186 22.4325 28.6219 22.96097 28.6219 curveto +23.48944 28.6219 23.9962 28.83186 24.36987 29.20552 curveto +24.74353 29.5792 24.95349 30.08595 24.95349 30.61443 curveto closepath fill + 0 0 0 setrgbcolor +newpath 24.95349 30.61443 moveto +24.95349 31.1429 24.74353 31.64966 24.36987 32.02333 curveto +23.9962 32.39699 23.48944 32.60695 22.96097 32.60695 curveto +22.4325 32.60695 21.92574 32.39699 21.55206 32.02333 curveto +21.1784 31.64966 20.96844 31.1429 20.96844 30.61443 curveto +20.96844 30.08595 21.1784 29.5792 21.55206 29.20552 curveto +21.92574 28.83186 22.4325 28.6219 22.96097 28.6219 curveto +23.48944 28.6219 23.9962 28.83186 24.36987 29.20552 curveto +24.74353 29.5792 24.95349 30.08595 24.95349 30.61443 curveto closepath stroke + 1 1 1 setrgbcolor +newpath 9.64598 72.70874 moveto +9.64598 73.23721 9.43602 73.74397 9.06236 74.11765 curveto +8.68869 74.4913 8.18193 74.70126 7.65346 74.70126 curveto +7.12498 74.70126 6.61823 74.4913 6.24455 74.11765 curveto +5.8709 73.74397 5.66093 73.23721 5.66093 72.70874 curveto +5.66093 72.18027 5.8709 71.67351 6.24455 71.29984 curveto +6.61823 70.92618 7.12498 70.71622 7.65346 70.71622 curveto +8.18193 70.71622 8.68869 70.92618 9.06236 71.29984 curveto +9.43602 71.67351 9.64598 72.18027 9.64598 72.70874 curveto closepath fill + 0 0 0 setrgbcolor +newpath 9.64598 72.70874 moveto +9.64598 73.23721 9.43602 73.74397 9.06236 74.11765 curveto +8.68869 74.4913 8.18193 74.70126 7.65346 74.70126 curveto +7.12498 74.70126 6.61823 74.4913 6.24455 74.11765 curveto +5.8709 73.74397 5.66093 73.23721 5.66093 72.70874 curveto +5.66093 72.18027 5.8709 71.67351 6.24455 71.29984 curveto +6.61823 70.92618 7.12498 70.71622 7.65346 70.71622 curveto +8.18193 70.71622 8.68869 70.92618 9.06236 71.29984 curveto +9.43602 71.67351 9.64598 72.18027 9.64598 72.70874 curveto closepath stroke + 1 1 1 setrgbcolor +newpath -47.75584 38.26788 moveto +-47.75584 38.79636 -47.9658 39.30312 -48.33946 39.67679 curveto +-48.71313 40.05045 -49.2199 40.2604 -49.74837 40.2604 curveto +-50.27684 40.2604 -50.7836 40.05045 -51.15727 39.67679 curveto +-51.53093 39.30312 -51.74089 38.79636 -51.74089 38.26788 curveto +-51.74089 37.73941 -51.53093 37.23265 -51.15727 36.85898 curveto +-50.7836 36.48532 -50.27684 36.27536 -49.74837 36.27536 curveto +-49.2199 36.27536 -48.71313 36.48532 -48.33946 36.85898 curveto +-47.9658 37.23265 -47.75584 37.73941 -47.75584 38.26788 curveto closepath fill + 0 0 0 setrgbcolor +newpath -47.75584 38.26788 moveto +-47.75584 38.79636 -47.9658 39.30312 -48.33946 39.67679 curveto +-48.71313 40.05045 -49.2199 40.2604 -49.74837 40.2604 curveto +-50.27684 40.2604 -50.7836 40.05045 -51.15727 39.67679 curveto +-51.53093 39.30312 -51.74089 38.79636 -51.74089 38.26788 curveto +-51.74089 37.73941 -51.53093 37.23265 -51.15727 36.85898 curveto +-50.7836 36.48532 -50.27684 36.27536 -49.74837 36.27536 curveto +-49.2199 36.27536 -48.71313 36.48532 -48.33946 36.85898 curveto +-47.9658 37.23265 -47.75584 37.73941 -47.75584 38.26788 curveto closepath + stroke +showpage +%%EOF diff --git a/8-geom2/Makefile b/8-geom2/Makefile new file mode 100644 index 0000000..087c424 --- /dev/null +++ b/8-geom2/Makefile @@ -0,0 +1,3 @@ +P=8-geom2 + +include ../Makerules diff --git a/8-geom2/lib.mp b/8-geom2/lib.mp new file mode 100644 index 0000000..2536305 --- /dev/null +++ b/8-geom2/lib.mp @@ -0,0 +1,82 @@ +% implementation of figure naming and figure transparency +string name,tag; name := ""; tag := ""; +def updatefigname = + if tag="": filenametemplate (name & "%c.eps"); + else: filenametemplate (name & "%c_" & tag & ".eps"); + fi; +enddef; + +def figname(expr n) = name := n; updatefigname; enddef; +def figtag(expr t) = tag := t; updatefigname; enddef; + +picture transparent_picture; +color transparent_color; transparent_color := 0.9white; +def drawtransparent(expr num) = + transparent_picture := currentpicture; +endfig; + +if tag="": filenametemplate (name & "%c_transparent.eps"); +else: filenametemplate (name & "%c_" & tag & "_transparent.eps"); +fi; +beginfig(num); + draw transparent_picture withcolor transparent_color; +endfig; + +updatefigname; +enddef; + +def from(expr p,d,len) = + p+dir(d)*len +enddef; + +def dirs(expr p,d,len) = + p--from(p,d,len) +enddef; + +def drawvertices(expr s,n) = + for i:=s upto n: + draw vertex(PQ[i]); + endfor +enddef; + +def drawfvertices(expr s,n,flags) = + for i:=s upto n: + draw vertex(PQ[i]) flags; + endfor +enddef; + +def vertex(expr p) = p withpen pencircle scaled 4pt enddef; +def drawemptyvertex(expr p) = unfill fullcircle scaled 4pt shifted p; draw fullcircle scaled 4pt shifted p; enddef; +def drawendpointvertex(expr p) = draw vertex(p) withcolor red; draw fullcircle scaled 6pt shifted p; enddef; +def createpath(expr p) = shakepath(p, 0.015cm,0.1cm) enddef; +vardef shakepath(expr p,d,l) = + save r,b; + path r; r := point(arctime 0 of p) of p; + b := -1; + for i:=l step l until arclength(p): + r := r--(point(arctime i of p) of p)+dir(angle(direction(arctime i of p) of p rotated 90))*d*b; + b := -b; + endfor + r--point(arctime arclength(p) of p) of p +enddef; + +pen normalpen; normalpen := pencircle scaled 0.6pt; +pen boldpen; boldpen := pencircle scaled 1.5pt; +pen bolderpen; bolderpen := pencircle scaled 2pt; +def dotline = withdots scaled 0.82 withpen boldpen enddef; + +vardef unclosedbubblec(expr p,c) = + bubblec((p..reverse p..cycle),c) +enddef; + +vardef bubblec(expr p,c) = + save r; + path r; r := (point(arctime 0 of p) of p)+dir(angle(direction(arctime 0 of p) of p rotated 90))*c; + for i:=0.01cm step 0.025cm until arclength(p): + r := r..(point(arctime i of p) of p)+dir(angle(direction(arctime i of p) of p rotated 90))*c; + endfor + r..(point(arctime arclength(p) of p) of p)+dir(angle(direction(arctime arclength(p) of p) of p rotated 90))*c..cycle +enddef; + +vardef bubble(expr p) = bubblec(p,0.12cm) enddef; +vardef unclosedbubble(expr p) = unclosedbubblec(p,0.12cm) enddef; -- 2.39.2