文档章节

判断线段相交是否相交

robslove
 robslove
发布于 2015/09/27 21:47
字数 2104
阅读 65
收藏 0

一.矢量基本知识

    因为后面的计算需要一些矢量的基本知识,这里只是简单的列举如下,如果需要更加详细的信息,可以自行搜索wikipedia或google。

1.矢量的概念:如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点,我们可以把它称为矢量(vector)p2。

2.矢量加减法:设二维矢量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 )。

3.矢量的叉积:计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 ),Q = ( x2, y2 ),则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积,即:P × Q = x1*y2 - x2*y1,其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下,本文下述算法中所有的点都看作矢量,两点的加减法就是矢量相加减,而点的乘法则看作矢量叉积。

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

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

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

  若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。

4.折线段的拐向判断:折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:

  若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

  若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

  若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

这一条判断也可用来判断点在线段或直线的哪一测。

为了后文的叙述方便,先定义几个结构:

struct point{
    int x;
    int y;
};
struct v{
     point start;
     point end;
};

    计算两条直线的叉积(cross production), 这里由于定义的都是二维的情况,本质上说,在平面上两个向量的叉积应该是垂直平面的,这里函数返回的整数值即为z轴上的值:

int crossProduct(v* v1, v* v2){
     v vt1, vt2;
    int result = 0;
    
     vt1.start.x = 0;
     vt1.start.y = 0;
     vt1.end.x = v1->end.x - v1->start.x;
     vt1.end.y = v1->end.y - v1->start.y;
    
     vt2.start.x = 0;
     vt2.start.y = 0;
     vt2.end.x = v2->end.x - v2->start.x;
     vt2.end.y = v2->end.y - v2->start.y;
    
     result = vt1.end.x * vt2.end.y - vt2.end.x * vt1.end.y;
    return result;
}

二.判断两条直线相交

    先来看一个简单的情况,即判断两条直线是否相交。

第一个可能会想到的办法,就是判断斜率,这个在中学时代就学过了,不过斜率需要考虑垂直的特殊情况,比较麻烦。更好的办法或许是计算两个向量的叉积,如果为0,则是平行或者重合的,否则两直线相交。

代码就不贴了,直接调用上面的函数就ok了。


三.判断两线段相交

经典方法,就是跨立试验了,即如果一条线段跨过另一条线段,则线段的两个端点分别在另一条线段的两侧。但是,还需要检测边界情况,即两条线段中可能某条线段的某个端点正好落在另一条线段上。这也是算法导论中介绍的算法。

程序模拟如下:

int direction(point* pi, point* pj, point* pk){
     point p1, p2;
    
     p1.x = pk->x - pi->x;
     p1.y = pk->y - pi->y;
    
     p2.x = pj->x - pi->x;
     p2.y = pj->y - pi->y;
    
    return crossProduct(&p1, &p2);
}
int onSegment(point* pi, point* pj, point* pk){
    int minx, miny, maxx, maxy;
    if (pi->x > pj->x){
         minx = pj->x;
         maxx = pi->x;   
     }
    else{
         minx = pi->x;
         maxx = pj->x;
     }
    
    if (pi->y > pj->y){
         miny = pj->y;
         maxy = pi->y;   
     }
    else{
         miny = pi->y;
         maxy = pj->y;
     }
    
    if (minx <= pk->x && pk->x <= maxx && miny <= pk->y && pk->y <= maxy)
        return 1;
    else
        return 0;
}
int segmentIntersect(point* p1, point* p2, point* p3, point* p4){
    int d1 = direction(p3, p4, p1);
    int d2 = direction(p3, p4, p2);
    int d3 = direction(p1, p2, p3);
    int d4 = direction(p1, p2, p4);
    if (d1 * d2 < 0 && d3 * d4 < 0)
        return 1;
    else if (!d1 && onSegment(p3, p4, p1))
        return 1;
    else if (!d2 && onSegment(p3, p4, p2))
        return 1;
    else if (!d3 && onSegment(p1, p2, p3))
        return 1;
    else if (!d4 && onSegment(p1, p2, p4))
        return 1;
    else
        return 0;
}

实际上,如果想改进上述算法,还可以在跨立试验前加一步,就是先做快速排斥试验。那就是,先分别判断以两条线段为对角线的矩形是否相交,如果不相交,则两个线段肯定不相交。


四.判断两条线段相交,然后计算交点

设一条线段为L0=P1P2, 另一条线段或直线为L1=Q1Q2, 要计算的就是L0和L1的交点。

1.首先判断L0和L1是否相交(方法已在前文讨论过), 如果不相交则没有交点, 否则说明L0和L1一定有交点, 下面就将L0和L1都看作直线来考虑. 

2.如果P1和P2横坐标相同, 即L0平行于Y轴 

a)若L1也平行于Y轴 

    i.若P1的纵坐标和Q1的纵坐标相同, 说明L0和L1共线, 假如L1是直线的话他们有无穷的交点, 假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);

    ii.否则说明L0和L1平行, 他们没有交点; 

b)若L1不平行于Y轴, 则交点横坐标为P1的横坐标, 代入到L1的直线方程中可以计算出交点纵坐标; 

