[中譯] ProjectEuler 363 Bézier Curves

[LPH66 (-858993460)]

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)
推 puzzlez:難道是我按錯了什麼嗎？應該不會吧？@@"
推 babufong:真的不見了耶@@
推 puzzlez:那可以再補回去嗎? @@
推 babufong:砍掉的文章會收到哪個版嗎　帕索要不要去翻找看看- -
推 isnoneval:用貝茲曲線趨近 1/4 圓就是 cos/sin 泰勒展開至 x^3 項
→ LPH66:閒聊一下, 這週終於把50題質數的成就給衝出來了...
→ LPH66:這一陣子比較忙所以幸運數成就只好暫時放著了
→ LPH66:比較囧的是不管是下一題質數還是下一題幸運數都是 367
→ LPH66:還要等一個月...
推 babufong:成就已經隨緣了　走一題是一題XD