PKUWWT

消遣时光

几种基本几何预测

本文讨论几种主要的几何预测(geometric predicates)。

方向(orientation)预测

, ,是平面上的3个点。我们已经证明了

是三角形的有向面积的2倍。本文是为了给出另外一种证明。图1显出了一个黄色平行四边形。用大正方形减去长方形,及三角形,可以得到的有向面积为。那这与方向预测有啥关系?

图1. 由矢量,确定的平行

其实,你以点为局部坐标系的原点,则另外两点在此坐标系中的坐标分别为,上面的行列式中用第二行和第三行送去第一行,显然,结果刚好就等于

有向面积值为正,表示三角形是逆时针,否则表示顺时针。如果为0则三点共线。

圆内外(side of circle)预测

, 是平面上的4个点。头3个点定义了一个有向圆(从经过到达)。我们希望判定在圆的左边还是右边。如果圆有逆时针方向,左对应内部,右对应着外部。本文的目的在于显示下面的公式可用于预测圆内外问题(side-of-circle)。

如果4点共线,则上式为0,因为只需要两个点就可以通过仿射变换(系数和为1)表示连线上的所有点,因此上述行列式至少有两行的前3项可以通过行变换变成0,显然这样的行列式值为0。

现在,假定4点不共线,且, 可以定义一个正常的三角形。对于平面上的点来说,令对于抛物面的”提升”。

首先假定的外接圆的中心位于原点。则矩阵第4列是各点离原点的距离的平方,且三点至原点距离相等,设为,而离原点的距离设为,则行列式变成

显然,点可以由其它3个点的仿射组合而得到,即存在,满足

使用上述公式可以简化矩阵的第4行。 在第4行上加上第一行的,第二行的,和第三行的,则第4行的前3项变成0,剩下最后一项为

现在,可以得到上述行列式的值为

其中的外接圆的半径,而离原点的距离。

由上式可知,行列式是可以用于圆内外(side-of-circle)的预测的。如果是逆时针的,则行列式为正说明在圆外,为负说明在圆内,为0说明共圆(或者共线)

此过程可以推广到原点不在外接圆圆心的情况。令原点为的外接圆的原心为,则,而

仍然是由的仿射变换的系数。且易知

与前面的推理一样,消除第4行的前3项,最后一项变成

如果是共线的,上述行列式不一定为0,但是的有向面积却为0。可以考虑极限情况,将其视为是无穷大的圆,由此相当于是判定在直线的哪一边。