About whudj

computational geometry

Bezier曲线(二):给定参数u求点

贝塞尔曲线最常见的功能就是给定参数点u,计算对应曲线上的点C(u)。这个过程是正算过程,即给定参数求表达式的值。最简单的方法是根据公式,首先计算各基函数的值,然后与相应的控制点相乘,相加。但是这样会计算u的n次幂,有可能是数值不稳定的。本文介绍的德卡斯特里奥(De Casteljau’s)算法,是一种数值稳定的方法。 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

最小二乘法三维(k维)直线拟合

上篇文章已经实现了二维直线\(Ax+By+C=0\)的拟合算法。如果要拟合三维直线怎么办?首先,方程\(Ax+By+Cz+D=0\)是不可以的,因为他是三维空间中的一个平面。如果要表达一条直线,需要两个三维平面的联立,似乎也不是个好办法。这里我们可以采用直线的“点+向量”方程\(l = A + dD\)的方式。 Continue reading