3.如果P1和P2横坐标不同, 但是Q1和Q2横坐标相同, 即L1平行于Y轴, 则交点横坐标为Q1的横坐标, 代入到L0的直线方程中可以计算出交点纵坐标; 

4.如果P1和P2纵坐标相同, 即L0平行于X轴

a)若L1也平行于X轴,

    i.若P1的横坐标和Q1的横坐标相同, 说明L0和L1共线, 假如L1是直线的话他们有无穷的交点, 假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);

    ii.否则说明L0和L1平行, 他们没有交点; 

b)若L1不平行于X轴, 则交点纵坐标为P1的纵坐标, 代入到L1的直线方程中可以计算出交点横坐标; 

5.如果P1和P2纵坐标不同, 但是Q1和Q2纵坐标相同, 即L1平行于X轴, 则交点纵坐标为Q1的纵坐标, 代入到L0的直线方程中可以计算出交点横坐标; 

6.剩下的情况就是L1和L0的斜率均存在且不为0的情况 

a)计算出L0的斜率K0, L1的斜率K1;

b)如果K1 = K2 

    i.如果Q1在L0上, 则说明L0和L1共线, 假如L1是直线的话有无穷交点, 假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);

    ii.如果Q1不在L0上, 则说明L0和L1平行, 他们没有交点.

c)联立两直线的方程组可以解出交点来

这个算法并不复杂, 但是要分情况讨论清楚, 尤其是当两条线段共线的情况需要单独考虑, 所以在前文将求两条共线线段的算法单独写出来. 另外, 一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交, 如果结果是相交, 那么在后面就可以将线段全部看作直线来考虑. 需要注意的是, 我们可以将直线或线段方程改写为ax+by+c=0的形式, 这样一来上述过程的部分步骤可以合并, 缩短了代码长度, 但是由于先要求出参数, 这种算法将花费更多的时间.

本文转载自:http://blog.sina.com.cn/s/blog_61dccbaa0100m0p7.html

robslove

robslove

粉丝 5
博文 197
码字总数 83957
作品 0
成都
程序员
私信 提问
数学美 之 判断线段相交的最简方法

首发于我的博客 转载请注明出处 解析几何的巅峰 是 向量 那无关过程的狂妄与简洁 映射着大自然无与伦比的美 引子 如何判断两条直线是否相交? 这很容易。平面直线,无非就是两种关系:相交 ...

hsfzxjy
2017/11/29
0
0
判断两线段是否相交

算法一 1. 快速排斥实验:设一线段P1P2为对角线的矩形为P,设一线段Q1Q2为对角线的矩形为Q,如果P和Q不相交,显然两线段不会相交。 以下2种(方法1、方法2)方法判断矩形是否相交仅限于正矩形...

乙知
2016/11/03
443
0
计算线段或直线与线段的交点

使用矢量叉乘积判断线段与线段(或直线)是否相交。如果结果是相交,那么在后面就可以将线段全部看做直线来考虑。 2.两条线段共线情况需要单独考虑。 3.使用直线或线段方程计算,可以把方程式改...

乙知
2016/11/07
251
0
圆弧与直线段相交的几何问题

已知直线段AB两个端点坐标、圆弧CD起点和终点的坐标,圆心角,半径,判断直线段AB与圆弧CD是否相交,如果相交,求交点数及它们的交点坐标,哪位大神会呢,求思路,能把代码写出来就更好了,如...

yhj8848
2014/05/16
587
2
[Heoi2013]Segment

Description 要求在平面直角坐标系下维护两个操作: 1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 2.给定一个数k,询问与直线 x = k相交的线段中,交点最靠上的线段的编号。 Inpu...

qq_39399999
2017/12/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

新建时隐藏按钮,显示明细时显示

在InitControl()中 if (saTableKeys != null) { rpgDesign.Visible = true; rpgPrint.Visible = true; }......

_Somuns
35分钟前
5
0
【实战演练,拒绝996】-SpringBoot2.x自定义Spring boot Starter

欢迎关注 提升能力,涨薪可待 面试知识,工作可待 实战演练,拒绝996 如果此文对你有帮助、喜欢的话,那就点个赞呗! 前言 是不是感觉在工作上难于晋升了呢? 是不是感觉找工作面试是那么难呢...

ccww_
37分钟前
10
0
SpringBoot从入门到放弃,原理篇-自动配置原理

SpringBoot从入门到放弃,原理篇-自动配置原理 springboot自动配置原理 配置文件能配置的属性参照 自动配置原理 1、springboot启动的时候加载主配置类,开启了自动配置功能@EnableAutoConfig...

有一个小阿飞
今天
11
0
php变量和数据类型

php中的变量 PHP中的变量声明 PHP中的变量的使用 PHP中的数据类型之整型 PHP数据类型之浮点类型和布尔类型 PHP数据类型之字符串类型 PHP数据类型之heredoc和nowdoc的使用 PHP数据类型之复合类...

达达前端小酒馆
今天
7
0
OSChina 周日乱弹 —— 沙发忽然就爆炸了,吓死我了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】@这次装个文艺青年吧:#今日歌曲推荐# 分享Vicetone/Youngblood Hawke的单曲《Landslide》: 《Landslide》- Vicetone/Youngblood Hawke 手机党...

小小编辑
今天
253
10

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部