判断点在线的左边还是右边还是在线上

这个算法遇到了，虽然有点思路，但是之前没写过

我考虑应该是一条直线把平面划分成两块，将询问点的坐标带入直线，大于0和小于0则说明询问点在直线的两侧

然而后来我还是选择了直接百度。。

以下内容来自https://www.cnblogs.com/carekee/articles/2299546.html,复制到这里备忘，这位兄总结的非常精炼

判断点在线的左边还是右边在构建三角网时是非常重要的

以及两点p1(x1,y1),p2(x2,y2),判断点p(x,y)在线的左边还是右边。

1.

bool LeftOfLine(const ZCoord2D& p, const ZCoord2& p1, const ZCoord2D& p2)

{

    double tmpx = (p1.x - p2.x) / (p1.y - p2.y) * (p.y - p2.y) + p2.x;

    if (tmpx > p.x)//当tmpx>p.x的时候，说明点在线的左边，小于在右边，等于则在线上。

        return true;
return false;
}

2.

另外一种方法：

Tmp = (y1 – y2) * x + (x2 – x1) * y + x1 * y2 – x2 * y1

Tmp > 0 在左侧

Tmp = 0 在线上

Tmp < 0 在右侧

3.

设线段端点为从 A(x1, y1)到 B(x2, y2), 线外一点 P(x0，y0)，
判断该点位于有向线 A→B 的那一侧。
a = ( x2-x1, y2-y1)
b = (x0-x1, y0-y1)
a x b = | a | | b | sinφ (φ为两向量的夹角)
| a | | b |  ≠ 0 时，  a x b  决定点 P的位置
所以  a x b  的 z 方向大小决定 P位置
(x2-x1)(y0-y1) – (y2-y1)(x0-x1)  >  0   左侧
(x2-x1)(y0-y1) – (y2-y1)(x0-x1)  <  0   右侧 
(x2-x1)(y0-y1) – (y2-y1)(x0-x1)  =  0   线段上