acm算法-計(jì)算幾何基礎(chǔ)(編輯修改稿)
2025-08-21 17:20 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 i)/N , sigma(yi)/N (i=1…N) ??? 2022/8/22 35 看看一個(gè)特例： 2022/8/22 36 原因： ?錯(cuò)誤的推廣公式是“質(zhì)點(diǎn)系重心公式”，即如果認(rèn)為多邊形的質(zhì)量?jī)H分布在其頂點(diǎn)上，且均勻分布，則這個(gè)公式是對(duì)的。 ?但是，現(xiàn)在多邊形的質(zhì)量是均勻分布在其內(nèi)部區(qū)域上的，也就是說(shuō)，是與面積有關(guān)的！ 2022/8/22 37 Solution: ? 剖分成 N個(gè)三角形，分別求出其重心和面積，這時(shí)可以想象，原來(lái)質(zhì)量均勻分布在內(nèi)部區(qū)域上，而現(xiàn)在質(zhì)量?jī)H僅分布在這 N個(gè)重心點(diǎn)上（等假變換），這時(shí)候就可以利用剛才的質(zhì)點(diǎn)系重心公式了。 ? 不過(guò)，要稍微改一改，改成 加權(quán)平均 數(shù)，因?yàn)橘|(zhì)量不是均勻分布的，每個(gè)質(zhì)點(diǎn)代表其所在三角形，其質(zhì)量就是該三角形的面積（ 有向面積 ！ ）， ——這就是權(quán)！ 2022/8/22 38 公式： ? C=sigma(Ai * Ci) / A (i=1…N) ? Ci=Centroid(△ O Pi Pi+1) ? = (O + ↑Pi +↑Pi+1 ) ? C=sigma((↑Pi +↑Pi+1)(↑Pi ↑Pi+1) ) /(6A) 2022/8/22 39 全部搞定！ 2022/8/22 40 第三單元 凸包 ( Convex Hull ) 2022/8/22 41 2022/8/22 42 2022/8/22 43 2022/8/22 44 2022/8/22 45 2022/8/22 46 2022/8/22 47 2022/8/22 48 2022/8/22 49 2022/8/22 50 2022/8/22 51 2022/8/22 52 2022/8/22 53 2022/8/22 54 2022/8/22 55 2022/8/22 56 2022/8/22 57 2022/8/22 58 2022/8/22 59 2022/8/22 60 2022/8/22 61 2022/8/22 62 2022/8/22 63 2022/8/22 64 2022/8/22 65 2022/8/22 66 2022/8/22 67 2022/8/22 68 凸包模板：
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1