[中譯] ProjectEuler 363 Bézier Curves

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間14年前 (2011/12/19 07:55)推噓6(6推 0噓 4→)

留言10則, 4人參與討論串1/1

363. Bézier Curves http://projecteuler.net/problem=363 所謂的 cubic Bézier curve (三次貝茲曲線) 是由四點個 P0, P1, P2 和 P3 定義的。這個曲線是這樣被定義的：分別在線段 P0P1, P1P2, P2P3 上取點 Q0, Q1, Q2 使得 P0Q0/P0P1 = P1Q1/P1P2 = P2Q2/P2P3 = t；分別在線段 Q0Q1, Q1Q2 上取點 R0, R1 使得 Q0R0/Q0Q1 = Q1R1/Q1Q2 = t；在線段 R0R1 上取點 B 使得 R0B /R0R1 = t。當 Q0 在線段 P0P1 上移動時(即當 t 取遍 0 到 1 的所有實數時)， B 所經過的軌跡即為由 P0, P1, P2, P3 定義的貝茲曲線。網頁中的 Applet 可以讓你拖動 P0, P1, P2, P3 及 Q0 的位置來更加了解其構成。容易得知這樣子得到的曲線會和線段 P0P1 切於 P0, 和線段 P2P3 切於 P3。考慮由 P0 = (1,0), P1 = (1,v), P2 = (v,1), P3 = (0,1) 定義的貝茲曲線來近似一個 1/4 圓弧。 v 的值選得讓這個曲線和 OP0, OP3 兩個直線所圍成的面積為π/4 (即 1/4 單位圓面積)。問這曲線的長度相對於一個 1/4 圓弧多了多少百分點？也就是說，若 L 為這樣的曲線長度，求 100 * (L - π/2) / (π/2)。答案四捨五入到小數點第十位。 -- 連續兩週難題所以這一週是很數學的題目 XD (我只搶到第 66 名, 前 50 都沒進... u 大倒是進了第 25) 基本上這正是現在一些地方 (例如 Flash) 裡面使用貝茲曲線近似圓的方式 (之所以是近似是因為圓無法分段用貝茲曲線描述) 在那裡一個圓會被描述成由像這樣的四條 1/4「圓弧」所組成的不過當你求出答案之後就會發現面積相等時長度差其實非常微小因此在我們看起來它就和一個 1/4 圓弧沒什麼兩樣除非放到非常大的地方時才會感覺有差異而這樣做有計算上的好處在畫圓時的參數式不是 sin 和 cos 而是一個三次多項式 (這個多項式正是這種貝茲曲線被稱做「三次貝茲曲線」的原因在計算這題時因為要求弧長所以必須求出來就不多說了) 在計算時間和準確度上能夠更好同樣的可以定義其他次數的貝茲曲線原題目裡的 R0 和 R1 的軌跡正各是一個二次貝茲曲線話說回來, 其實平常在用的近似圓的貝茲曲線不是題目這一條而是讓曲線中點在圓上的那一條 (v = 4(√2 - 1)/3) 這個面積多了約萬分之三長度多了約萬分之一點五但是計算比題目這一條方便多了 -- 話說 362 題的文章怎麼消失了 0.0? -- いああオレたちには見えてるモノがあるbデきっと誰にも奪われないモノがあるはずさけ開口一番一虚一実跳梁跋扈形影相弔yュL羊頭狗肉東奔西走国士無双南柯之夢歪もぶ　意味がないと思えるコトがあるラPきっとでも意図はそこに必ずあるんのく依依恋恋空前絶後疾風怒濤有無相生ラH急転直下物情騷然愚者一得相思相愛だがろ無意味じゃないラ6あの意図が恋たで有為転変死生有命蒼天已死黄天當立 !!6五里霧中解散宣言千錯万綜則天去私のり -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.91 ※ 編輯: LPH66 來自: 140.112.28.91 (12/19 08:07)