ProjectEuler 363 Bézier Curves - 拼圖

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五里霧中解散宣言千錯万綜則天去私 のり

--