`

计算几何_半平面求交

阅读更多

 

const double eps = 1e-8;
const double inf = 1e30;
int sign(double d){
	return d < -eps ? -1 : (d > eps);
}
struct point{
	double x, y;
	point(double _x=0, double _y=0) : x(_x), y(_y) {}
	void read(){
		scanf("%lf%lf", &x, &y);
	}
};
//直线p1-p2和直线a*x+b*y+c=0的交点
point intersect(point p1, point p2, double a, double b, double c){
	double u = fabs(a * p1.x + b * p1.y + c);
	double v = fabs(a * p2.x + b * p2.y + c);
	return point((p1.x * v + p2.x * u) / (u + v), (p1.y * v + p2.y * u) / (u + v));
}
//求经过st和ed(保证这两个点不相等)的直线a*x+b*y+c=0的三个参数
void tran(point st, point ed, double& a, double& b, double& c){
	a = st.y - ed.y;
	b = ed.x - st.x;
	c = (ed.y - st.y) * st.x - (ed.x - st.x) * st.y;
}
//多边形类
struct poly{
	static const int N = 1005; //点数的最大值
	point ps[N+5]; //逆时针存储多边形的点,[0,pn-1]存储点
	int pn;  //点数
	poly() { pn = 0; }
	//加进一个点
	void push(point tp){
		ps[pn++] = tp;
	}
	//第k个位置
	int trim(int k){
		return (k+pn)%pn;
	}
	void clear(){ pn = 0; }
};

//求该凸多边形org(确保org的点是逆时针方向的)在半平面a*x+b*y+c < 0 的部分
poly incise(poly org, double a, double b, double c){
	poly ans;
	point* ps = org.ps;
	int i;
	for(i = 0; i < org.pn; i++){
		if(sign(a*ps[i].x+b*ps[i].y+c) < 1){
			ans.push(ps[i]);
		}else{
			int g = org.trim(i-1);
			if(sign(a*ps[g].x+b*ps[g].y+c) < 0){
				ans.push(intersect(ps[g], ps[i], a, b, c));
			}
			g = org.trim(i+1);
			if(sign(a*ps[g].x+b*ps[g].y+c) < 0){
				ans.push(intersect(ps[g], ps[i], a, b, c));
			}
		}
	}
	return ans;
}
//求该凸多边形org(确保org的点是逆时针方向的)在st-->ed的左边(即从st看向ed时的左手边)的部分
poly incise(poly org, point st, point ed){
	double a, b, c;
	point tp;
	tran(st, ed, a, b, c);
	//tp是st-->ed的左边的半平面的一个代表点
	tp.x = st.x - (ed.y - st.y);
	tp.y = st.y + (ed.x - st.x);
	if(sign(a*tp.x+b*tp.y+c) < 0){
		return incise(org, a, b, c);
	}else{
		return incise(org, -a, -b, -c);
	}
}
分享到:
评论

相关推荐

    计算几何半平面交学习笔记

    计算几何学习笔记

    最小圆覆盖 半平面交 凸包 三维几何

    在计算几何中,半平面交经常用于构造复杂的形状,例如多边形。 凸包是包含一个集合内所有点且具有最少顶点的多边形。在二维空间中,可以使用Gift Wrapping算法(也称为Jarvis March)或者 Graham Scan来计算。凸包...

    计算几何 (李澎煦/朱泽园)

    其中,半平面交问题作为计算几何中一个基础且实用的课题,吸引了众多研究者的关注。李澎煦和朱泽园两位专家针对此问题进行了深入研究,并提出了各自的算法和应用案例。 首先,李澎煦的研究工作将目光聚焦于半平面交...

    7、省选+NOI-第七部分 计算几何_2020.08.27.pdf

    5. **半平面交、旋转卡壳、三角剖分**:用于解决特定类型的几何问题。 ### 总结 以上内容覆盖了计算机科学领域中非常重要的知识点,特别是针对编程竞赛中的高级主题进行了详细的梳理。这些知识不仅对于参加NOIP、...

    半平面交得算法及其应用

    针对半平面交的计算问题,有两种主要的算法策略:联机算法和分治算法。 ##### 联机算法 **算法描述**: 1. **初始化**:将整个平面视为初始的区域 \(A\)。 2. **迭代处理**:对于每个半平面 \(H_i\)(\(i = 1, 2,...

    算法合集之《半平面交的算法及其应用》

    《半平面交的算法及其应用》是一篇关于算法理论和技术的文章,主要探讨了如何处理半平面交的问题,以及这些问题在实际应用中的场景。半平面在二维平面上被定义为一条直线及其一侧的部分,通常可以用一个不等式ax + ...

    ACM计算几何基础模板,杭电老学长精心整理.pdf

    描述部分提到了点、线、多边形、凸多边形、圆、半平面交等算法的板子,这代表了计算几何在竞赛中的应用范畴。一个板子通常是指一个代码模板,包含了实现特定算法的基础代码框架和函数,可以在解决类似问题时直接使用...

    MIT的计算几何教程

    其次,计算几何涉及的主要问题包括:最近点对查找、多边形遍历、碰撞检测、求交问题、三角剖分等。这些问题在实际应用中有着广泛的需求。例如,最近点对查找常用于图形渲染中的光照计算;多边形遍历则对于理解和处理...

    acm之半平面交,很少有的好资源

    在计算机科学领域,尤其是在算法竞赛中,掌握半平面交算法对于解决复杂的几何问题至关重要。本文将深入探讨半平面交算法,剖析其在ACM竞赛中的应用,并通过实例进一步说明其应用价值。 首先,我们要明确什么是半...

    ACM计算几何模板

    ### ACM计算几何模板知识点概述 本文档是一份详尽的计算几何模板,共计74页,涉及了计算几何领域的多个方面,包括基本的几何公式、直线与线段处理方法、多边形操作、三角形特性分析、圆的相关计算、球面几何以及三...

    算法文档无代码半平面交的算法及其应用

    标题和描述提到了“算法文档无代码半平面交的算法及其应用”,这表明该文档可能是一篇关于计算几何领域中半平面交问题的理论和应用分析,但不包含实际代码实现。半平面交是计算机图形学和计算几何中一个重要的问题,...

    计算几何算法与应用 国外教材编译

    以实例为基础,运用计算几何知识分析 线段求交、布尔运算、三角剖分、半平面求交、Vonoroi图、凸包问题、K-D数....

    CGAL 计算几何算法库

    1. **数据结构**:CGAL提供了一些基本的数据结构,如Kd树、半平面交数据结构、多边形网格等,这些数据结构对于高效地存储和操作几何对象至关重要。 2. **2D几何算法**:包括点定位、线段交点检测、凸包问题、最近点...

    计算几何常用函数模版(转载)

    计算几何是计算机科学中的一个重要分支,它涉及到二维和三维空间中的几何对象的处理。这篇文档提供了计算几何中一些常见的函数模板,涵盖了点、线段、多边形、圆和矩形的基本运算,以及一些实用的算法。以下是这些...

    poj2451半平面交

    计算几何半平面交,poj2451 一题是模版题,这里的代码可以作为模版使用,速度比较快

    半平面交的新算法及其实用价值_朱泽园.ppt

    半平面交问题是一个重要的计算机科学领域内的几何计算问题,它涉及到如何找到一组直线(或半平面)在平面上的公共部分。这个问题在图形学、路径规划、数据结构和算法设计等多个方面都有广泛应用。朱泽园的论文《半...

    计算几何-算法与应用

    本章首先介绍了铸造中的几何问题(第4.1节),然后详细讲解了半平面求交(第4.2节)、递增式线性规划(第4.3节)和随机线性规划(第4.4节)等技术。这些方法能够帮助制造商在满足各种约束条件的同时,寻找到最优的...

    计算几何PPT

    可以通过二分搜索结合半平面交的方法来解决。 - **POJ1981 Circle and Points**: 此题要求给定半径 `r` 和一组点,找到最多可以包含多少个点的圆。可以通过枚举所有可能的中心点,并检查每个点是否在圆内的方法来...

    计算几何专题WelcomeToPKUJudgeOnline计算几何专题欢迎来到北大在线评测.ppt

    半平面的交是计算几何中的难题,因为可能需要处理大量的交点。基本的解决方法可能达到O(n^2)的时间复杂度,但更高效的算法如扫线法可以将其优化到O(nlogn)。在实际应用中,例如判断两个点集(如黑色点和白色点)的...

Global site tag (gtag.js) - Google Analytics