判断点和直线位置关系的算法实现

判断点和直线位置关系的算法实现

在线段上给定点P的所在方向意味着给定点P和线段(比如AB)的坐标，我们必须确定点P相对于线段的方向。也就是这个点是在线段的右边还是在线段的左边。

这个点可能在线段的后面，在这种情况下，我们通过延伸线段来假设一条假想的线，并确定点的方向。

点与直线的位置关系，只有三种情况存在，分别是点在直线左边，或在直线右边，或在就在线段本身上。

这是一个非常基本的问题，在在线地图导航中经常遇到，

例如:假设用户a在下图中必须到达C点，用户首先到达B点，但之后用户a如何知道他需要右转还是左转?

从线段中了解点的方向也可以解决更复杂的问题，例如，线段相交问题，求两条线段是否相交。

我们要用的坐标系是笛卡尔平面，大多数二维问题都用笛卡尔平面，因为这是一个二维问题。这个问题可以用向量代数的叉积来解决，两点A和B的叉积是:Ax * By - Ay * Bx

其中Ax和Ay分别是A的x坐标和y坐标。类似地，Bx和By分别是B的x和y坐标。叉乘有一个有趣的性质，它将用于从线段确定一个点的方向。也就是说，当且仅当两点在原点(0,0)处的角是逆时针方向时，两点的叉乘是正的。反之，当且仅当这些点在原点的角度是顺时针方向时，叉乘是负的。

举个例子就清楚了，

下图中，角度BOP为逆时针方向，的叉积为29*28 -15 *(-15)= 1037，是正的。

实际上，叉积有更直观的几何意义，根据定义:

" class="mathcode" src="?%5Cvec%7Ba%7D%5Ctimes%5Cvec%7Bb%7D%3D%5Cleft%20%7C%20%5Cvec%7Ba%7D%20%5Cright%20%7C%5Ccdot%20%5Cleft%20%7C%20%5Cvec%7Bb%7D%20%5Cright%20%7Csin%3C%5Cvec%7Ba%7D%2C%5Cvec%7Bb%7D%3E">

其中，， ,分别是向量的模长，" class="mathcode" src="?%3C%5Cvec%7Ba%7D%2C%5Cvec%7Bb%7D%3E">表示两个向量之间的夹角。需要注意的是，叉积有正有负，有其夹角" class="mathcode" src="?%3C%5Cvec%7Ba%7D%2C%5Cvec%7Bb%7D%3E">决定，夹角" class="mathcode" src="?%3C%5Cvec%7Ba%7D%2C%5Cvec%7Bb%7D%3E">可以理解为 到的角，相比内积，叉积只是将  变成了.

如果说内积的几何意义是投影和乘积的话，叉积的几何意义就会明确许多,叉积的数值（绝对值）就表示以两向量为边长的平行四边形的面积。

证明 如图，在平行四边形 OACB 中，设