图形算法基础之向量

灰太狼 2022-07-21 01:46 156阅读 0赞

今天部门技术培训，讲了一些算法的基础，这些干货必须记录![吐舌头][tongue.gif]。在我看来，算法和思想才是编程的核心，语言只是一种工具，只要算法和思想懂了，换一种语言学习两天语法，牛逼的功能马上就能做出来。![奋斗][struggle.gif]不过，说归说，作为一个不喜欢思考的小白，想要从码农晋升为攻城狮，还有很长的路要走。![委屈][wronged.gif]

所以，从现在开始吧![奋斗][struggle.gif]

今天要说的是向量。向量从高中开始就经常接触，那时候总觉得课本上的东西到以后工作了是没用的，现在才知道人云亦云是多么愚蠢。![尴尬][awkward.gif]

数学是一种很强大的东西，数学有很简单的东西，比如加减乘除，几何基础，这些简单的“算法”会让人感觉很有趣。数学也有很复杂的东西，复杂到让人不想接近。但如果敢去接近它，并努力攻克它，等到用它来轻轻松松地解决实际问题的时候，你就不只是感觉到有趣，还会有很大的成就感。![大笑][laugh.gif]

说回正题。向量是什么东西？向量就是一个方向而已。几何图形本身是没有方向，但对这些几何图形进行处理时如果没有方向的话将是一个费力不讨好的活。为什么这么说？处理图形无非就是对点、线、区域进行操作，包括判断位置及关系，平移、缩放旋转等变换，而这些操作最后都可以转换为点的操作，不用向量也完全可以做，但这种处理方式的结果肯定是杂乱、低效率、无章可循的。举个简单的例子，判断两条线段能否合并，如果不使用向量的话，就需要求出每条线段的斜率，还要对斜率不存在的情况作特殊处理。在有些地方，向量还可以减少计算量，避免开方，三角计算等复杂计算。

下面给出一个使用向量合并两条线段的代码：

bool MergeLine(line line1, line line2, line & line) {
    	point tempPoint;
    	vector vec1, vec2,vect1,vect2;
    	
    	//(1)预处理，统一线段方向
    	if (line1.startPt.x > line1.endPt.x) {
    		tempPoint = line1.startPt;
    		line1.startPt = line1.endPt;
    		line1.endPt = tempPoint;
    	}
    	if (line2.startPt.x > line2.endPt.x) {
    		tempPoint = line2.startPt;
    		line2.startPt = line2.endPt;
    		line2.endPt = tempPoint;
    	}
    	//(2)判断直线平行
    	vec1.x = line1.endPt.x - line1.startPt.x;
    	vec1.y = line1.endPt.y - line1.startPt.y;
    	vec2.x = line2.endPt.x - line2.startPt.x;
    	vec2.y = line2.endPt.y - line2.startPt.y;
    	//平行：叉乘x1*y2-x2*y1=0
    	//垂直：点乘x1*x2+y1*y2=0
    	if (vec1.x*vec2.y - vec1.y*vec2.x != 0) {
    		return false;
    	}
    	//(3)判断直线共线
    	vect1.x = line1.startPt.x - line2.startPt.x;
    	vect1.y = line1.startPt.y - line2.startPt.y;
    	if (vect1.x*vec1.y - vect1.y*vec1.x != 0) {
    		return false;
    	}
    	//(4)判断直线是否有交点
    	if (line2.startPt.x >= line1.endPt.x || line2.endPt.x <= line1.startPt.x) {
    		return false;
    	}
    	if (line2.startPt.x>line1.startPt.x) {
    		line.startPt.x = line2.startPt.x;
    		line.startPt.y = line2.startPt.y;
    	}
    	else {
    		line.startPt.x = line1.startPt.x;
    		line.startPt.y = line1.startPt.y;
    	}
    	if (line2.endPt.x < line1.endPt.x) {
    		line.endPt.x = line2.endPt.x;
    		line.endPt.y = line2.endPt.y;
    	}
    	else {
    		line.endPt.x = line1.endPt.x;
    		line.endPt.y = line1.endPt.y;
    	}
    	
    	return true;
    }

向量主要有两种计算：点乘和叉乘。点乘用于判断两个向量的方向关系，大于0表示同向，小于0表示反向，等于0表示垂直。叉乘主要用于判断向量是否平行。

判断线段平行后还需要判断共线，处理的方法是用两条线段的起点（或终点）生成一个新向量，如果这个向量与任意一个向量平行，则两条线段共线。

最后判断两条线段是否有交点的方法：用线段2的起点分别与线段1的起点和终点生成两个向量，再判断这两个向量是否同向，如果同向则表示线段2的起点在线段1中间。两样的方式处理线段2的终点。但程序中并没有用这种方式，而是用一种更加简单的方式，直接判断x坐标的相对关系；可以这么做的原因是之前对线段进行预处理，保证每条线段的方向一样，即终点的x坐标比起点大。

[tongue.gif]: http://static.blog.csdn.net/xheditor/xheditor_emot/default/tongue.gif
[struggle.gif]: /images/20220720/2bfef709ad3745d98e6bfe8f593d2e69.png
[wronged.gif]: /images/20220720/d7c8666e4b414f3692915f9f9f3b37e7.png
[awkward.gif]: /images/20220720/e404a4b43c6248c08d868e1bc71b1ae9.png
[laugh.gif]: /images/20220720/2d75fd01b779470db6177d9ec57fb76c.png