五千年(敝帚自珍)

主题:【翻译】计算机几何基础算法(一) -- 东方射日

共:💬11 🌺53
全看分页树展 · 主题 跟帖
家园 【翻译】计算机几何基础算法(二)

东方射日:【翻译】计算机几何基础算法(一)

多边形的面积

另外有一个普遍的问题是计算一个给出各个顶点的多边形的面积。我们考虑如下图所示的有五个顶点的非凸多边形。要计算它的面积,我们可以将它分割为一个个三角形。在这个五边形中,我们可以分割为三个三角形:ABC,ACD和ADE。不过,等等....你可能会反对,并不是每个三角形都是这个五边形的一部分。这里,叉积是有正负的优势就大大体现出来了,它会让每件事情都变得很奇妙。首先,我们计算ABxBC可以得到三角形ABC的面积,如果你还记得右手法则的话,在本例中,AB到BC是顺时针,那么我们就会得到一个负值。同样地,由ACxAD的叉积我们可以得到三角形ACD的面积,这也是一个负值。最后,我们计算ADxAE,由于ADE三点是逆时针方向,我们知道那将得到一个正值。我们将这三个面积(两负一正)相加,本例中,我们就得到一个负值,那个绝对值就是这个多边形的面积。

点看全图

外链图片需谨慎,可能会被源头改

看上图,很显然多边形的面积就是三角形ABC和ACD的面积之和减去三角形ADE的面积。

最后一点提示,如果我们计算的面积是负值,表示各个顶点是按顺时针方向给出的。

下面给一段具体的代码,其中顶点是以2维数组的方式给出:

int area = 0;

int N = lengthof(p);

//We will triangulate the polygon

//into triangles with points p[0],p[i],p[i+1]

for(int i = 1; i+1<N; i++){

int x1 = p[i][0] - p[0][0];

int y1 = p[i][1] - p[0][1];

int x2 = p[i+1][0] - p[0][0];

int y2 = p[i+1][1] - p[0][1];

int cross = x1*y2 - x2*y1;

area += cross;

}

return abs(cross/2.0);

注意,如果各顶点都是整数,最后的面积是一个整数的一半。(0.5的整数倍)

线-线交点

你将发现寻找两条线的交点是最普遍的几何问题之一。尽管这个问题很普遍且看起来很简单,但是还是有许多程序员感到无从下手。第一个问题是直线是以什么形式给出的?或者说你希望它是什么形式?理想情况下,每条线都可以写成Ax+By=C的形式。ABC这三个值就可以唯一确定一条直线。然而,经常给我们的直线并不是这样的形式,不过我们总可以很容易地将两个点装换成这种标准形式。例如给出直线上两个点(x1,y1)和(x2,y2),我们可以等到相应的A,B和C:

A = y2-y1

B = x1-x2

C = A*x1+B*y1

无论直线是如何描述的,我们总可以有直线上的至少两个点,然后以上述方式得到A,B和C。好现在我们可以假定我们有两条直线:

A1x + B1y = C1 (一)

A2x + B2y = C2 (二)

那么要找这两条直线的交点就变成一个简单的二元一次方程问题。

double det = A1*B2 - A2*B1

if(det == 0){

//Lines are parallel

}else{

double x = (B2*C1 - B1*C2)/det

double y = (A1*C2 - A2*C1)/det

}

复习一下初中数学,将(一)两边乘以B2,(二)两边乘以B1,然后将两式相减得到:

A1B2x - A2B1x = B2C1 - B1C2

那么就得到 x = (B2C1 - B1C2 )/(A1B2 – A2B1) 类似第你可以得到y.

现在你就得到了两条直线的交点。那么在两条线段的情况下又怎样呢?你需要确认我们的到的点在两条线段上。如果线段的两个端点是(x1,y1)和(x2,y2),那么你只要检查min(x1,x2) ≤ x ≤ max(x1,x2) 和min(y1,y2) ≤ y ≤ max(y1,y2)就可以认为该点在线段上。这里特别提醒一下浮点数的精度问题。如果交点正好在线段的端点或线段是水平/垂直的,简单的比较是可能有问题的。这里你可以定义一个最小的许可误差或是用一个分数的类来进行。

三点确定一个圆

给出不共线的三个点就可以唯一确定一个圆。但这个圆的圆心和半径是多少呢?这个问题实际上就是求直线交点的一个简单应用。如下图示,我们首先确定XY和YZ的中垂线,他们的交点就是圆心。

点看全图

外链图片需谨慎,可能会被源头改

要得到XY的中垂线,首先我们可以有上面的介绍得到XY的直线Ax+By=C。那么它的中垂线就是 -Bx+Ay=D。至于D是多少,可以代入XY的中点得到。中点简单的就是XY两点的x和y坐标的平均值。同样,我们可以得到YZ的中垂线。再用上面介绍的方法得到交点,那就是圆心。

镜像

找到一个点关于一条直线的镜像,我们可以采用上面三点确定一个圆同样的技巧。首先注意到点X和镜像点X'到直线的距离相等,同时注意到XX'垂直于所给的直线。那么如果所给出的直线是Ax+By=C,我们已经知道它的垂线是-Bx+Ay=D。代入点X,就可以计算出D。现在我们可以计算这两直线的交点Y。那么X'=Y-(X-Y)

点看全图

外链图片需谨慎,可能会被源头改

旋转

旋转并不完全和计算直线的交点相关。但是我觉得把它和镜像问题放在一起还是有好处的。事实上找到镜像点的另一种方法是将点X相对点Y旋转180度。

想象一下将一点相对另一点逆时针旋转角度θ 。简单话我们可以假设相对原点旋转,我们有x' = x Cos(θ) - y Sin(θ) 和 y' = x Sin(θ) + y Cos(θ) 。如果相对其他点旋转,那么只要将坐标平移使该点为原点,然后采用以上公式计算,接着再将坐标平移回去即可。

东方射日:【翻译】计算机几何基础算法(三)


本帖一共被 2 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河