求助！两条三维直线求交点的算法！最好有C++语言的算法程序

Icer 2009-04-11 04:36:59
一直两条三维直线上的两点L1:P1(x1,y1,z1),P2(x2,y2,z2) L2:P3,P4
怎样求两直线交点，我的程序中理论上是一定有交点的，但三维中判断相交不好办，也可以提供求最短距离点的程序代码。
...全文
2459 11 打赏 收藏 转发到动态 举报
写回复
用AI写文章
11 条回复
切换为时间正序
请发表友善的回复…
发表回复
ai_hebe 2009-09-25
  • 打赏
  • 举报
 回复
a1=m_3D_x2-m_3D_x1; b1=m_3D_y2-m_3D_y1; c1=m_3D_z2-m_3D_z1;
a2=m_3D_x3-m_3D_x1; b2=m_3D_y3-m_3D_y1; c2=m_3D_z3-m_3D_z1;
a3=m_3D_x4-m_3D_x1; b3=m_3D_y4-m_3D_y1; c3=m_3D_z4-m_3D_z1;
//首先判断两直线是否重合，即向量AB，AC，AD是否成比例
if((a1*b2==b1*a2&&a1*b3==b1*a3)&&(a1*b3==b1*a3&&a1*c3==c1*a3))
MessageBox("两直线重合!");
else
{
//根据四点共面定理,若三个向量的混合积(AB,AC,AD)!=0,则四点不共面.
if((a1*b2*c3+a2*b3*c1+a3*b1*c2-a3*b2*c1-a1*b3*c2-a2*b1*c3)!=0)
MessageBox("两直线异面，没有交点!");
else
{
//共面以后判断是否平行，向量AB=(a1,b1,c1),向量CD=(a3-a2,b3-b2,c3-c2)
//若向量CD是AB成比例，则表示平行.
if((a3-a2)*b1==(b3-b2)*a1&&(a3-a2)*c1==(c3-c2)*a1)
MessageBox("两直线平行，没有交点!");
else
{
//通过计算，得到交点的坐标
m_3D_x=(a1*a3*b2-a1*a2*b3)/(b1*a3+b2*a1-b3*a1-a2*b1)+m_3D_x1;
m_3D_y=(b1*a3*b2-b1*a2*b3)/(b1*a3+b2*a1-b3*a1-a2*b1)+m_3D_y1;
m_3D_z=(c1*a3*b2-c1*a2*b3)/(b1*a3+b2*a1-b3*a1-a2*b1)+m_3D_z1;
UpdateData(false);
}

}
Dancing_Sea 2009-05-28
  • 打赏
  • 举报
 回复
struct SVert3d
{
double x, y, z;
};
SVert3d p1, p2, q1, q2;
混合积，检查这四个点形成的四面体的体积是否为零，不为零，则不相交


double t;
p = p1 + (p2-p1) * t;

如果p在 q1q2上，那么
(p-q1) 叉乘 (q2-q1) 得到的向量各项 vn 均为0; 按 vn 分量中绝对值最大值求出t;

如果是线段：
1、检查 t 是否在[0, 1]区间内
2、检查 p是否在 q1 q2之间，用q1p, q2p, 跟q1q2的长度作比较
len(q1p) > len(q1q2) 不在线内
len(q2p) > len(q1q2) 不在线内

程序自己写了
小草sd 2009-05-27
  • 打赏
  • 举报
 回复
可以给出两直线的参数方程，偏微分求解，可得两直线最近点和距离。
arong1234 2009-05-24
  • 打赏
  • 举报
 回复
没有z座标当然是错误的
首先这样的两条直线不一定相交，不知道你的理论是这样确保他相交的

考虑直线
L1:P1(x1,y1,z1),P2(x2,y2,z2)
L2:P3(x3,y3,z3),P4(x4,y4,z4)

根据P1,P2可以得到L1的参数方程
x=x1 * t + (1-t)*x2 = (x1-x2) t +x2
y=y1 * t + (1-t)*y2 = (y1-y2) t +y2
z=z1 * t + (1-t)*z2 = (z1-z2)t +z2

同理，直线L2的参数方程
x=x3 * s + (1-s)*x4 = (x3-x4) s +x4
y=y3 * s + (1-s)*y4 = (y3-y4) s +y4
z=z3 * s + (1-s)*z4 = (z3-z4) s +z4

上面两组方程重x,y,z分别相等可以得到关于s,t的3个方程
(x1-x2) t +x2 = (x3-x4) s +x4
(y1-y2) t +y2 = (y3-y4) s +y4
(z1-z2) t +z2 = (z3-z4) s +z4


整理一下就是
(x1-x2)t +(x4-x3)s = x4-x2
(y1-y2)t +(y4-y3)s = y4-y2
(z1-z2)t +(z4-z3)s = z4-z2

这个方程有唯一解的前提是
矩阵
x1-x2, x4-x3
y1-y2, y4-y3
z1-z2, z4-z3

和增广矩阵
x1-x2, x4-x3,x4-x2
y1-y2, y4-y3,y4-y2
z1-z2, z4-z3,z4-z2
的秩必须相等

如果满足这个条件，那么上面的线性方程求解的方法到处都是






[Quote=引用 7 楼 zhuj397 的回复:]
那这个意思是跟z的坐标没有关系了？
[/Quote]
zhuj397 2009-05-24
  • 打赏
  • 举报
 回复
那这个意思是跟z的坐标没有关系了？
fosjos 2009-04-11
  • 打赏
  • 举报
 回复
[Quote=引用 4 楼 baiwei156 的回复:]
求交点坐标的问题完全可以用数学的方法求得结果的表达公司来解决啊
设P1(x1,y1,z1),P2(x2,y2,z2) L2:P3(x3,y3,z3),P4（x4,y4,z3）
记xi-xj=xij,ij是下标
利用参数式，设L1方程为 x=x1+x12*t, y=y1+y12*t,z=z1+z12*t
L2方程x=x3+x34*s, y=y3+y34*s,z=z3+z34*s.
将L1带入L2，可以得到t的表达式

t=(y13*x34-y34*x13)/(y34*x12-x34*y12)

带入L1中，即可得到交点。。。。
如

x=x1+x12*((y13*x34-y34*x13)/(y3…
[/Quote]
立体几何得到两个直线方程，行列式求二元一次方程组的解
最后判断分母是否为0，是0就不相交
baiwei156 2009-04-11
  • 打赏
  • 举报
 回复
笔误
第1行，“公司”应为“公式”
第2行，P4P4（x4,y4,z4）

不能直接修改帖子，好郁闷啊
baiwei156 2009-04-11
  • 打赏
  • 举报
 回复
求交点坐标的问题完全可以用数学的方法求得结果的表达公司来解决啊
设P1(x1,y1,z1),P2(x2,y2,z2) L2:P3(x3,y3,z3),P4（x4,y4,z3）
记xi-xj=xij,ij是下标
利用参数式，设L1方程为 x=x1+x12*t, y=y1+y12*t,z=z1+z12*t
L2方程x=x3+x34*s, y=y3+y34*s,z=z3+z34*s.
将L1带入L2，可以得到t的表达式

t=(y13*x34-y34*x13)/(y34*x12-x34*y12)

带入L1中，即可得到交点。。。。
如

x=x1+x12*((y13*x34-y34*x13)/(y34*x12-x34*y12)),全部都是已知的

直接给出表达式，求出结果即可



LemIST 2009-04-11
  • 打赏
  • 举报
 回复
[Quote=引用 2 楼 LemIST 的回复:]
P1：x1, y1, z1
P2: x2, y2, z2
P3: x3, y3, z3
P4: x4, y4, z4

设交点为P: x, y, z
则
(x - x1) / (y - y1) = (x1 - x2) / (y1 - y2)
(x - x3) / (y - y3) = (x3 - x4) / (y3 - y4)
(y - z1) / (z - y1) = (y1 - y2) / (z1 - z2)
(y - z3) / (y - z4) = (y3 - y4) / (z3 - z4)

解方程,可以算出x, y, z.或算不出就说明没有交点
[/Quote]
还要验证
(x - x1) / (z - z1) = (x1 - x2) / (z1 - z2)
(x - x3) / (z - z3) = (x3 - x4) / (z3 - z4)
LemIST 2009-04-11
  • 打赏
  • 举报
 回复
P1：x1, y1, z1
P2: x2, y2, z2
P3: x3, y3, z3
P4: x4, y4, z4

设交点为P: x, y, z
则
(x - x1) / (y - y1) = (x1 - x2) / (y1 - y2)
(x - x3) / (y - y3) = (x3 - x4) / (y3 - y4)
(y - z1) / (z - y1) = (y1 - y2) / (z1 - z2)
(y - z3) / (y - z4) = (y3 - y4) / (z3 - z4)

解方程,可以算出x, y, z.或算不出就说明没有交点
Icer 2009-04-11
  • 打赏
  • 举报
 回复
各位大大帮帮忙啊，困惑几天了。。。
C++语言实现一些基本算法(两点距离、点是否在直线上、点与直线的关系、两直线的夹角、两直线的交点、两个举行的重合面积等等)
C++语言实现一些基本算法(两点距离、点是否在直线上、点与直线的关系、两直线的夹角、两直线的交点、两个举行的重合面积等等)
判断两条直线相交算法
这个算法在数学建模中非常有用.特别是当涉及图论的知识时,这个算法将非常有用.
c++与人工智能
立足于大数定律的统计规律是当前成熟AI产品的理论基础之一。 1、C++程序设计技术与计算机软件行业发展趋势介绍2、C++技术与人工智能在主流行业中的已有应用3、从算法到人工智能：：如何真正实现随机生成？来自扫雷游戏的启示4、智能语音应答的技术解决方案：QQ自动聊天是如何实现的5、Python人工智能编程语言的宠儿—python是用C写的？：python调用c++三维引擎
实战OpenGL三维可视化系统开发与源码精解.part10
第1篇　系统开发基础 　　包括第1章三维图形世界、第2章OpenGL概述和第3章Oracle与 OCI技术及编程基础。 　　第1章　介绍了计算机三维图形技术的发展、科学计算可视化技术、三维可视化工程设计的基本概念和发展现状。 　　第2章　主要对OpenGL的基本概念、OpenGL编程基础和在Visual C++环境下OpenGL基本程序框架的建立进行了讲解，并给出了一个简单的旋转立方体程序示例。通过这一章，使读者对OpenGL有初步的概念和了解，对于纹理、显示列表等更深入的编程，我们将通过后续章节进行更详细的讲解和学习。 　　第3章　主要对Oracle数据库及其特点进行简要的介绍和说明。以Oracle 9i为例，介绍了Oracle数据库的安装步骤和Oracle支持的数据类型。在此基础上，介绍了ADO、Pro*C/C++和OCI三个主要Oracle编程接口，对它们的各自功能和特点进行了详细说明，从功能方面、性能方面、开发难度方面进行了详细分析和比较。重点介绍OCI编程基础、OCI的数据结构、OCI程序的基本结构、OCI执行的步骤，最后给出了在Visual C++6.0环境下开发OCI应用程序的示例。 　　第2篇　大规模地形三维可视化系统设计与实现 　　包括第4章地形三维可视化系统框架与OCI类模块设计、第5章地形三维可视化系统的地形渲染实现和第6章地形三维可视化系统项目管理与辅助功能设计。 　　第4章　在第2章的基础上，完成了基于OpenGL的地形三维可视化系统程序框架的建立，为后续的功能模块开发提供了基础平台；在第3章的基础上，设计了OCI公共类，将所有与OCI有关的数据库操作、数据读取等功能函数实现全部封装在该类中，并定义了公共类的全局变量myOci。 　　第5章　本章对地形三维可视化进行了基本概述，介绍了目前地形三维可视化的主要算法。主要介绍了海量地形与影像纹理数据的常用获取方法，给出了海量地形自分块与影像纹理分块原则和程序实现，以及地形与影像子块调度的程序实现，在此基础上实现了地形的三维可视化；还介绍了真三维立体的实现算法和数学模型，在此基础上给出了基于OpenGL的真三维立体的程序实现。 　　第6章　主要讲解了新建项目、打开项目、背景天空的绘制、绘图模式控制的实现方法和程序设计。介绍了基于OpenGL深度缓存的二维屏幕坐标向三维空间坐标的转换算法，实现了对三维空间坐标和空间距离查询，以及查询标识设置的程序设计；最后讲解了基于键盘和鼠标联合控制的三维场景照相机程序模块的实现，实现三维场景的前、后、左、右移动和任意方向的旋转。 　　第3篇　线路三维可视化系统设计与实现 　　包括第7章三维交互技术与三维线路数据结构、第8章三维线路设计实现、第9章道路整体三维建模和第10章三维漫游的实现。 　　第7章　主要对三维交互环境进行了介绍，详细讲解了正射投影模式的实现、正射投影模式下场景控制方法和程序设计，以及透视投影模式的实现方法；还讲解了正射投影模式和透视投影模式下三维地面坐标的获取原理、方法，在此基础上，设计了边坡数据结构、桥梁数据结构、隧道数据结构、水沟数据结构及线路数据结构，为实现三维线路设计做好了前期准备。 　　第8章　主要对线路方案的主要参数设计方法和程序实现、设计交点信息输入实现、线路中心线定位方法、设计方案的保存、平面方案的自动生成和程序设计、纵断面设计模块的实现、边坡模型的生成算法、线路路基三维建模方法和实现、隧道三维建模和参数控制、桥梁三维建模和参数控制的程序设计进行了详细讲解。 　　第9章　主要讲解了道路整体三维模型实现，对其中的线路封闭区域确定与分割算法、地形块综合数据点计算、分块TIN模型的构网实现、封闭区域内数据点的剔除、整体构网的程序实现都进行了详细说明；在纹理管理部分，详细讲解了边坡纹理、路肩纹理、桥梁护坡面纹理、隧道内墙纹理、隧道洞门纹理的程序设计和实现。 　　第10章　从多个方面对三维漫游的基本概念、程序实现、参数调整和控制进行了讲解，帮助读者学会在三维可视化系统中三维漫游模块的程序设计方法；对飞行路径的基本概念、设置方法、插值算法、保存和打开的程序设计，沿飞行路径实现三维漫游的程序设计，沿线路方案漫游的固定高度和相对高度两种模式的程序设计，三维漫游控制和调整的程序设计，以及三维漫游的相关计算都进行了详细的讲解，每一部分都给出了完整的程序代码。 　　第4篇　线路三维可视化系统辅助功能实现 　　包括第11章显示模式控制及实现、第12章3D模型载入与应用、第13章系统输出接口与动画录制实现和第14章系统简介与运行实例。 　　第11章　本章主要对双目立体方式、正射投影方式和透视投影方式的显示模型模式控制和实现、时钟指北针的程序设计和实现、缩略图的实现方法和程序设计进行
实战OpenGL三维可视化系统开发与源码精解.part08
第1篇　系统开发基础 　　包括第1章三维图形世界、第2章OpenGL概述和第3章Oracle与 OCI技术及编程基础。 　　第1章　介绍了计算机三维图形技术的发展、科学计算可视化技术、三维可视化工程设计的基本概念和发展现状。 　　第2章　主要对OpenGL的基本概念、OpenGL编程基础和在Visual C++环境下OpenGL基本程序框架的建立进行了讲解，并给出了一个简单的旋转立方体程序示例。通过这一章，使读者对OpenGL有初步的概念和了解，对于纹理、显示列表等更深入的编程，我们将通过后续章节进行更详细的讲解和学习。 　　第3章　主要对Oracle数据库及其特点进行简要的介绍和说明。以Oracle 9i为例，介绍了Oracle数据库的安装步骤和Oracle支持的数据类型。在此基础上，介绍了ADO、Pro*C/C++和OCI三个主要Oracle编程接口，对它们的各自功能和特点进行了详细说明，从功能方面、性能方面、开发难度方面进行了详细分析和比较。重点介绍OCI编程基础、OCI的数据结构、OCI程序的基本结构、OCI执行的步骤，最后给出了在Visual C++6.0环境下开发OCI应用程序的示例。 　　第2篇　大规模地形三维可视化系统设计与实现 　　包括第4章地形三维可视化系统框架与OCI类模块设计、第5章地形三维可视化系统的地形渲染实现和第6章地形三维可视化系统项目管理与辅助功能设计。 　　第4章　在第2章的基础上，完成了基于OpenGL的地形三维可视化系统程序框架的建立，为后续的功能模块开发提供了基础平台；在第3章的基础上，设计了OCI公共类，将所有与OCI有关的数据库操作、数据读取等功能函数实现全部封装在该类中，并定义了公共类的全局变量myOci。 　　第5章　本章对地形三维可视化进行了基本概述，介绍了目前地形三维可视化的主要算法。主要介绍了海量地形与影像纹理数据的常用获取方法，给出了海量地形自分块与影像纹理分块原则和程序实现，以及地形与影像子块调度的程序实现，在此基础上实现了地形的三维可视化；还介绍了真三维立体的实现算法和数学模型，在此基础上给出了基于OpenGL的真三维立体的程序实现。 　　第6章　主要讲解了新建项目、打开项目、背景天空的绘制、绘图模式控制的实现方法和程序设计。介绍了基于OpenGL深度缓存的二维屏幕坐标向三维空间坐标的转换算法，实现了对三维空间坐标和空间距离查询，以及查询标识设置的程序设计；最后讲解了基于键盘和鼠标联合控制的三维场景照相机程序模块的实现，实现三维场景的前、后、左、右移动和任意方向的旋转。 　　第3篇　线路三维可视化系统设计与实现 　　包括第7章三维交互技术与三维线路数据结构、第8章三维线路设计实现、第9章道路整体三维建模和第10章三维漫游的实现。 　　第7章　主要对三维交互环境进行了介绍，详细讲解了正射投影模式的实现、正射投影模式下场景控制方法和程序设计，以及透视投影模式的实现方法；还讲解了正射投影模式和透视投影模式下三维地面坐标的获取原理、方法，在此基础上，设计了边坡数据结构、桥梁数据结构、隧道数据结构、水沟数据结构及线路数据结构，为实现三维线路设计做好了前期准备。 　　第8章　主要对线路方案的主要参数设计方法和程序实现、设计交点信息输入实现、线路中心线定位方法、设计方案的保存、平面方案的自动生成和程序设计、纵断面设计模块的实现、边坡模型的生成算法、线路路基三维建模方法和实现、隧道三维建模和参数控制、桥梁三维建模和参数控制的程序设计进行了详细讲解。 　　第9章　主要讲解了道路整体三维模型实现，对其中的线路封闭区域确定与分割算法、地形块综合数据点计算、分块TIN模型的构网实现、封闭区域内数据点的剔除、整体构网的程序实现都进行了详细说明；在纹理管理部分，详细讲解了边坡纹理、路肩纹理、桥梁护坡面纹理、隧道内墙纹理、隧道洞门纹理的程序设计和实现。 　　第10章　从多个方面对三维漫游的基本概念、程序实现、参数调整和控制进行了讲解，帮助读者学会在三维可视化系统中三维漫游模块的程序设计方法；对飞行路径的基本概念、设置方法、插值算法、保存和打开的程序设计，沿飞行路径实现三维漫游的程序设计，沿线路方案漫游的固定高度和相对高度两种模式的程序设计，三维漫游控制和调整的程序设计，以及三维漫游的相关计算都进行了详细的讲解，每一部分都给出了完整的程序代码。 　　第4篇　线路三维可视化系统辅助功能实现 　　包括第11章显示模式控制及实现、第12章3D模型载入与应用、第13章系统输出接口与动画录制实现和第14章系统简介与运行实例。 　　第11章　本章主要对双目立体方式、正射投影方式和透视投影方式的显示模型模式控制和实现、时钟指北针的程序设计和实现、缩略图的实现方法和程序设计进行了详细的讲解和说明。 　　第12章　本章主要对目前常用的3DS、AES、OBJ、MD2、MD3、MS3D等3D模型进行了介绍和说明，并给出了每种3D模型的示例，在此基础上，详细介绍了在OpenGL中应用3DS模型的两种主要方法：通过第三方软件对3DS模型进行转换和直接通过程序读取3DS模型；以桥墩3DS模型为例，给出了3DS模型在线路三维场景中的应用方法和程序设计实现。 　　第13章　介绍了DXF文件格式，详细讲解了DXF输出模块的程序设计，实现了线路三维模型输出到DXF文件，可以在AutoCAD中打开线路三维模型进行观察；设计了动画录制类，实现将OpenGL动画录制到AVI文件中；设计了屏幕图形打印类，实现了对OpenGL屏幕图形的打印，在此基础上，设计录制屏幕图像模块，实现了将OpenGL动画录制为一系列图像并保存到硬盘中。 　　第14章　主要对所建立的三维可视化设计系统的主要特点和功能进行了介绍，对线路可视化设计系统加以总结，并对相应的功能模块进行集中说明，使读者能够对整个三维可视化设计有更加清晰的思路和概念，最后给出系统运行实例。 　　附录 　　包括附录A：相关数学程序模块；附录B：OpenGL核心函数库和应用函数库；附录C：OpenGL常用编程技巧；附录D：OpenGL资源网站。
数据结构与算法

33,009

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章