Question

点积与叉积

电脑实施运算，通常会有浮点数误差。为了避免浮点数误差，当使用电脑计算几何问题，会採用不同于一般的数学公式和定理。

点积（dot product）、叉积（cross product）这两个运算只有加减法和乘法，而不包括除法，能够有效避免除法产生的浮点数误差，另一方面也能够减少计算时间。点积与叉积有著许多好用的特性，大部分的几何问题，都可以运用点积与叉积来计算答案。

以下都是用二维空间当作范例。

资料结构

点积与叉积是向量运算，所以先设计一个向量的资料结构。

向量资料结构拥有一个座标，并且拥有一支点积函式与一支叉积函式。

两个向量做点积的结果是一个纯量。两个向量做叉积的结果为一个向量，然而我们通常只会用到纯量部份，所以让叉积函式的回传值为纯量。

点积、叉积跟长度的关係

点积的结果为垂直投影的某种量。这某种量取绝对值，再除以底向量长度，得到底。

叉积的结果为平行四边形的面积量。面积量取绝对值，再除以底向量长度，得到高。

点积、叉积跟角度的关係

注意到 acos 与 asin 的回传值，回传的结果是弪度量（radian）而非度度量（grade），而且回传值的范围也不同。一般都以点积与 acos 求得介于 0˚到 180˚之间的夹角大小。

点积与向量夹角

利用点积的性质，可以粗略判断夹角大小：点积大于 0 时，两向量夹角小于 90˚；等于 0 时，夹角等于 90˚；小于零时，夹角大于 90˚且小于 180˚。

叉积与向量旋转

利用叉积的性质，可以粗略判断夹角方向：叉积大于 0 时，两向量前后顺序为逆时针顺序（在 180˚之内）；等于 0 时，两向量平行，也就是指夹角等于 0˚或 180˚；小于 0 时，两向量前后顺序为顺时针顺序（在 180˚之内）。

UVa 10445

Distance

Distance

以下简单介绍二维座标平面上计算距离的方式。

UVa 152 10514 10709

点到原点距离

开根号相当耗费时间。有时候做一些几何计算时，会将数学式子简化到不必开根号，以节省计算时间。因此，设计不开根号的程式码，有时候也是会有用途的。

点到点距离

点到线距离

数学常常用 ax+by+c=0 表示直线，运用 abs(ax+by+c)/sqrt(a^2+b^2) 公式计算点到线距离。计算学则是直接以相异两点表示直线，运用叉积计算点到线距离。

叉积求出 v1v2 组成的平行四边形面积，然后除以 v2 的长度，便是垂直距离。叉积可能会有负值，请记得取绝对值，才不会得到负的距离。

点到线段距离

点到线段的最短距离，有时候是点到线上的垂直距离，有时候却是点到线段端点的距离。

点到线段的距离，和三点共线、点在线上这些因素无关，所以这裡将空间划分为垂直距离区和端点距离区两块，用点积进行判断。这只是一种划分方式，各位也可以自行发明适合的划分方式。

线段到线段距离

两线段相交，距离为零；两线段不相交，穷举所有的端点到线段距离，取最短者。两线段相交请参考后面章节，点到线段距离请参考前面章节。

各位可依照上图所列举的各种情况，验证此方法是有效的。

线到线距离

两线相交，距离为零；两线平行，距离为 l1 上任取一点到 l2 的距离。用叉积判断平行。

Intersection

Intersection

人类比电脑擅长判断相交。人类可以追著线条移动，快速找到交点；人类也有很强的空间感，能够迅速划分地理位置，看一眼就能区隔出成堆的线段。但是电脑却做不到这些，电脑只会算数字、分条件。

判断相交原本是极容易的事情，主角改为电脑之后，却变成极複杂的事情了。下面介绍二维座标平面上判断相交的方式、计算交点的方式。

UVa 191 273 378 527 754 866 10902

点与线段相交

利用点到点距离。开根号，有误差。

比较妥当的方式，是先用叉积判断点与线段是否共线，再用点积判断点是否位于线段端点之间。

Transformation

Transformation

以下介绍二维座标平面上的常见动作。

运用 C++的複数函式库，以複数表示二维座标，就能少写很多程式码。

UVa 10263 12303

Translate

“位移”是直直移动，大小不变。

运用 Incremental Method 的精神，图形的位移，分解成线段的位移，分解成点的位移。

点的位移有两种想法，第一种是座标相加的概念，位移量便是座标差；第二种是向量相加的概念，位移量便是向量差。

虽然第二种想法不太直觉，但是由于向量很强大，还是习惯一下向量吧！

Rotate

“旋转”，先取一个旋转中心点，旋转整张图。

点的旋转，先把旋转中心点位移至原点，就容易处理了。

複数相乘等于角度相加、长度相乘。制造一个複数，长度等于一，角度等于旋转角度，就可以运用複数乘法，完成点的旋转。

Scale

“缩放”，先取一个缩放中心点，缩放整张图。

点的缩放，先把缩放中心点位移至原点，就容易处理了。

Project

“投影”，先取一条投影线，整张图垂直投射至线上。

project 这个英文单字有“投影”和“计画”两种意义，此处讲的是“投影”。

点的投影有两种想法，第一种想法是直线交点的概念，首先求出投影线与其法线，再解联立方程式；第二种想法是向量点积的概念，首先把投影线位移至原点，就容易处理了。

虽然第二种想法不太直觉，但是由于向量很强大，老话一句，还是习惯一下向量吧！

Reflect

“镜射”，先取一条对称线，整张图沿线翻转，正面变反面。

reflect 这个英文单字有“镜射”和“反射”两种意义，此处讲的是“镜射”。

有两种实作方式，后者的程式码比较简洁。