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

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

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

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

假设有点 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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码