纳金网

标题: 点与直线关系之——点在直线左边右边 [打印本页]

作者: may 时间: 2015-6-28 23:38
标题: 点与直线关系之——点在直线左边右边

最近项目中要求用到点面检测，路径优化（项目中的关键词）。。其中一知识点，要判断一个点和多边形的关系，卡了我半天。晕倒，，领导还赶着要出活。。文科艺术转程序的我，XX碎了一地，、没办法普及了半天数学知识，点点关系，。点线关系，点面关系，三角形四边形多边形面积等等吧。。甚至连现在我都不懂的矩阵都看了半天。。各自平方根，反正不会 Mathf.Sqrt, 什么向量。。。
嫑说那些不开心的事了，转正题。。

最终得到其中关键的一点，点与直线的关系。。

上面推的思路就是：
如求：o是不是在ABCD内部。。
想到2 个方法：
一、

简单思考化：就是判断出 O 点在 AB、AD的右边，BC、CD 的左边，就算图形面ABCD 占用到了点O。。
点线公式：
判断点在线的左边还是右边在构建三角网时是非常重要的

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

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;
}

另外一种方法：

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

Tmp > 0 在左侧

Tmp = 0 在线上

Tmp < 0 在右侧

设线段端点为从 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 线段上

二、
这方法，又牵连的数学知识就又来了，三角形、多边形面积计算，点与点距离，，直线公式，。哎。。。只说下思路吧，数学公式我不提了。。
思路是：
判断点O 和两个点A、B的形成得到三角形，BC、CD,AD，算出各自面积，面积相加得出 S_o，和整个多边形（四边形）的面积 S ，相对比
如果S_o > s ，，点O 在四边形外面。。

最后：
不得不承认，做程序，会数学真好，理科生真对口。。哎。。
以后的路子还很长。。。

以上部分有借鉴是其它网站看到的。。
http://www.cnblogs.com/carekee/articles/2299546.html

欢迎光临纳金网 (http://go.narkii.com/club/)