快速排斥实验和跨立实验 快速排斥实验

矢量

如果一条线段的端点是有次序之分的话,那么这种线段就称为 有向线段,如果有向线段p1p2的起点p1在坐标的原点,则可以把它称为矢量p2

矢量的加减

设二维矢量 P = (x1, y1), Q = (x2, y2),则 P + Q = (x1 + x2, y1 + y2), P -Q = (x1 - x2, y1 - y2),且有 P + Q = Q + P, P - Q = -(Q - P)

矢量叉积

设矢量 P = (x1, y1), Q = (x2, y2),则 P * Q = x1 * y2 - x2 * y1; 其结果是一个由(0, 0), P, Q, P + Q 所组成的平行四边形的 带符号的面积,P * Q = -(Q * P), P * (- Q) =-(P * Q)

叉积的一个非常重要的性质是可以通过它的符号来判断两矢量相互之间的顺逆时针关系:

若 P * Q > 0,则 P 在 Q 的顺时针方向

若 P * Q < 0, 则 P 在 Q 的逆时针方向

若 P * Q = 0,则 P 与 Q 共线,但不确定 P, Q 的方向是否相同

折线段的拐向判断

如图,假设有折线段 p0p1p2 ,要确定 p1p2 相对于 p0p1 是向左拐还是向右拐,可以通过计算(p2 - p0)*(p1 -p0) 的符号来确定折线的拐向(点 p2 - p0 实际上就是向量 p2,但这里要注意线段和矢量的区别)

判断点是否在线段上

设点 Q = (x, y), P1 = (x1, y1), P2 = (x2, y2),若 (Q - P1)*(P2 - P1) =0 且 min(x1, x2) <= x <= max(x1, x2) && min(y1, y2)<= y <= max(y1, y2),则点 Q 在线段 P1P2 上

判断两线段是否相交

1)快速排斥试验

设以线段 P1P2 为对角线的矩形为 R,设以线段 Q1Q2 为对角线的矩形为 T,若 R、T 不相交,则两线段不可能相交

假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3), Q2 = (x4, y4),设矩形 R的 x 坐标的最小边界为 minRX = min(x1, x2),以此类推,将矩形表示为 R = (minRX, minRY,maxRX, maxRY) 的形式,若两矩形相交,则相交的部分构成了一个新的矩形 F,如图所示,我们可以知道 F 的 minFX =max(minRX, minTX), minFY = max(minRY, minTY), maxFX = min(maxRX,maxTX), maxFY = min(maxRY, maxTX),得到 F 的各个值之后,只要判断矩形 F 是否成立就知道 R 和T 到底有没有相交了,若 minFX > maxFX 或 minFY > maxFy 则 F 无法构成,RT不相交,否则RT相交

2)跨立试验

若 P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,则有 (P1 - Q1)*(Q2 - Q1) *(Q2 - Q1)*(P2 - Q1) > 0,当 (P1 - Q1)*(Q2 - Q1) = 0 时,说明 (P1 - Q1)与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验,所以 Q1 必为 P1P2 与 Q1Q2的交点,依然满足线段相交的条件,则跨立试验可改为:

当 (P1 - Q1)*(Q2 - Q1) * (Q2 - Q1)*(P2 - Q1) >= 0,则 P1P2 跨立Q1Q2,当 Q1Q2 也跨立 P1P2 的时候,则 P1P2 相交

(注意式子中被隔开的 * 代表两个叉积的值的相乘,而另外的两个 * 则代表计算矢量叉积)

快速排斥实验和跨立实验 快速排斥实验

  

爱华网本文地址 » http://www.413yy.cn/a/25101015/261123.html

更多阅读

立正稍息跨立 立正稍息qq表情

立正两脚跟靠拢并齐,两脚尖向外分开约60度;两腿挺直;小腹微收,自然挺胸;上体正直,微向前倾;两肩要平,稍向后张;两臂自然下垂,手指并拢自然微屈拇指尖贴于食指的第二节,中指贴于裤缝;头要正,颈要直,口要闭,下颌微收,两眼向前平视。稍息队列常用的

大金和海信日立对比 大金和日立

 从审美观点和最佳空间利用上考虑,家用中央空调可使室内装饰更灵活,轻松实现与室内装潢完美融合的效果。在现代房屋装修中,家用中央空调可称为一步到位、永不落后的选择。家用中央空调品牌哪种好,作为中央空调行业的鼻祖,大金跟海信日立

越野车和跨界车区别 越野车suv区别

越野车是一种为越野而特别设计的汽车。主要特点是四轮驱动,较高的底盘、较好抓地性的轮胎、较高的排气管、较大的马力和粗大结实保险杠。越野车不但可以在野外适应各种路面状况,而且给人一种粗狂豪迈的感觉。在城市里,越来越多的人喜欢

声明:《快速排斥实验和跨立实验 快速排斥实验》为网友北座城市分享!如侵犯到您的合法权益请联系我们删除