{"id":507,"date":"2017-12-10T19:52:13","date_gmt":"2017-12-10T11:52:13","guid":{"rendered":"http:\/\/www.whudj.cn\/?p=507"},"modified":"2019-04-13T10:48:23","modified_gmt":"2019-04-13T02:48:23","slug":"b-spline%e5%9b%9b%e5%9f%ba%e5%87%bd%e6%95%b0%e8%ae%a1%e7%ae%97","status":"publish","type":"post","link":"http:\/\/www.whudj.cn\/?p=507","title":{"rendered":"B-Spline(\u56db):\u57fa\u51fd\u6570\u8ba1\u7b97"},"content":{"rendered":"

\u4e0eBezier\u66f2\u7ebf\u4e00\u6837\uff0cB\u6837\u6761\u5bf9\u4e8e\u7ed9\u5b9a\u53c2\u6570u\u6c42\u66f2\u7ebf\u4e0a\u70b9\u7684\u7b97\u6cd5\u90fd\u4e0d\u662f\u901a\u8fc7\u8ba1\u7b97\u57fa\u51fd\u6570\u7684\u503c\u540e\u5e26\u5165\u63a7\u5236\u70b9\u5750\u6807\u8ba1\u7b97\u7684\uff0c\u800c\u662f\u901a\u8fc7de Boor\u7b97\u6cd5\u8ba1\u7b97\uff0c\u4f46\u662f\u5728\u66f2\u7ebf\u5185\u63d2\u3001\u62df\u5408\u3001\u4f18\u5316\u7b49\u540e\u7eed\u8bdd\u9898\u4e2d\uff0c\u90fd\u9700\u8981\u5e26\u5165\u57fa\u51fd\u6570\u7684\u503c\u3002\u56e0\u6b64\u672c\u8282\u7684\u76ee\u6807\u662f\u4ecb\u7ecd\u7ed9\u5b9a\u4efb\u610f\u53c2\u6570u,\u8ba1\u7b97\u4e00\u7ec4\\(N_{i,p}(u)\\)\u503c\u7684\u7b97\u6cd5\u3002<\/p>\n

\u539f\u59cb\u65b9\u6cd5(naive method)<\/strong><\/p>\n

\u9996\u5148\uff0c\u56de\u60f3B\u6837\u6761\u57fa\u51fd\u6570\u7684\u9012\u5f52\u516c\u5f0f\uff1a$$ N_{i,0}=\\left\\{\\begin{aligned}1&\u00a0 & u \\in [u_i,u_{i+1}) \\\\0 &\u00a0 & otherwise \\end{aligned}\\right. \\\\ N_{i,p}(u)=\\frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u) + \\frac{u_{i+p+1}-u}{u_{i+p+1-u_{i+1}}}N_{i+1,p-1}(u)$$\u901a\u8fc7\u8fd9\u4e2a\u516c\u5f0f\uff0c\u6211\u4eec\u53ef\u4ee5\u8ba1\u7b97\u4efb\u4f55\\(u\\in[u_0,u_m)\\)\u6240\u5bf9\u5e94\u7684\u4e00\u7ec4\u57fa\u51fd\u6570\u503c\\([N_{0,p}(u)],[N_{1,p}(u)],…,[N_{n,p}(u)]\\)\u3002\u4f46\u662f\uff0c\u901a\u8fc7\u57fa\u51fd\u6570\u7684\u6027\u8d28\u6211\u4eec\u4e5f\u4e86\u89e3\u5230\uff0c\u5728\u8fd9n+1\u4e2a\u57fa\u51fd\u6570\u91cc\u9762\uff0c\u81f3\u591a\u4e5f\u53ea\u6709p+1\u4e2a\u57fa\u51fd\u6570\u6709\u503c\u5462\u3002\u5982\u679c\u6309\u7167\u4e0a\u8ff0\u8fed\u4ee3\u5f0f\uff0c\u6211\u4eec\u4f1a\u6d6a\u8d39n-p\u4e2a\u57fa\u51fd\u6570\u7684\u8fd0\u7b97\uff0c\u56e0\u4e3a\u4ed6\u4eec\u7684\u503c\u6839\u672c\u5c31\u662f0\u3002\u800c\u4e14\uff0c\u5982\u679c\u6309\u7167\u9012\u5f52\u65b9\u5f0f\u5b9e\u73b0\u4e0a\u8ff0\u8ba1\u7b97\u8fc7\u7a0b\uff0c\u90a3\u4e48\u8fd8\u4f1a\u9020\u6210\u53e6\u5916\u4e00\u79cd\u6d6a\u8d39\uff1a\u5982\u540cde Casteljau’s \u4e0eFabonacci\u7b97\u6cd5\u7684\u9012\u5f52\u5b9e\u73b0\u4e00\u6837\uff0c\u5f88\u591a\u53c2\u6570\u4e00\u6837\u7684\u51fd\u6570\u88ab\u591a\u6b21\u91cd\u590d\u6267\u884c\u4e86\u3002<\/p>\n

\u6539\u8fdb\u65b9\u5f0f<\/strong><\/p>\n

\u56e0\u4e3a\u5927\u90e8\u5206\u5e94\u7528\u4e2d\u7684B\u6837\u6761\u90fd\u662f\u201cclamped B-Spline\u201d\u5373\u524dp+1\u4e2a\u4e0e\u540ep+1\u4e2a\u8282\u70b9\u91cd\u590d\u7684\u6837\u6761\uff0c\u56e0\u6b64\u6211\u4eec\u53ef\u4ee5\u5047\u5b9a\u53c2\u6570u\u4f4d\u4e8e\u8282\u70b9\u533a\u95f4\\([u_p,u_{m-p}]\\)\u3002<\/p>\n

\"\"<\/p>\n

\u800c\u4e14\uff0c\u89c2\u5bdf\u4e0a\u56fe\u7684\u57fa\u51fd\u6570\u66f2\u7ebf\uff0c\u53ef\u4ee5\u77e5\u9053\u5f53\\(u\\le u_p\\)\u65f6\uff0c\\(N_0=1\\),\u5176\u4ed6\u57fa\u51fd\u6570\u4e3a0\u3002\u5f53\\(u\\ge u_{m-p}\\)\u65f6\uff0c\\(N_n=1\\),\u5176\u4ed6\u57fa\u51fd\u6570\u4e3a0\u3002<\/p>\n

\u5bf9\u4e8e\\(u\\in (u_p,u_{m-p})\\)\uff0c\u6709\u5982\u4e0b\u529e\u6cd5\uff1a<\/p>\n

    \n
  1. \u5bf9\u4e8e\\(u\\in [u_k,u_{k+1})\\)\uff0c\u81f3\u591a\\(N_{k-p},…,N_k\\)\u7b49p+1\u4e2a\u57fa\u51fd\u6570\u975e0\u3002<\/li>\n
  2. \\(N_{k-p},…,N_k\\)\u5728\u533a\u95f4\u00a0\\([u_{k-p},u_{k+p+1})\\)\u4e0a\u975e0\u3002<\/li>\n
  3. \u5728\u533a\u95f4\u00a0\\([u_{k-p},u_{k+p+1})\\)\u4e0a,\\(N_{k,0}=1\\)\uff0c\u5176\u4ed6\\(N_{i,0}=0\\)\u3002<\/li>\n<\/ol>\n

    \u53ef\u4ee5\u770b\u5230\\(N_{i,0}\\)\u6570\u7ec4\u51712p+1\u4e2a\u503c\u5df2\u7ecf\u7ed9\u51fa\uff0c\u53ef\u4ee5\u6309\u7167\u9012\u63a8\u516c\u5f0f\u7b97\u51fa\\(N_{i,1}\\)\u51712p\u4e2a\uff0c\u8fed\u4ee3p\u6b21\u540e\u5f97\u5230p+1\u4e2a\u503c\u5373\\(N_{k-p},…,N_k\\)\u3002<\/p>\n

    \u6211\u7684\u7b97\u6cd5C++\u5b9e\u73b0\u5982\u4e0b\uff1a<\/p>\n

    \/*!\r\n*\\brief b\u6837\u6761\u66f2\u7ebf\u57fa\u51fd\u6570\u8ba1\u7b97\r\n*\\ param double u \u53c2\u6570\u503c\r\n*\\ param int k \u533a\u95f4 k\u3002\u53ef\u4ee5\u901a\u8fc7std::upper_bound()-1\u83b7\u5f97\r\n*\\ param std::vector<double> & basis_func basis_func\u57fa\u51fd\u6570\u503c\uff0c\u5bf9\u5e94N_{k-p},...,N_k\r\n*\\ Returns:   void \r\n*\/\r\nvoid BSpline::BasisFunc(double u,int k,std::vector<double>& basis_func)\r\n{\r\n\tconst int& p = m_nDegree;\r\n\tconst std::vector<double>& knots = m_vecKnots;\r\n\tbasis_func.resize(p+1);\r\n\r\n\t\/\/2p+1\u4e2a N_{i,0}\r\n\tint n = 2 * p + 1;\r\n\tvector<double> temp(n,0);\r\n\ttemp[p] =1;\r\n\r\n\t\/\/\u8fed\u4ee3p\u6b21\r\n\tfor (int j=1;j<=p;++j)\r\n\t{\r\n\t\t\/\/\u533a\u95f4 [k-p,k+p+1)\r\n\t\tfor (int i=k-p,h = 0;h < (n - j);++h,++i)\r\n\t\t{\r\n\t\t\t\/\/\u9012\u63a8\u516c\u5f0f\r\n\t\t\tdouble a = (u - knots[i]);\r\n\t\t\tdouble dev = (knots[i+j] - knots[i]);\r\n\t\t\ta = (dev !=0) ? a \/dev : 0;\r\n\r\n\t\t\tdouble b = (knots[i+j+1]-u);\r\n\t\t\tdev = (knots[i+j+1] - knots[i+1]);\r\n\t\t\tb = (dev != 0)? b\/dev : 0;\r\n\t\t\t\r\n\t\t\ttemp[h] = a*temp[h] + b*temp[h + 1];\r\n\t\t}\r\n\t}\r\n\t\/\/\u62f7\u8d1d\u524d p+1\u4e2a\u503c\u5230basis_func\r\n\tstd::copy(temp.begin(), temp.begin() + p + 1, basis_func.begin());\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u4e0eBezier\u66f2\u7ebf\u4e00\u6837\uff0cB\u6837\u6761\u5bf9\u4e8e\u7ed9\u5b9a\u53c2\u6570u\u6c42\u66f2\u7ebf\u4e0a\u70b9\u7684\u7b97\u6cd5\u90fd\u4e0d\u662f\u901a\u8fc7\u8ba1\u7b97\u57fa\u51fd\u6570 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"_links":{"self":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts\/507"}],"collection":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=507"}],"version-history":[{"count":10,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts\/507\/revisions"}],"predecessor-version":[{"id":1254,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts\/507\/revisions\/1254"}],"wp:attachment":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=507"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=507"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}