判断两个线段相交问题(快速排斥实验跨立实验) (计算几何)

本文主要是介绍判断两个线段相交问题(快速排斥实验跨立实验) (计算几何),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

计算几何中,有 判断两个线段是否相交问题. 用到快速排斥实验和 跨立实验

快速排斥实验,是跨立实验的前提和基础.

假设有点 P1(x1,y1) P2(x2,y2)  Q1(x3,y3) Q2(x4,y4)  构成线段 P1P2  Q1Q2 问 P1P2与Q1Q2是否相交

快速排斥实验:  

 P1P2 对角线构成矩形R, Q1Q2对角线构成矩形T  若 R与T 相交着 通过快速排斥, 否则不通过

 矩形相交判断:

§  方法:  假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3),Q2 = (x4, y4)

 设矩形 R x坐标的最小边界为 RX1 = min(x1, x2)RX2=max(x1,x2) ,RY1=min(y1,y2)

 以此类推,将矩形表示为 R = (RX1, RY1, RX2, RY2)的形式,若两矩形相交,

 则相交的部分构成了一个新的矩形 F,我们可以知道 F FX1 = max(RX1, TX1), FY2 = max(RY1, TY1),

 FX2 = min(RX2,TX2), FY2 = min(RY2, TX2),得到 F 的各个值之后,

 只要判断矩形 F是否成立就知道 R T到底有没有相交了

  FX1 > FX2 FY1 > Fy1 F无法构成,RT不相交,否则 RT相交

 § 

跨立实验:(互相跨立)

 

若 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 相交



[代码实现]


#include <iostream>
#include <bits/stdc++.h>
using namespace std;typedef struct Node{double x,y;
}point;
typedef struct Segments{point line;
}Line;
typedef struct Rectangle{point A,B;
}Rec; 
double x1,x2,x3,x4,y1,y2,y3,y4;
bool judge1(Rec R,Rec T)
{Rec F;R.A.x=min(x1,x2);R.A.y=min(y1,y2);R.B.x=max(x1,x2);R.B.y=max(y1,y2);T.A.x=min(x3,x4);T.A.y=min(y3,y4);T.B.x=max(x3,x4);T.B.y=max(y3,y4);F.A.x=max(R.A.x,T.A.x); F.A.y=max(R.A.y,T.A.y);F.B.x=min(R.B.x,T.B.x); F.B.y=min(R.B.y,T.B.y);if(F.A.x>=F.B.x || F.A.y>=F.B.y)return false;return true;
}
bool judge2()
{Line P1Q1,P2Q1,Q2Q1,Q2P2,P1P2,Q1P2;P1Q1.line={x1-x3,y1-y3};P2Q1.line={x2-x3,y2-y3};Q2Q1.line={x4-x3,y4-y3};Q2P2.line={x4-x3,y4-y2};Q1P2.line={x3-x2,y3-y2};P1P2.line={x1-x2,y1-y2};// 叉乘  A(x1,y1) X B(x2,y2) = x1y2-x2y1 if( (P1Q1.line.x*Q2Q1.line.y-Q2Q1.line.x*P1Q1.line.y)*(Q2Q1.line.x*P2Q1.line.y-P2Q1.line.x*Q2Q1.line.y)>=0 ){if( (Q1P2.line.x*Q2P2.line.y-Q2P2.line.x*Q1P2.line.y)*(Q2P2.line.x*P1P2.line.y-P1P2.line.x*Q2P2.line.y)>=0 )return true;elsereturn false;}return false;
}
int main()
{Rec R,T;cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;if(!judge1(R,T))cout<<"矩阵R与T矩阵不相交 即 线段P1P2 与线段Q1Q2不相交"<<endl;else{if(judge2)cout<<"线段P1P2 与 线段 Q1Q2 相交"<<endl;elsecout<<"不相交"<<endl; } return 0;
}
/*
-2 0
1 2
-1 1
2 -1
*/



 



这篇关于判断两个线段相交问题(快速排斥实验跨立实验) (计算几何)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/190437

相关文章

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32