# GGB 碎形製作 --- ## 二元樹 Binary Tree ---- ### 定義 二元樹是每個節點最多只有兩個分支的樹狀結構 分支具有左右次序，不能隨意顛倒 二元樹的第 \\(i\\) 層至多擁有 \\(2^{i-1}\\) 個節點 深度為k的二元樹至多總共有 \\(2^{k+1}-1\\) 個節點 ---- 二元樹是圖論中"樹"的特例 樹: 一種無向圖，任一兩點間存在一條簡單路徑 ---- 而本次製作的是完全二元樹 即: 除了最後一層外 每個節點的子節點一定是兩個 ---- ### Outline * 做出初始線段 * 線段集 * 工具 * 迭代 ---- 首先做出任意兩點 A, B 以及 5 個滑桿: * n - 迭代次數 * r1, r2 - 左右線段比例 * a, b - 左右角度 ----  ----  ----  請特別注意那個"度" ----  做完應該長這樣 ---- 接下來我們開始下幾個指令: ```cpp= u = Vector(A, B) B1 = Translate(B, u) B2 = Dilate(B1, r1, B) B3 = Rotate(B2, alpha, B) B4 = Dilate(B1, r2, B) B5 = Rotate(B4, -beta, B) //特別注意中間那個"-beta" ``` 這些是什麼意思? ---- * Vector 產生起點至終點的向量 * Translate 由起點位置往向量方向延伸做新點 * Dilate 將輸入的向量伸縮 * Rotate 將物件旋轉 ```cpp= // 各參數意義 Vector( <Start Point>, <End Point> ) Translate( <Vector>, <Start Point> ) Dilate( <Object>, <Dilation Factor>, <Dilation Center Point> ) Rotate( <Object>, <Angle>, <Point> ) ``` ---- 最後我們把這些東西作成線段並存成串列 ```cpp= list1 = {Segment(B, B3), Segment(B, B5)} // Segment[ <Point>, <Point> ] ``` 然後把 B1 到 B5 隱藏起來 ----  ----  接下來要自訂工具 ---- 輸出:  ---- 輸入:  ----  ---- 來測試一下:D 新增隨意點 C、 D 然後輸入指令: ```cpp= branch(C, D, a, b, r1, r2) ```  ---- 接下來我們要一步步做出最終的式子:D ```cpp= IterationList(Flatten(Sequence(branch(Vertex(Element(list1,i),1),Vertex(Element(list1,i),2),a,b,r1,r2),i, 1,Length(list1))),list1,{{Segment(A,B)}},n) ``` 怕豹 所以先準備這條:D ```cpp= branch(Vertex(Element(list1,i),1),Vertex(Element(list1,i),2),a,b,r1,r2) ``` 什麼意思? ---- * Vertex - 將線段中的點取出 * Element - 將串列中的元素取出 ```cpp= Vertex( <Segment>, <Index> ) Element( <List>, <Position of Element n> ) ``` 所以剛剛那條是 "將 list1 中的第 i 個線段取出，並得到那兩個點" **再拿那兩個點做新線** 可是 GGB 不認識 "i" 是誰ㄚ ---- 所以要來實現一個"迴圈"的功能 加上"Sequence"! ```cpp= Sequence( <Expression>, <Variable k>, <Start Value a>, <End Value b> ) ``` 把這個套上剛剛的那式就變成: ```cpp= Sequence(branch(Vertex(Element(list1,i),1),Vertex(Element(list1,i),2),a,b,r1,r2),i,1,Length(list1)) ``` 最後把產生的串列攤平: ```cpp= Flatten(Sequence(branch(Vertex(Element(list1,i),1),Vertex(Element(list1,i),2),a,b,r1,r2),i,1,Length(list1))) ``` ---- 今天的主角: IterationList ``` IterationList( <Expression>, <Variable Name>, ..., <Start Values>, <Number of Iterations> ) ``` 我們以 list1 作為迭代物件，點 A、B 作為初始值 ```cpp= IterationList( <Expression>, list1, {{Segment(A,B)}},n) ``` ---- 再把上面那一長串指令帶入 expression: ```cpp= IterationList(Flatten(Sequence(branch(Vertex(Element(list1,i),1),Vertex(Element(list1,i),2),a,b,r1,r2),i,1,Length(list1))), list1, {{Segment(A,B)}},n) ``` 就大功告成啦:D ----  :D --- ## 謝爾賓斯基三角形 Sierpinsky Triangle ---- ### 何謂謝爾賓斯基三角形 ？ ---- #### 構作（方法） - 去掉中心 - Chaos Game - L系統(接近謝爾賓斯基三角形) ---- #### 1.去掉中心 1. 取一實心三角形。（多數使用等邊三角形） 2. 沿三邊中點連線，將之分成四個小三角形。 3. 去掉中間的那一個小三角形。 4. 對其餘三個小三角形重複1。 > 取一正方形或其他形狀開始，用類似方法，形狀也會和謝爾賓斯基三角形相近 >  ---- #### 2.用隨機的方法（Chaos Game） 1. 任意取平面上三點A,B,C，組成一三角形 2. 任意取三角形ABC內的一點P，畫出 該點 3. 畫出 P和三角形其中一個頂點的中點 4. 重複1 ---- #### 3.L系統 - 這條曲線以L系統來記述為： - 變數: A , B - 常數: + , - (+為右轉60° -為 左轉60°) - 公理: A - 規則:1. (A → B-A-B) 2.(B → A+B+A) 3.(A,B：向前)  ---- ## 開始做謝爾賓斯基三角形吧！ ---- ### Outline * 三角形 * 往內縮放 * 迭代 ---- 首先做出任意兩點 A、B 並使用 polygon() 函數做出正三角形 ```cpp= poly1 = Polygon(A, B, 3) // 後面的 3 代表三邊的正多邊形 ``` ----  ---- * Vertex - 將線段中的點取出 * Dilate 將輸入的向量伸縮 * Zip(): 將 expression 內的變數以 list 內的替換 ```cpp= // 各參數意義 Vertex( <Segment>, <Index> ) Dilate( <Object>, <Dilation Factor>, <Dilation Center Point> ) Zip( <Expression>, <Var1>, <List1>, <Var2>, <List2>, ...) e.g.: Dilate(poly1,0.5,O) // 以 0.5 倍縮放 poly1 ``` ---- 接下來使用剛剛有提到的 Dilate() 來縮放三角形 並使用 Zip() 各對三頂點縮放 ```cpp= Zip(Dilate(poly1,0.5,O),O,{Vertex(poly1)}) // 將 {vertex(poly1)} 中的點代進 O ``` ----  ---- 接下來就可以來迭代啦 下一種迭代技巧: Iteration() * Iteration: 將上一層得出的結果輸入到下一層中 ```cpp= Iteration( <Expression>, <Variable Name>, ..., <Start Values>, <Number of Iterations> ) ``` ----  ---- ```cpp= Iteration(Join(Zip(Zip(Dilate(poly1,0.5,O),O,{Vertex(poly1)}),poly1,p1)),p1,{{Polygon(A,B,3)}},n) ``` 1. 以 {{Polygon(A, B, 3)}} 作為初值 2. 用 Zip() 將大括號內的串列取出 3. 放入 expression ----  --- ## 科赫雪花 Koch Snowflake ---- ### 何謂科赫雪花(Koch Snowflake)？ ---- #### 科赫雪花的定義(作法) 1. 任取兩點 A、B，連成一條線段。 2. 以線段 AB 為底邊，做出一個**正三角形** ABC。 3. 以此正三角形 ABC 三邊分為**三等分**，以每一邊的**中間**那等分為底邊，向外做出正三角形，並**去除**正三角形 ABC 的邊。 4. 如此反覆，所產生的圖形與雪花相似，因此稱為科赫"雪花"。 ---- #### 科赫雪花的邊長&周長 假設正三角形 ABC 的邊長為 \\(a\\)，周長為 \\(3a\\) 那麼迭代一次後的圖形(十二邊形)邊長為 **\\(a \over 3\\)** 周長為 \\(4a\\)，**為原本圖形的 \\(4 \over 3\\) 倍** 。 ---- ## 開始作科赫雪花吧！ ---- ### Outline * 任取兩點 * 自訂工具 * 迴圈 * 限制條件 ---- ### Step 1 ## 自訂工具 ---- 首先任取兩點 A, B 然後使用 Dilate() 進行向量伸縮 Rotate() 進行旋轉 ```cpp= C = Dilate(B, 1 / 3, A) //對向量 AB 縮為原本的 1/3 倍。 D = Dilate(B, 2 / 3, A) E = Rotate(D, 60°, C) //以點 C 為旋轉中心，對點 D 逆時針旋轉 60 度。 ``` ---- 輸入好後，圖形長這樣。  ---- 然後輸入: ```cpp= {A, C, E, D, B} ``` 把點通通輸進一個串列裡。 ---- 接著，自訂工具。  ---- 輸出物件：剛剛新建的串列 \\(list1\\)  ---- 輸入：A、B 兩點  ---- 工具名稱：koch  ---- 完成後，把它們通通隱藏。 ---- Step 1 完成囉！ ---- ### Step 2 ## 使用 koch() 輸出科赫雪花圖形 ---- 任取兩點 F, G，然後輸入： ```cpp= H = rotate(F, 60°, G) A1 = {F, H, G} B1 = Polyline(F, H, G, F) //做出線段 FH, HG, GF。 A2 = koch(F, H) ``` ---- 此時的圖形長這樣。  ---- **常見錯誤示範** 若輸出的圖形長這樣(新三角形跑到裡面了) 那麼請把 A2 = koch(F, H) 指令中的兩點順序**交換**。  ---- 然後輸入： ```cpp= A3 = Join(Sequence(koch(Element(A2,i),Element(A2,i+1)),i,1,Length(A2)-1)) ``` ---- #### 為什麼指令要這樣寫呢？ ---- 我們層層往內推進 ```cpp= Join() -> 把輸出的元素合成成一個串列。 Sequence( <運算式>, <變數名>, <起始值>, <結束值>, <遞增值(沒寫=1)> ) Element( <list1>, i) -> 將串列中的第 i 個元素取出。 ``` ---- A3 輸入完後，圖形長這樣。  ---- 接著，進入試算表。  ---- 選取 A3 儲存格 把儲存格下拉拖曳到 A6 (A7 以後程式可能當機) 完成請先**存檔** 否則可能會發生 GGB 當機的慘劇。  ---- 選取 A1~A6 儲存格 並按右鍵點擊 屬性 -> 一般 把｢顯示物件」關掉。  ---- 接著，輸入： ```cpp= B2 = Polyline(A2) //把 A2 輸出的那些點連成線段。 ``` 完成後一樣到試算表中，下拉 B2 儲存格到 B6。 ---- 然後再用與剛剛 A2~A6, B2~B6 相同方法把 A12~A16, B12~B16(線段 HG) A22~A26, B22~B26(線段 GF) 做出來吧！ ```cpp= A12 = koch(H, G) A13 = Join(Sequence(koch(Element(A12,i),Element(A12,i+1)),i,1,Length(A12-1))) B12 = Polyline(A12) A22 = koch(G, F) A23 = Join(Sequence(koch(Element(A22,i),Element(A22,i+1)),i,1,Length(A22-1))) B22 = Polyline(A22) ``` ---- 最後，把所有物件通通隱藏起來 並新增一個滑杆，參數如圖所示。  ---- 點選儲存格->屬性->進階 - 把 B1 顯示物件的條件設為 n = 1 - 把 B2, B12, B22 顯示物件的條件設為 n = 2 - 把 B3, B13, B23 顯示物件的條件設為 n = 3 - 以此類推 ---- 回到繪圖區，拖動滑杆，如果可以輸出這樣的圖形，那麼 Step 2 就完成啦！  ---- ### Step 3 ## 使用遞迴關係式算出科赫雪花周長 & 邊長 ---- 科赫雪花每多一層，周長會變原本的 \\(4 \over 3\\)倍，下列為計算**周長**的方法： ```cpp= a = distance(F, H) f1(a) = 4/3*a 然後把f1(a)點隱藏 f2 = iteration(f1, 3a, n-1) text1 = "周長="+f2+"" ``` ---- 科赫雪花每多一層，邊長會變原本的 \\(1 \over 3\\)倍，下列為計算**邊長**的方法： ```cpp= f3(a) = 1/3*a 然後把f3(a)點隱藏 f4 = iteration(f3, a, n-1) text2 = "邊長="+f4+"" ``` ---- 完成後像是這樣，就大功告成囉！  --- ## 謝爾賓斯基地毯 Sierpinski carpet ---- ### 何謂謝爾賓斯基地毯 ？ ---- #### 定義 將一實心正方形劃分為 \\(3 \times 3\\) 的 \\(9\\) 個小正方形 去掉中間的小正方形，再對餘下的小正方形重複此操作。 ---- ## 開始做謝爾賓斯基地毯吧！ ---- ### Outline - 作正方形 OABC - 滑桿 - 迴圈 ---- ### Step 1 ### 以 OA 為邊作正方形 OABC ---- 設點OA ```python= O=(0,0) A=(27,0) ``` ---- 以 OA 為邊作正方形 OABC 並作出內部的正方形 ```python= O=(0,0) A=(27,0) poly1= Polygon(O, A, 4) //以 OA 為邊作正方形 OABC poly2=Polygon(Dilate(O,((2)/(3)),B),Dilate(A,((2)/(3)),C),4) //第四行為作出內部的正方形 ```  ---- ### Step2 ## 製作滑桿 ---- 命名為整數滑竿 n，範圍 0~5，增量 1 （超過5電腦會爆掉www）  ---- poly2 設定 n>= 1 時才出現  ---- ### step 3 ### 迴圈畫正方形 ---- ### 指令長這樣，為什麼呢？  ---- ### 首先來看這個 變量 i 控制 x 方向，變量 j 控制 y 方向 共兩個迴圈   ---- ### 再看這個   ---- ### 最後再看這個   ---- ### 藉由上述我們可知有規律 - 邊長每次乘以 \\(1 \over 3\\) - 起始點 (3,3) 每次乘以 \\(1 \over 3\\)    ---- ### 應此將上述改寫成以下這行 外面再套ㄧ層Sequence，加入變量k 執行1~n次（n就是滑桿的值）  ```cpp= list1=Sequence(Sequence(Sequence(Polygon((((3)/(3^(k-1)))+((9)/(3^(k-1))) i,((3)/(3^(k-1)))+((9)/(3^(k-1))) j),(((6)/(3^(k-1)))+((9)/(3^(k-1))) i,((3)/(3^(k-1)))+((9)/(3^(k-1))) j),4),i,0,3^(k)-1),j,0,3^(k)-1),k,1,n) ``` ---- ### 這樣就完成了 ─=≡Σ((( つ•̀ω•́)つ  ###### 全部程式碼在下頁 ---- 全部程式碼在這 ```cpp= O=(0,0) A=(27,0) poly1=Polygon(O,A,4) poly2=Polygon(Dilate(O,((2)/(3)),B),Dilate(A,((2)/(3)),C),4) f=Segment(O,A,poly1) list1=Sequence(Sequence(Sequence(Polygon((((3)/(3^(k-1)))+((9)/(3^(k-1))) i,((3)/(3^(k-1)))+((9)/(3^(k-1))) j),(((6)/(3^(k-1)))+((9)/(3^(k-1))) i,((3)/(3^(k-1)))+((9)/(3^(k-1))) j),4),i,0,3^(k)-1),j,0,3^(k)-1),k,1,n) ```