判断同一平面内任意两线段是否相交的方法

jason zhai 2010-09-19

展开全文

判断同一平面内任意两线段是否相交的方法收藏

本文给出一种判断同一平面内两线段相交的判定方法。如下图：

如果两线段相交，则两线段必然相互跨立对方。
若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。

代码实现：

view plain copy to clipboard print ?

#include <iostream>
#include <math.h>
using namespace std;
#define ABS_FLOAT_0 0.0001
struct pointf
{
float x;
float y;
};
struct Vectorf3D
{
float x;
float y;
float z;
};
bool IsIntersectLine(
const pointf p1, // 线段1起点
const pointf p2, // 线段1终点
const pointf q1, // 线段2起点
const pointf q2 // 线段2终点
)
{
Vectorf3D v1, v2, v3, v4;
v1.x = (p1.x - q1.x);
v1.y = (p1.y - q1.y);
v1.z = 0.0;
v2.x = (q2.x - q1.x);
v2.y = (q2.y - q1.y);
v2.z = 0.0;
//计算v1,v2的叉乘
v3.x = v1.y * v2.z - v1.z * v2.y;
v3.y = v1.z * v2.x - v1.x * v2.z;
v3.z = v1.x * v2.y - v1.y * v2.x;
v1.x = (p2.x - q1.x);
v1.y = (p2.y - q1.y);
v1.z = 0.0;
//计算v2,v1的叉乘
v4.x = v2.y * v1.z - v2.z * v1.y;
v4.y = v2.z * v1.x - v2.x * v1.z;
v4.z = v2.x * v1.y - v2.y * v1.x;
// 计算v3,v4的点积
float fTemp1 = v3.x * v4.x + v3.y * v4.y + v3.z * v4.z;
v1.x = (q1.x - p1.x);
v1.y = (q1.y - p1.y);
v1.z = 0.0;
v2.x = (p2.x - p1.x);
v2.y = (p2.y - p1.y);
v2.z = 0.0;
//计算v1,v2的叉乘
v3.x = v1.y * v2.z - v1.z * v2.y;
v3.y = v1.z * v2.x - v1.x * v2.z;
v3.z = v1.x * v2.y - v1.y * v2.x;
v1.x = (q2.x - p1.x);
v1.y = (q2.y - p1.y);
v1.z = 0.0;
//计算v2,v1的叉乘
v4.x = v2.y * v1.z - v2.z * v1.y;
v4.y = v2.z * v1.x - v2.x * v1.z;
v4.z = v2.x * v1.y - v2.y * v1.x;
// 计算v3,v4的点积
float fTemp2 = v3.x * v4.x + v3.y * v4.y + v3.z * v4.z;
if ((fTemp1 >= ABS_FLOAT_0) && (fTemp2 >= ABS_FLOAT_0))
{
return true;
}
else
{
return false;
}
}
void main(void)
{
pointf p1, p2, q1, q2;
p1.x = 0.0;
p1.y = 0.0;
p2.x = 30.0;
p2.y = 30.0;
q1.x = 0.0;
q1.y = 20.0;
q2.x = 20.0;
q2.y = 0.0;
if (IsIntersectLine(p1, p2, q1, q2))
{
cout<<"线段相交!"<<endl;
}
else
{
cout<<"线段不相交!"<<endl;
}
}

#include <iostream>
#include <math.h>
using namespace std;
#define ABS_FLOAT_0 0.0001
struct pointf
{
float x;
float y;
};
struct Vectorf3D
{
float x;
float y;
float z;
};
bool IsIntersectLine(
const pointf p1, // 线段1起点
const pointf p2, // 线段1终点
const pointf q1, // 线段2起点
const pointf q2  // 线段2终点
)
{
Vectorf3D v1, v2, v3, v4;
v1.x = (p1.x - q1.x);
v1.y = (p1.y - q1.y);
v1.z = 0.0;
v2.x = (q2.x - q1.x);
v2.y = (q2.y - q1.y);
v2.z = 0.0;
//计算v1,v2的叉乘
v3.x = v1.y * v2.z - v1.z * v2.y;
v3.y = v1.z * v2.x - v1.x * v2.z;
v3.z = v1.x * v2.y - v1.y * v2.x;
v1.x = (p2.x - q1.x);
v1.y = (p2.y - q1.y);
v1.z = 0.0;
//计算v2,v1的叉乘
v4.x = v2.y * v1.z - v2.z * v1.y;
v4.y = v2.z * v1.x - v2.x * v1.z;
v4.z = v2.x * v1.y - v2.y * v1.x;
// 计算v3,v4的点积
float fTemp1 = v3.x * v4.x + v3.y * v4.y + v3.z * v4.z;
v1.x = (q1.x - p1.x);
v1.y = (q1.y - p1.y);
v1.z = 0.0;
v2.x = (p2.x - p1.x);
v2.y = (p2.y - p1.y);
v2.z = 0.0;
//计算v1,v2的叉乘
v3.x = v1.y * v2.z - v1.z * v2.y;
v3.y = v1.z * v2.x - v1.x * v2.z;
v3.z = v1.x * v2.y - v1.y * v2.x;
v1.x = (q2.x - p1.x);
v1.y = (q2.y - p1.y);
v1.z = 0.0;
//计算v2,v1的叉乘
v4.x = v2.y * v1.z - v2.z * v1.y;
v4.y = v2.z * v1.x - v2.x * v1.z;
v4.z = v2.x * v1.y - v2.y * v1.x;
// 计算v3,v4的点积
float fTemp2 = v3.x * v4.x + v3.y * v4.y + v3.z * v4.z;
if ((fTemp1 >= ABS_FLOAT_0) && (fTemp2 >= ABS_FLOAT_0))
{
return true;
}
else
{
return false;
}
}
void main(void)
{
pointf p1, p2, q1, q2;
p1.x = 0.0;
p1.y = 0.0;
p2.x = 30.0;
p2.y = 30.0;
q1.x = 0.0;
q1.y = 20.0;
q2.x = 20.0;
q2.y = 0.0;
if (IsIntersectLine(p1, p2, q1, q2))
{
cout<<"线段相交!"<<endl;
}
else
{
cout<<"线段不相交!"<<endl;
}
}

发表于 @ 2009年07月09日　22:04:00 | 评论( 1 ) | 编辑| 举报| 收藏