本系列的主题是“NURBS”,但是大部分篇幅集中与Bezier(B Spline的特殊形式),B Spline。之所以这么安排,是因为NURBS与B样条可以轻松的互相转换,B样条的计算方法,均可以应用到NURBS(非均匀有理B样条)上。 Continue reading
Yearly Archives: 2017
B-Spline(11):样条曲线拟合-光顺逼近
曲线拟合包含两个方面,插值(interpolation)和逼近(approximation)。用于曲线拟合的离散点通常不具有非常高的精度,直接插值得到的曲线可能不满足“光顺(fair)”要求,本节的目标是介绍光顺的定义,以及给出一种满足“光顺”要求的最小二乘逼近方法。 Continue reading
B-Spline(十):样条曲线拟合-插值(Interpolation)
插值是指:已知形状点(Fit Point),求一条样条曲线穿过所有的形状点。插值是B样条乃至CAGD应用中最常见的应用之一。本节,我将分享一种样条曲线插值算法。 Continue reading
根据三点估算导数/Bessel Tangent方法
在曲线拟合问题中,通常需要根据已知曲线上的离散点,估算出曲线在端点处的导数(严格来说是导矢),常用的一种导数估计方法称为“Bessel Tangent”方法。 Continue reading
B-Spline(九):打断(Subdividing)以及折线化(Tesslelation)
与Bezier曲线的打断方法类似,B样条的打断利用了de Boor算法。并且结合B样条的强凸包性,我们可以推算出一种有效的B样条折线化方法。因此,本节是对前面几节内容的一个综合应用,后面,我的分享也主要面向应用。 Continue reading
windows下gdal python安装与使用
我日常的编程语言是C++,看到周边的同事有学习python,围观了几个小例子,感觉python很不错,用起来很方便。所以我打算利用业余时间学习一些python的知识,如果学会了用GPIO 库控制我的树莓派做一些好玩的事情最好了。这篇文章里。我打算分享一下gdal python库的安装与pycharm下编写一个读取shapefile小程序的过程。 Continue reading
B-Spline(八):节点插入
节点插入的含义是在不改变曲线形状的前提下,向节点序列(knot vector)中插入节点。节点插入的出发点与Bezier曲线的升阶一样,都是想增加控指点的数量以增加曲线的自由度。在不考虑改变曲线阶次的情况下,根据 m=p+n+1的等式,节点数加一,控制点数量加一。 Continue reading
B-Spline(七):求导
求导是参数曲线非常最重要的功能之一。比如切线计算、曲线拟合等等。本节的主要目的是介绍B样条曲线求导的方法。(ps:因为内容里含有矩阵,如果没有正确显示请刷新一下)。 Continue reading
B-Spline(六):给定参数求点(de Boor 算法)
给定参数u,计算参数曲线上对应点的运算称为求值(Evalute)操作。反之,称之为求解(Solve)。这一节的目标是介绍德布尔(de Boor)在1972年提出的数值稳定的求值方法。它是德利斯特里奥(De Casteljau’s)算法的一般化形式。 Continue reading
B-Spline(五):修型-移动控制点
在基函数的性质中我们已经学习过,B样条基函数\(N_{i,p}\)的作用范围是局部的,因此与Bezier曲线不同,移动控制点\(N_{i,p}\)对B样条的影响是局部的。而且,通过基函数“强凸包性”的特点,我们可以推导出若干样条曲线修型的技巧。 Continue reading
B-Spline(四):基函数计算
与Bezier曲线一样,B样条对于给定参数u求曲线上点的算法都不是通过计算基函数的值后带入控制点坐标计算的,而是通过de Boor算法计算,但是在曲线内插、拟合、优化等后续话题中,都需要带入基函数的值。因此本节的目标是介绍给定任意参数u,计算一组\(N_{i,p}(u)\)值的算法。 Continue reading
B-Spline(三)样条曲线的性质
本节的目标为介绍B样条曲线的定义,以及其重要性质。这些性质,对样条曲线的应用起了决定性的作用。 Continue reading
B-Spline(二)基函数
B样条的形式与Bezier曲线的定义方式相同:\(C(u) = \sum_{i=0}^n N_{i,n}(u)P_i \) 但是其基函数的形式有很大的变化。重要的一个不同是,B样条的基函数是定义在一组参数区间上的。这一节,我将介绍B样条的基函数。 Continue reading
NURBS(一): 动机、定义以及历史漫谈
了解完一种特殊的nurbs曲线:贝塞尔曲线后,从本节开始,我将逐步介绍非均匀有理本样条曲线。理解bezier曲线的相关概念对NURBS的学习非常有帮助。本文的目标是介绍NURBS曲线的背景、主要应用和基本概念,并且介绍NURBS的前世今生。 Continue reading
Bezier曲线(四): 曲线升阶(degree elevation)
因为n阶bezier曲线的控制点个数为固定的n+1个,如果需要通过增加控制点个数达到更灵活控制bezier曲线的目的,那么需要将bezier曲线的阶数增加,同时保持曲线的形状不发生变化。 Continue reading
Bezier曲线(三)Bezier曲线的求导和打断
业务中使用曲线的目的,主要是因为曲线具有高阶导数连续的特点。比如设计公路,不仅要求方向连续(\(G^1\)),而且还要求曲率连续。因此,求导是bezier曲线的一项基本而且重要的功能。 Continue reading
Bezier曲线(二):给定参数u求点
贝塞尔曲线最常见的功能就是给定参数点u,计算对应曲线上的点C(u)。这个过程是正算过程,即给定参数求表达式的值。最简单的方法是根据公式,首先计算各基函数的值,然后与相应的控制点相乘,相加。但是这样会计算u的n次幂,有可能是数值不稳定的。本文介绍的德卡斯特里奥(De Casteljau’s)算法,是一种数值稳定的方法。 Continue reading
Bezier曲线(一):定义与控制点移动
计算机图形学中,我们已经接触了贝塞尔曲线的定义。在这篇文章里,我将从几何意义出发解释bezier曲线的定义与运用,为nurbs的学习奠定基础。 Continue reading
NURBS先导集: 参数曲线,切线,曲率与连续性
从本篇开始,我将陆续介绍NURBS(Non-Uniform Relational B-Spline 非均匀有理B样条)有关的算法以及实现。作为背景,我们有必要了解参数曲线的知识。 Continue reading
二维坐标的旋转平移缩放
本文原来发布在cnblogs上,现在移动到我个人博客,并进行了一些修改。 Continue reading
线段交点/geos实现的分析以及我的实现
两线段(直线/射线)求交点是几何计算中的一个最基本的算法。虽然它大部分情况都不是影响程序效率的主要因素,但是它的执行次数可能非常的高,因此提升它的执行效率仍然具有价值。本文将分为两部分,一部分以geos为例,介绍主流的直线交点的判断与计算算法,另一部分给出我的实现,我相信它是一种更加简单和高效的算法,并且可以直接应用于更高的维度。 Continue reading
网页访问变慢的原因分析及优化
我的个人wordpress博客开通也有二个星期了,除了写了几篇文章之外,对云服务器、 wordpress的使用也是非常的感兴趣,从一开始的配置,到各种插件的探索,玩的不亦乐乎。自我感觉个人博客的有意思之处也是在此:建设的乐趣。就像小时候非常爱搭的“房子”一样。哈哈:) Continue reading
最小二乘圆拟合: Pratt 方法
kasa方法圆拟合作为最常见的圆拟合方法,虽然计算方法简单,效率快,但是拟合结果存在较大偏差(Heavy bias)。通过将\(D=\sqrt{(x-a)^2+(y-b)^2}\)与半径R的差值\(D-R\)转换为\(D^2-R^2\),将非线性问题转换为线性问题。但是因为\(D^2-R^2 = d(d+2R) (令d=D-R)\),当偏离值d较大时,kasa方法导致R明显变小。Pratt通过将kasa方法的目标除以\((2R)^2\)的方式,取得更准确的结果。 Continue reading
最小二乘法圆拟合:kasa’s method
在圆拟合方法中,最常见的是一 种代数圆拟合方法,在我查阅的资料中,这种方法被称为“kasa’s method”。已知采样点集\( \{(x_1,y_1),(x_2,y_2),…,(x_n,y_n)\}\) 欲求圆$$(x-a)^2 + (y-b)^2 = r^2$$使得采样点到圆的距离的平方和最近。 Continue reading
道格拉斯-普克折线压缩/抽稀算法 实现
道格拉斯-普克算法,根据wiki,全名“Ramer–Douglas–Peucker algorithm” 是一种采用迭代式方法对折线进行压缩的方法,选取一些特征点代表原折线,并且保证原折线的点距离压缩后的折线不超过一定的范围阈值\(d\)。 Continue reading
最小二乘平面拟合:Ax+By+Cz+D=0
三维平面的表达方式有很多种,通常采用的形式为$$Ax+By+Cz+D=0$$其中\(\begin{bmatrix}A\\B\\C \end{bmatrix}\)为平面法向量。 Continue reading
最小二乘法三维(k维)直线拟合
上篇文章已经实现了二维直线\(Ax+By+C=0\)的拟合算法。如果要拟合三维直线怎么办?首先,方程\(Ax+By+Cz+D=0\)是不可以的,因为他是三维空间中的一个平面。如果要表达一条直线,需要两个三维平面的联立,似乎也不是个好办法。这里我们可以采用直线的“点+向量”方程\(l = A + dD\)的方式。 Continue reading
最小二乘法直线拟合:Ax+By+C=0
因为\( y =kx+b\) 在斜率无穷大或接近无穷大时的数值计算问题,所以在直线方程的选择上选用更一般的形式:$$Ax+By+C=0$$ Continue reading
最小二乘法直线拟合:y= kx+b 及其缺点分析
二维直线常用斜截式方程 \(y=kx+b\)表达。 Continue reading