扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
判断两线段是否相交
星空大帝1Jk9
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下面的方法是标准算法：　　我们分两步确定两条线段是否相交：　　(1)快速排斥试验　　　　设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交.　　(2)跨立试验 　　　　如果两线段相交,则两线段必然相互跨立对方.若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) & ( Q2 - Q1 ) * ( P2 - Q1 ) & ( Q2 - Q1 ) & 0.上式可改写成( P1 - Q1 ) & ( Q2 - Q1 ) * ( Q2 - Q1 ) & ( P2 - Q1 )
0.当 ( P1 - Q1 ) & ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上；同理,( Q2 - Q1 ) &(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上.所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) & ( Q2 - Q1 ) * ( Q2 - Q1 ) & ( P2 - Q1 ) = 0.同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) & ( P2 - P1 ) * ( P2 - P1 ) & ( Q2 - P1 ) = 0.在相同的原理下,对此算法的具体的实现细节可能会与此有所不同,除了这种过程外,大家也可以参考《算法导论》上的实现.class POINT{public:double x,y;};class LINESEG{public:POINT s,e;}l[2000];double max(double a,double b){return ab?a:b;}double min(double a,double b){return a&b?a:b;}double multiply(POINT sp,POINT ep,POINT op){return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));}bool online(LINESEG l,POINT p){return( (multiply(l.e,p,l.s)==0) &&( ( (p.x-l.s.x)*(p.x-l.e.x)&=0 )&&( (p.y-l.s.y)*(p.y-l.e.y)&=0 ) ) );}/*如果线段u和v相交(包括相交在端点处)时,返回true */bool intersect(LINESEG u,LINESEG v){return( (max(u.s.x,u.e.x)=min(v.s.x,v.e.x))&& //排斥实验(max(v.s.x,v.e.x)=min(u.s.x,u.e.x))&&(max(u.s.y,u.e.y)=min(v.s.y,v.e.y))&&(max(v.s.y,v.e.y)=min(u.s.y,u.e.y))&&(multiply(v.s,u.e,u.s)*multiply(u.e,v.e,u.s)=0)&& //跨立实验(multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)=0));}上面的算法在两线段共线时会有问题,这时第二步时两个叉积都为0,这时就可以用这四个点的不相等的坐标分量来判断两线段是否有重合部分就行了.如果X、Y坐标分量都相等,那就是一个点了此外在用叉积作判断时认为一个线段的端点点在另一个线段上或两线线段有公共端点时两线段有交点.
为您推荐：
其他类似问题
扫描下载二维码trackbacks - 0
2006年10月
242526272829301234567891011131415161718192021222324252627282930311234
方法一、bool TwoLineIsIntersect(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3, float &InterX, float &InterY){ //两条线段是否相交X0X1 AND X1X2
float Minx01 = Min(x0, x1);
float Miny01 = Min(y0, y1);
float Minx23 = Min(x2, x3);
float Miny23 = Min(y2, y3);
float Maxx01 = Max(x0, x1);
float Maxy01 = Max(y0, y1);
float Maxx23 = Max(x2, x3);
float Maxy23 = Max(y2, y3);
if(x1!=x0 && x2!=x3)
float k1 = (y1-y0)/(x1-x0);
float k2 = (y3-y2)/(x3-x2);
float Den = (y1-y0)*(x3-x2) - (y3-y2)*(x1-x0);
if(k1==k2)
{ //平行不相交
float d1 = abs(y0*(x1-x0)-x0*(y1-y0)-y2*(x3-x2)+x2*(y3-y2)); //距离公式d = abs(c1-c2) / sqrt(a*a+b*b)
{//直线重合
if((x2&Minx01 && x2&Maxy01 && y2&Miny01 && y2&Maxy01) || (x3&Minx01 && x3&Maxy01 && y3&Miny01 && y3&Maxy01)
|| (x0&Minx23 && x0&Maxy23 && y0&Miny23 && y0&Maxy23) || (x1&Minx23 && x1&Maxy23 && y1&Miny23 && y1&Maxy23))
//实际碰撞问题线段重合认为相交了
x = ((y2-y0)*(x1-x0)*(x3-x2)+(y1-y0)*(x3-x2)*x0-(y3-y2)*(x1-x0)*x2)/D
y = ((y1-y0)*(x-x0))/(x1-x0) + y0;
if(Minx01&=x && x&=Maxx01 && Miny01&=y && y&=Maxy01 && Minx23&=x && x&=Maxx23 && Miny23&=y && y&=Maxy23)
else if(x1==x0 && x2!=x3)
y = ((y3-y2)*(x0-x2))/(x3-x2) + y2;
if(Minx01&=x && x&=Maxx01 && Miny01&=y && y&=Maxy01 && Minx23&=x && x&=Maxx23 && Miny23&=y && y&=Maxy23)
else if(x1!=x0 && x2==x3)
y = ((y1-y0)*(x2-x0))/(x1-x0) + y0;
if(Minx01&=x && x&=Maxx01 && Miny01&=y && y&=Maxy01 && Minx23&=x && x&=Maxx23 && Miny23&=y && y&=Maxy23)
}}方法二、
(1) 快速排斥试验
　　　　设以线段 P1P2 为对角线的矩形为 R ， 设以线段 Q1Q2 为对角线的矩形为 T ，如果 R 和 T 不相交，显然两线段不会相交。
(2) 跨立试验
　　　　 如果两线段相交，则两线段必然相互跨立对方。若 P1P2 跨立 Q1Q2 ，则矢量 ( P1 - Q1 ) 和 ( P2 - Q1 ) 位于矢量 ( Q2 - Q1 ) 的两侧，即 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) & 0 。上式可改写成 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) & 0 。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 ) 共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2 上；同理， ( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2 上。所以判断 P1P2 跨立 Q1Q2 的依据是： ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) &= 0 。同理判断 Q1Q2 跨立 P1P2 的依据是： ( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) &= 0 。
//确定两条线段是否相交
Yu_GeometryLibrary::intersect(YLineSeg
u,YLineSeg
(max(u.a.x,u.b.x)&=min(v.a.x,v.b.x))&&
(max(v.a.x,v.b.x)&=min(u.a.x,u.b.x))&&
(max(u.a.y,u.b.y)&=min(v.a.y,v.b.y))&&
(max(v.a.y,v.b.y)&=min(u.a.y,u.b.y))&&
(multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)&=0)&&
(multiply(u.a,v.b,v.a)*multiply(v.b,u.b,v.a)&=0));
//判断两个点是否相等
Yu_GeometryLibrary::Euqal_Point(YPoint
return((fabs(p1.x-p2.x)&EP)&&(fabs(p1.y-p2.y)&EP));
//一种线段相交判断函数，当且仅当u,v相交并且交点不是u,v的端点时函数为
Yu_GeometryLibrary::intersect_A(YLineSeg
u,YLineSeg
return((intersect(u,v))&&
(!Euqal_Point(u.a,v.a))&&
(!Euqal_Point(u.a,v.b))&&
(!Euqal_Point(u.b,v.a))&&
(!Euqal_Point(u.b,v.b)));
阅读(13526)
&re: 判断两条线段是否相交& 20:40&
取经来了&&&&&&
&re: 判断两条线段是否相交& 13:32&
非常感谢，很有价值的一篇文章！！！&&&&&&两条线段是否相交，计算交点公式。 - 恶人谷 - ITeye技术网站
博客分类：
A本身无限长，假设B也无限长，直接求得AB的交点坐标，然后再判断该坐标是否在定长线段B的内部就可以了啊
AB本身就是两条直线，知道两端点就可以知道其直线方程，B也是一样，两个方程联立，
得到一个坐标，再看该坐标是否在B的定义域内就可以啊
A的两点为(x1,y1),(x2,y2)
则A的直线方程为l1:y-y1=(y2-y1)(x-x1)/(x2-x1)
B的两点为(x3,y3),(x4,y4)
则B的直线方程为l2:y-y3=(y4-y3)(x-x3)/(x4-x3)
联立解出交点坐标为的横坐标为：
x=(k2x3-y3-k1x1+y1)/(k2-k1)
其中k1=(y2-y1)/(x2-x1)
k2=(y4-y3)/(x4-x3)
可以推导出来
x = ((x2 - x1) * (x3 - x4) * (y3 - y1) -
x3 * (x2 - x1) * (y3 - y4) + x1 * (y2 - y1) * (x3 - x4)) /
((y2 - y1) * (x3 - x4) - (x2 - x1) * (y3 - y4));
同理也可以推导出y的值：
y = ((y2 - y1) * (y3 - y4) * (x3 - x1) -
y3 * (y2 - y1) * (x3 - x4) + y1 * (x2 - x1) * (y3 - y4)) /
((y2 - y1) * (y3 - y4) - (y2 - y1) * (x3 - x4));
double x1 = 10, y1 = 20, x2 = 100, y2 = 200;
double a = (y1 - y2) / (x1 - x2);
double b = (x1 * y2 - x2 * y1) / (x1 - x2);
System.out.println("求出该直线方程为: y=" + a + "x + " + b);
double x3 = 50, y3 = 20, x4 = 20, y4 = 100;
double c = (y3 - y4) / (x3 - x4);
double d = (x3 * y4 - x4 * y3) / (x3 - x4);
System.out.println("求出该直线方程为: y=" + c + "x + " + d);
double x = ((x1 - x2) * (x3 * y4 - x4 * y3) - (x3 - x4) * (x1 * y2 - x2 * y1))
/ ((x3 - x4) * (y1 - y2) - (x1 - x2) * (y3 - y4));
double y = ((y1 - y2) * (x3 * y4 - x4 * y3) - (x1 * y2 - x2 * y1) * (y3 - y4))
/ ((y1 - y2) * (x3 - x4) - (x1 - x2) * (y3 - y4));
System.out.println("他们的交点为: (" + x + "," + y + ")");
********************************************************************
下面附上java的实现，
前提是：a 线段1起点坐标
b 线段1终点坐标
c 线段2起点坐标
d 线段2终点坐标
import java.awt.P
public class AlgorithmUtil {
public static void main(String[] args) {
AlgorithmUtil.GetIntersection(new Point(1, 2), new Point(1, 2),
new Point(1, 2), new Point(1, 2));
AlgorithmUtil.GetIntersection(new Point(1, 2), new Point(1, 2),
new Point(1, 4), new Point(1, 4));
AlgorithmUtil.GetIntersection(new Point(100, 1), new Point(100, 100),
new Point(100, 101), new Point(100, 400));
AlgorithmUtil.GetIntersection(new Point(5, 5), new Point(100, 100),
new Point(100, 5), new Point(5, 100));
* 判断两条线是否相交 a 线段1起点坐标 b 线段1终点坐标 c 线段2起点坐标 d 线段2终点坐标 intersection 相交点坐标
* reutrn 是否相交: 0 : 两线平行 -1 : 不平行且未相交 1 : 两线相交
private static int GetIntersection(Point a, Point b, Point c, Point d) {
Point intersection = new Point(0, 0);
if (Math.abs(b.y - a.y) + Math.abs(b.x - a.x) + Math.abs(d.y - c.y)
+ Math.abs(d.x - c.x) == 0) {
if ((c.x - a.x) + (c.y - a.y) == 0) {
System.out.println("ABCD是同一个点！");
System.out.println("AB是一个点，CD是一个点，且AC不同！");
if (Math.abs(b.y - a.y) + Math.abs(b.x - a.x) == 0) {
if ((a.x - d.x) * (c.y - d.y) - (a.y - d.y) * (c.x - d.x) == 0) {
System.out.println("A、B是一个点，且在CD线段上！");
System.out.println("A、B是一个点，且不在CD线段上！");
if (Math.abs(d.y - c.y) + Math.abs(d.x - c.x) == 0) {
if ((d.x - b.x) * (a.y - b.y) - (d.y - b.y) * (a.x - b.x) == 0) {
System.out.println("C、D是一个点，且在AB线段上！");
System.out.println("C、D是一个点，且不在AB线段上！");
if ((b.y - a.y) * (c.x - d.x) - (b.x - a.x) * (c.y - d.y) == 0) {
System.out.println("线段平行，无交点！");
intersection.x = ((b.x - a.x) * (c.x - d.x) * (c.y - a.y) -
c.x * (b.x - a.x) * (c.y - d.y) + a.x * (b.y - a.y) * (c.x - d.x)) /
((b.y - a.y) * (c.x - d.x) - (b.x - a.x) * (c.y - d.y));
intersection.y = ((b.y - a.y) * (c.y - d.y) * (c.x - a.x) - c.y
* (b.y - a.y) * (c.x - d.x) + a.y * (b.x - a.x) * (c.y - d.y))
/ ((b.x - a.x) * (c.y - d.y) - (b.y - a.y) * (c.x - d.x));
if ((intersection.x - a.x) * (intersection.x - b.x) &= 0
&& (intersection.x - c.x) * (intersection.x - d.x) &= 0
&& (intersection.y - a.y) * (intersection.y - b.y) &= 0
&& (intersection.y - c.y) * (intersection.y - d.y) &= 0) {
System.out.println("线段相交于点(" + intersection.x + "," + intersection.y + ")！");
return 1; // '相交
System.out.println("线段相交于虚交点(" + intersection.x + "," + intersection.y + ")！");
return -1; // '相交但不在线段上
========================下面是找到的另外的一种方法====================
第二种方法: 利用斜率公式, 直线方程为ax+bx+c=0, 先求出a,b,c, 然后再求出交点
public static void main(String[] args) {
Point2D p1 = new Point2D.Double(10, 20);
Point2D p2 = new Point2D.Double(100, 200);
Point2D p3 = new Point2D.Double(50, 20);
Point2D p4 = new Point2D.Double(20, 100);
Param pm1 = CalParam(p1, p2);
Param pm2 = CalParam(p3, p4);
Point2D rp = getIntersectPoint(pm1, pm2);
System.out.println("他们的交点为: (" + rp.getX() + "," + rp.getY() + ")");
public static Param CalParam(Point2D p1, Point2D p2){
double a,b,c;
double x1 = p1.getX(), y1 = p1.getY(), x2 = p2.getX(), y2 = p2.getY();
a = y2 - y1;
b = x1 - x2;
c = (x2 - x1) * y1 - (y2 - y1) * x1;
if (b & 0) {
a *= -1; b *= -1; c *= -1;
}else if (b == 0 && a & 0) {
a *= -1; c *= -1;
return new Param(a, b, c);
public static Point2D getIntersectPoint(Param pm1, Param pm2){
return getIntersectPoint(pm1.a, pm1.b, pm1.c, pm2.a, pm2.b, pm2.c);
public static Point2D getIntersectPoint(double a1, double b1, double c1, double a2, double b2, double c2){
Point2D p = null;
double m = a1 * b2 - a2 * b1;
if (m == 0) {
return null;
double x = (c2 * b1 - c1 * b2) /
double y = (c1 * a2 - c2 * a1) /
p = new Point2D.Double(x, y);
输出的结果为:
求出该直线方程为: y=2.0x + -0.0
求出该直线方程为: y=-2.6665x + 153.34
他们的交点为: (32.854,65.71)
他们的交点为: (32.854,65.71)
浏览: 303285 次
来自: 北京
Y坐标的公式不对。算出来的值是错的！！！！！！！！！！！！！！ ...
茅塞顿开哈，感谢
非常感谢作者这么详细的讲解，自己也动手实践了一下，发现前面几个 ...
你试过没有为啥我试过了没用??扫二维码下载作业帮
1.75亿学生的选择
下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
求出交点之后 为什么还判断交点是否在线段上啊?//交点是线段无线延长的交点呀?求两多边形的交点可以用判定点在多边形内部的方法,如果有一个多边形的一个边的两个顶点中有一个在另一个多边形内或边上,另一个顶点在边上或在外部,则这条边有交点.具体求线段的交点可以用下面的方法求：已知一条线段的两个端点为A(x1,y1),B(x2,y2),另一条线段的两个端点为C(x3,y3),D(x4,y4),要判断AB与CD是否有交点,若有求出.首先判断d = (y2-y1)(x4-x3)-(y4-y3)(x2-x1),若d=0,则直线AB与CD平行或重合,若d!=0,则直线AB与CD有交点,且交点(x0,y0)为：x0 = [(x2-x1)*(x4-x3)*(y3-y1)+(y2-y1)*(x4-x3)*x1-(y4-y3)*(x2-x1)*x3]/dy0 = [(y2-y1)*(y4-y3)*(x3-x1)+(x2-x1)*(y4-y3)*y1-(x4-x3)*(y2-y1)*y3]/(-d)求出交点后在判断交点是否在线段上,即判断以下的式子：(x0-x1)*(x0-x2)
zfieep00022
扫二维码下载作业帮
1.75亿学生的选择
不平行的两条直线一定会有交点,但是不平行的两条线段不一定有交点,因为可能是线段延长之后才会相交.所以用联立两线段所在的两直线方程,求出的交点不一定会在线段上.
为您推荐：
其他类似问题
扫描下载二维码}