|
电脑做运算时，常会有浮点数误差的问题。为避免浮点数误差的问题，用电脑计算几何问题时，会採用不同于一般数学运算时所用的公式和定理。
内积（inner product、dot product）、外积（outer product、cross product）这两个运算只用了加法和乘法，而不包括除法，故能有效的避免除法所產生的浮点数误差。内积与外积有许多很有用的特性。大部分的几何问题，都可以用内积与外积来计算答案。
此处仅作简单介绍。不失一般性，以下都用二维空间当作范例。
内积与外积是向量运算，所以得设计一个向量的资料结构。
struct Vector {int x, y;}; // 二维向量的资料结构
// 内积运算
int dot(Vector& v1, Vector& v2)
{
return v1.x * v2.x + v1.y * v2.y; // 没有除法，尽量避免误差。
}
// 外积运算，回传纯量（除去方向）
int cross(Vector& v1, Vector& v2)
{
return v1.x * v2.y - v1.y * v2.x; // 没有除法，尽量避免误差。
}
struct Vector {int x, y;}; // 二维向量的资料结构
// 内积运算
int dot(Vector& v1, Vector& v2)
{
return v1.x * v2.x + v1.y * v2.y; // 没有除法，尽量避免误差。
}
// 外积运算，回传纯量（除去方向）
int cross(Vector& v1, Vector& v2)
{
return v1.x * v2.y - v1.y * v2.x; // 没有除法，尽量避免误差。
}
向量资料结构拥有一个座标，并拥有一支内积函式与一支外积函式。
两个向量做内积的结果是一个纯量。两个向量做外积的结果为一个向量，然而我们通常只会用到纯量部份，所以让外积函式的回传值为纯量。
内积、外积跟长度的关係
内积后取绝对值，求得的是投影量，再除以投影标的的单位向量，则得到投影长度。
外积后取绝对值，求得的是平行四边形的面积量，再除以底的单位向量，则得到高。
struct Point {double x, y;}; // 点的资料结构
typedef Point Vector; // 向量的资料结构，和点一样
// 内积运算
double dot(Vector& v1, Vector& v2)
{
return v1.x * v2.x + v1.y * v2.y;
}
// 外积运算，回传纯量（去除方向）
double cross(Vector& v1, Vector& v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
// 向量的长度
double length(Vector& v)
{
return sqrt(v1.x * v1.x + v2.y * v2.y);
// return sqrt(dot(v, v));
}
void print_d1_and_d2()
{
Point p, p1, p2;
Vector v1 = p1 - p, v2 = p2 - p;
cout << "d1:" << fabs(dot(v1, v2)) / length(v1);
cout << "d2:" << fabs(cross(v1, v2)) / length(v1);
}
内积、外积跟角度的关系
void print_θ()
{
Point p, p1, p2;
Vector v1 = p1 - p, v2 = p2 - p;
double l1 = length(v1), l2 = length(v2);
cout << "cos(θ):" << dot(v1, v2) / l1 / l2;
cout << "sin(θ):" << cross(v1, v2) / l1 / l2;
cout << "θ:" << acos(dot(v1, v2) / l1 / l2); // [0, π]
cout << "θ:" << asin(cross(v1, v2) / l1 / l2); // [-π/2, π/2]
}
注意到acos与asin的回传值，回传的结果是弪度量（radian）而非度度量（grade），而且回传值的范围也不同。一般都以内积与acos求得介于0到180之间的夹角大小。
内积与向量夹角
利用内积的性质，可以粗略判断夹角大小：内积大于0时，两向量夹角小于90；等于0时，夹角等于90；小于零时，夹角大于90且小于180。
外积与向量旋转
外积大于0时，两向量前后顺序为逆时针顺序（在180之内）；等于0时，两向量平行，也就是指夹角等于0或180；小于0时，两向量前后顺序为顺时针顺序（在180之内）。
转自:http://www.csie.ntnu.edu.tw/~u91029/VectorProduct.html
另外可参考:如何判断一个点是否在三角形内http://blog.csdn.net/xueyong1203/archive/2007/01/05/1474474.aspx | 
转播
