图形算法

判断某一点处于有向线段左右侧

这里我们使用矢量来进行判断：
定义：平面上三点A(x1,y1), B(x2,y2), C(x3,y3) 组成的面积（含正负，取绝对值为面积）是：
S(A,B,C) = [ (x1-x3) (y2-y3) - (y1 -y3) (x2-x3) ]
那么，当ABC逆时针顺序时S为正的，顺时针则S为负值。
所以，
对于有向线段AB和点C
如果S(A,B,C)为正数，则C在有向线段AB的左侧；
如果S(A,B,C)为负数，则C在有向线段AB的右侧；
如果S(A,B,C)为0，则C在直线AB上。

点关于直线的距离、垂足、对称点公式

已知点p(x0,y0), 直线方程为Ax+By+C=0;
点到直线的距离d
d = ( Ax0 + By0 +C ) / sqrt( AA + BB);
这个距离有符号之分，表示点处于直线的上下方，绝对值表示欧氏距离。
点到直线上的垂足（x,y）
对于方程 ：
(1) Ax + By +C =0
(2) (y - y0) / (x - x0) = B / A 联合求解：
x = ( BBx0 - ABy0 - AC )/ (AA + BB);
y = (-ABx0 + AAy0 - BC) /(AA + BB )

直线方程

• 直线的一般式方程： Ax + By + C = 0
  平行于x轴时，A=0，C≠0；
  平行于y轴时，B=0，C≠0；
  与x轴重合时，A=0，C=0；
  与y轴重合时，B=0，C=0；
  过原点时，C=0；
  与x、y轴都相交时，A*B≠0。
• 直线的点斜式方程：y - y0 = k( x - x0 ) 也就是 y = k( x - x0 ) + y0
  k为斜率，(x0,y0)为直线上一点
• 直线的斜截式方程： y = kx + b =- (A/B)y - (C/B)
  斜率：k = -A/B
  设（x1,y1）,(x2,y2)为直线上的两点，则
  斜率：k = tanα =（y2-y1）/（x2-x1）或（y1-y2）/（x1-x2）
  代表由直线与右边X轴所成的角的正切，α 为其夹角

垂足公式

• 已知直线一般式方程时：
  设已知直线外一点坐标为（x0,y0）,垂足坐标为（x,y），因为垂线与直线垂直，垂线斜率为k的负倒数，则可得方程：
  { Ax + By + C = 0;
  { (y - y0) / (x - x0) = B / A;
  解方程可得：
  x = ( B*B*x0 - A*B*y0 - A*C ) / ( A*A + B*B )
y = ( -A*B*x0 + A*A*y0 - B*C ) / ( A*A + B*B )
• 已知线段端点时：
  设已知直线外一点坐标为p0（x0,y0）,垂足坐标为（x,y），两端点为p1（x1,y1）和p2（x2,y2）
  则直线斜率为：k1 = ( y2 - y1 ) / (x2 - x1 )
  该直线方程为：y = k1 ( x - x1 ) + y1
  其垂线斜率为：k2 = -1 / k1，
  其垂线方程为：y = k2 (x-x0) + y0 = k2 ( x - x0 ) + y = (-1/k1) (x - x0) + y0
  联立两直线方程，也就是求交点，解得：
  x = ( k1^2 * x1 + k1 * ( y0 - y1 ) + x0 ) / ( k1^2 + 1)
y = k1 * ( x - x1) + y1

点到线段的最近点判断

求出垂足后，判断垂足坐标是否在p1、p2之间，若在则垂足为最近的，否则求p1、p2到p0距离，短者为最近点

点到线段的距离

求出最近点，则就得到了最短距离