判断两线段是否相交(快速排斥和跨立)

2023-10-11 19:50

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

背景知识:

判断两线段是否相交:  

我们分两步确定两条线段是否相交:  

(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。具体情况如下图所示:

程序模版:

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
typedef struct line
{P s;P e;
}Line;
Line L[M];
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x<y?x:y;
}
int paichi(line a,line b)//快速排斥,若通过快速排斥进行跨立实验,否则无交点;
{if(max(a.e.x,a.s.x)>=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)//叉积
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)//跨立实验(通过相互跨立则可确定两线段相交返回1)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}


相关题目:

hdu1086 判断线段相交

You can Solve a Geometry Problem too

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6740    Accepted Submission(s): 3256


Problem Description
Many geometry(几何)problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very easy, after all we are now attending an exam, not a contest :)
Give you N (1<=N<=100) segments(线段), please output the number of all intersections(交点). You should count repeatedly if M (M>2) segments intersect at the same point.

Note:
You can assume that two segments would not intersect at more than one point. 

Input
Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending. 
A test case starting with 0 terminates the input and this test case is not to be processed.

Output
For each case, print the number of intersections, and one line one case.

Sample Input
  
2 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.00 3 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.000 0.00 0.00 1.00 0.00 0

Sample Output
  
1 3
分析:判断交点数:

程序:

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
typedef struct line
{P s;P e;
}Line;
Line L[M];
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x<y?x:y;
}
int paichi(line a,line b)//快速排斥,若通过快速排斥进行跨立实验,否则无交点;
{if(max(a.e.x,a.s.x)>=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)//叉积
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)//跨立实验(通过相互跨立则可确定两线段相交返回1)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
int main()
{int n,i,j;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);int cnt=0;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(paichi(L[i],L[j])&&kuali(L[i],L[j]))cnt++;}}printf("%d\n",cnt);}
}
poj1127

题目:

Jack Straws
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 3066 Accepted: 1376

Description

In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. Here, we are only concerned with if various pairs of straws are connected by a path of touching straws. You will be given a list of the endpoints for some straws (as if they were dumped on a large piece of graph paper) and then will be asked if various pairs of straws are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws.

Input

Input consist multiple case,each case consists of multiple lines. The first line will be an integer n (1 < n < 13) giving the number of straws on the table. Each of the next n lines contain 4 positive integers,x1,y1,x2 and y2, giving the coordinates, (x1,y1),(x2,y2) of the endpoints of a single straw. All coordinates will be less than 100. (Note that the straws will be of varying lengths.) The first straw entered will be known as straw #1, the second as straw #2, and so on. The remaining lines of the current case(except for the final line) will each contain two positive integers, a and b, both between 1 and n, inclusive. You are to determine if straw a can be connected to straw b. When a = 0 = b, the current case is terminated. 

When n=0,the input is terminated. 

There will be no illegal input and there are no zero-length straws. 

Output

You should generate a line of output for each line containing a pair a and b, except the final line where a = 0 = b. The line should say simply "CONNECTED", if straw a is connected to straw b, or "NOT CONNECTED", if straw a is not connected to straw b. For our purposes, a straw is considered connected to itself.

Sample Input

7
1 6 3 3 
4 6 4 9 
4 5 6 7 
1 4 3 5 
3 5 5 5 
5 2 6 3 
5 4 7 2 
1 4 
1 6 
3 3 
6 7 
2 3 
1 3 
0 02
0 2 0 0
0 0 0 1
1 1
2 2
1 2
0 00

Sample Output

CONNECTED 
NOT CONNECTED 
CONNECTED 
CONNECTED 
NOT CONNECTED 
CONNECTED
CONNECTED
CONNECTED
CONNECTED
分析:判断线段相交+并查集

程序:

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
int f[M];
int finde(int x)
{if(x!=f[x])f[x]=finde(f[x]);return f[x];
}
void make(int a,int b)
{int x=finde(a);int y=finde(b);if(x!=y)f[x]=y;
}
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x<y?x:y;
}
typedef struct line
{P s;P e;
}Line;
Line L[M];
int paichi(line a,line b)
{if(max(a.e.x,a.s.x)>=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
int main()
{int i,n,j;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);for(i=1;i<=n;i++)f[i]=i;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(paichi(L[i],L[j])&&kuali(L[i],L[j]))make(i,j);}}int a,b;while(scanf("%d%d",&a,&b),a||b){if(finde(a)==finde(b))printf("CONNECTED\n");elseprintf("NOT CONNECTED\n");}}return 0;
}




这篇关于判断两线段是否相交(快速排斥和跨立)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

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

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

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

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

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

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

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

使用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

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav