第五十三章 比例切割 算法初成

陳東風和李爺爺從董明竹家回來後已經快10點了。

進屋後,李爺爺對他說:“這段時間你嬸嬸不容易,她的事情你要多幫幫她。”

“當然,我是他侄子,不幫他幫誰?爺爺你放心。”陳東風肯定的說。

“那就好,你也知道,這次你文山叔叔去RB治病花了不少錢,光靠兩個人在單位裡的幾十塊工資是不夠的。她想經商的想法很好,我很支持她。”

“現在的萬元戶,哪個不是做小生意的?嬸嬸只要敢闖,現在的華國是遍地黃金。”陳東風對董明竹和李文山以後從商也是很看好的。

“那就好,我老了,不過還是可以爲她跑跑關係的。好了,你去洗漱吧,早點休息。”

陳東風現在哪裡還能輕易睡得這麼早,好不容易抓住靈感的尾巴,說什麼也不能把他丟了。

其實陳東風在航模的設計階段,不怕各種數學模型和理論計算。他最討厭的是各種葉輪的工程設計圖紙的繪製。

工程中表達葉輪表面的方法是投影圖法,通常情況下使用的圓柱座標系中的投影方法是旋轉投影以及軸面投影、平面投影。葉輪的軸面投影圖反映了葉輪的總體尺寸和特徵,而平面投影相當於三視圖裡面的俯視圖。需要葉片表面方程:Θ=(r,z)來一步步畫出空間曲線。就算你畫的再好,到了加工現場加工的時候也是晦澀難懂,需要專門的技術人員分析出一步步的運動指令,效率十分低下。

陳東風看到了貝塞爾曲線是光滑離散化成一段段的微小的直線段的實質,如果可以根據貝塞爾曲線的特徵方程,設計出一套切實可行的算法——把各種曲率的曲線通過命令來生成,那麼既可以簡化設計中製圖的複雜程度,也可以根據曲線各個離散化的座標點反推出數控加工的路徑。所以如果陳東風可以設計的出來那將是一舉兩得的。

70年代現在國際上的流行算法是(以一次方貝塞爾曲線爲例)需要在兩個定點A、B之間,在選定特定u的情況下在曲線上找到點C(u)。一個簡單的方法是把u插到每一個基函數上,計算每個其與基函數的乘積以及其相應的控制頂點,最後將其相加。

雖然這種方法很好,但是缺乏數值穩定性,尤其是在計算伯恩斯坦多項式的時候可能引進數值誤差。當然算法都是各個CAD軟件的核心,是不會輕易示人的。

還有就是一款好的CAD軟件不管是算法重要,它的控制核心也是非常重要,當然現在陳東風也沒考慮到這些,只是想先把算法設計出來。

陳東風也是發了狠,不設計出這個算法,連門都懶的出了,過年前的衛生也忘記打掃了。好在李爺爺看他鑽研辛虧,毫不計較,盡心盡力的爲他做好了後勤工作。

終於,陳東風在大年三十前把這套他自己命名的比例切割算法給設計出來了。靈感來自於華國曆史上著名的數學家祖沖之的割圓術,割圓術目的是等分圓之後取得正多邊形,而他的比例切割是取一個特定的比例來逼近一個特殊的曲線。

簡單來講比例切割算法(以一次貝塞爾曲線爲例)的基本觀點是選擇在AB中的一個點C,C將AB分爲u:1-u(A到C的距離與AB之間的距離之比是u),讓我們找到決定C在哪裡的方法。

從A到B的向量是B-A。因爲u是在0和1之間的比率,點C位於u(B-A)。將A的位置加以考慮,點C爲A+u(B-A)=(1-u)A+uB。因此,對於給定的u,(1-u)A+uB是在A和B之間的點C,將AB分爲u:1-u的兩段。

更加具有普遍性的比例切割算法的想法如下是假設我們想要找到C(u),u在【0,1】中。由第一個多段線P0-P1-P2-P3...-Pn開始,利用上面的法則找到在線段上的點P1i,P1i在P0i到P0(i+1)的連線上並且將這段線分爲u:1-u的兩部分。依次地,我們可以得到n個點10,11,12,...,1(n-1),他們定義了一個新的多段線,一共有n-1段。

新點由1i進行標記,再次利用上面的規則我們可以得到第二個多段線,具有n-1個點(20,21,...,2(n-2))和n-2條邊。從這個多段線開始,進行第三次,得到新的多段線,由n-2個點30,31,...,3(n-3)和n-3條邊組成。重複這個過程n次得到一個點n0。

以上想法只是給定了比例切割想法的幾何解釋,而實際計算需要一個具體的計算方法。

首先,對於每一對臨近的控制點,可以畫出一條右上方和右下方的箭頭(類似於楊輝三角),並且在兩個箭頭的交點處寫下一個新點。例如相鄰的兩個點分別爲ij 和i(j+1),新點是(i+1)j,右下方(相對應的左下方)的箭頭表示將其尾數ij(相對應的爲i(j+1))乘以1-u(相對應的乘以u),新的點是兩個的和。

因此,從初始的第0列開始,我們計算第1列。之後從第1列得到第2列。最終,在n次計算之後我們最終到達了一個單個的點n0並且這個點就是在曲線上的點。下面的算法總結了上面我們討論的內容,輸入的是具有n+1個點的數列P和在0到1之間的u,最終得到在貝塞爾曲線上的點C(u)。

這個計算過程可以用遞歸的方法表示,對於j=0,1,...,n用P0,j表示Pj,也就是P0,j是第0列的第j項元素,在第i列計算第j項如下:P(i,j)=(1-u)P(i-1,j)+uP(i-1,j+1),(i=1,2....,n;j=0,1,2...,n-i)

元素Pi,j是(1-u)Pi-1,j(左上方元素)和 uPi-1,j+1(左下方元素)的和,最終的結果(在曲線上的點)是Pn,0.在這種想法的基礎上,通過編程就可以得到基本的算法程序。

在這個基本算法的基礎上,陳東風還需要對螺旋線、球面螺旋線、雙弧外擺線和星行線、心臟線、圓內螺旋線、正弦曲線、太陽線和費馬曲線等等幾百種曲線給出需要選定的控制點數量和控制比例u。這個工作如果沒有計算機的幫助的話,估計他這輩子都得耗在這上面了。

“好在,通用的算法以及計算出來了,可能有迭代算法效率的不高的問題,但是計算機應該可以克服。”陳東風一邊自言自語,一邊站了起來,往窗外一看天快黑了,正好肚子有點餓,把桌子上堆成小山的草稿紙整理下後,就出了房間。

第一三八章 人才問題第二十七章 院長三招 整機裝配第一三三章 前往鵬城第二十二章 假期結束 成果斐然第三十八章 夜訪嬸嬸 合作外貿第八十五章 推銷第一章:天降異雷 莊周夢蝶第一三零章 不輕鬆的會議2第一二六章 支援第二十九章 試飛大綱 全部完成第二十五章 核心機點火 艱難測試第一一三章 清點&總結第六章 組團複習 團隊初成第九章 院長有請 侃侃而談第六十一章 飛龍航發 點火實驗第一二一章 夜戰第一二六章 支援第五十四章 除夕夜話 鵬城計劃第十章 考試周中 計劃暑假第一一四章 風雲再起第一三九章 布爾戈斯第一零九章 午夜槍聲第一五一章 航模協會第五十三章 比例切割 算法初成第一章:天降異雷 莊周夢蝶第一五二章 計算機曙光第九十四章 偵察演習2第六十四章 方案研討 李組折服第五十八章 飛龍立項 獨立負責第七十八章 飛龍首飛第五章 初識學霸 猶如神助第二十四章 開始試製 齊頭並進第三十章 特技設計 飛行訓練第四十九章 飛龍擱置 備戰考試第六十六章 制導方案 葛森入夥第一三六章 新型電機第一一八章 序幕第一三四章 抵達第一二一章 夜戰第六十三章 放下芥蒂 合作研發第七十七章 組裝完成 試飛計劃第六十六章 制導方案 葛森入夥第九十八章 夜視設備第一四五章 賽後第三十六章 內部商議 籌劃外銷第八十三章 機房觀摩第九章 院長有請 侃侃而談第七十三章 微波信號第一一三章 清點&總結第五十四章 除夕夜話 鵬城計劃第一一二章 請君入甕第八十六章 參與演習的機會第六十七章 鷹擊和鷹眼第三十一章 院長帶隊 奔赴金陵第一二九章 不輕鬆的會議第一五零章 青眼有加第一三七章 設計第一五一章 航模協會第五十九章 飛龍啓動 工廠對接第一零六章 組裝調試第六十五章 修改方案第四十三章 飛龍初議 設計不易第一二四章 結束第一零八章 傳音2第一一零章 雨中試飛第六十三章 放下芥蒂 合作研發第一二二章 出人意料的變化第六十四章 方案研討 李組折服第一零八章 傳音2第一一五章 反火炮鷹眼第一二七章 支援2第七十八章 飛龍首飛第七十七章 組裝完成 試飛計劃第三十五章 橫空出世 橫掃比賽第二十三章 院長再請 準備試製第一四七章 有償服務第一一三章 清點&總結第十一章 大一結束 計劃開始第一三二章 鵬城消息2第一零二章 最後的準備第一四二章 賽前2第九章 院長有請 侃侃而談第二章:慰問連連,從頭開始第七十四章 計算機難題第一二零章 炮戰第一四一章 賽前第八十三章 機房觀摩第九十三章 偵察演習1第一零八章 傳音2第二章:慰問連連,從頭開始第一一六章 功能測試第九十四章 偵察演習2第一四二章 賽前2第九十四章 偵察演習2第一五三章 IBM代理商第一四四章 比賽第一章:天降異雷 莊周夢蝶第九十九章 情況交流第二十三章 院長再請 準備試製