向量叉积和应用:判断点是否在三角形内部
要求编程判断一个点是否在三角形(三个点)内部。
可以看出,如果点在三角形的内部,沿着三边走一圈,这个点相对于行进路径始终保持相同方向(上图左三角形绿线一直在蓝线左边); 如果点在三角形的外部,沿着三条边走一圈,会有不同的结果(右图中BC前进方向对应绿线指向变为右,即P不在三角形内)。 这样,只要判断点和直线的相对位置就可以了。
点的数据结构表示
这里的代码使用c++,每个点包含x坐标和y坐标,还增加了一个构造函数。
struct Point{ int x; int y; Point(int a, int b) :x(a), y(b){ }};
点和直线的位置关系
注意这里的直线是有方向的,例如P点在AB的坐标,但在BA的右边。
叉积的正负和两条线的夹角
高中几何知识点:
AB × AP = |AB| |AP| sin∠PAB P在AB的左边,则∠PAB在0°到180°之间 , sin∠PAB > 0 。P在AB右边时,则∠PAB在-180°到0°之间 sin∠PAB < 0 因此,我们只要用AB和AP的叉积的正负,就可以判断P和AB的相对位置(AP相对AB是顺时针还是逆时针旋转)。
叉积的计算公式
这里有一个三维向量叉积的定义: a=(x1,y1,z1),b=(x2,y2,z2),
这样就得到了计算叉积的函数:
int cross(const Point &a, const Point &b, const Point &p){ return (b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x);}
使用这个就可以得到判断点和直线位置关系的函数 判断P是否在AB的左边:
bool toLeft(const Point &a, const Point &b, const Point &p){ return cross(a, b, p) > 0;}
根据上面的思路,对三角形的三边判断三次,就可以得到点是否在三角形内部了
bool inTriangle(const Point &p, const Point &a, const Point &b, const Point &c){ bool res = toLeft(a, b, p); if (res != toLeft(b, c, p)) return false; if (res != toLeft(c, a, p)) return false; if (cross(a, b, c) == 0) //ABC is in one line return false; return true;}
测试两个点试试效果
#include <cstdio>#include <iostream>using namespace std;struct Point{ int x; int y; Point(int a, int b) :x(a), y(b){ } friend ostream& operator<<(ostream &os, Point &p);};int cross(const Point &a, const Point &b, const Point &p){ return (b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x);}bool toLeft(const Point &a, const Point &b, const Point &p){ return cross(a, b, p) > 0;}bool inTriangle(const Point &p, const Point &a, const Point &b, const Point &c){ bool res = toLeft(a, b, p); if (res != toLeft(b, c, p)) return false; if (res != toLeft(c, a, p)) return false; if (cross(a, b, c) == 0) //ABC is in one line,不构成三角形 return false; return true;}ostream& operator<<(ostream &os, Point &p){ os << "(" << p.x << ", " << p.y << ") " ; return os;}int main(){ Point A(1, 1); Point B(6, 3); Point C(4, 7); Point P(4, 1); if (inTriangle(P, A, B, C)) cout << P << "is in Trinagle "<<A<<B<<C; else cout << P << "is not in Trinagle "<<A<<B<<C; printf("\n"); Point Q(4, 5); if (inTriangle(Q, A, B, C)) cout << Q << "is in Trinagle "<<A<<B<<C; else cout << Q << "is not in Trinagle "<<A<<B<<C; return 0;}
结果如下:
技术应用场景:
由语言的共通性,上述C++适当修改即可换成JavaScript哦。
核心要点:向量和叉积。
编辑:--ns868