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

平面分割问题c++
平面分割问题是计算几何中的一个经典问题，它的基本思想是将平面上的点集分割成若干个不相交的区域。

在c++中，我们可以使用多种算法来解决这个问题，例如扫描线算法，半平面交算法等等。

这些算法的实现都需要对点进行排序，对线段进行比较，判断点是否在多边形内部等等操作。

具体来说，扫描线算法是利用扫描线不断水平扫描平面上的点，当遇到线段时，通过比较线段的端点坐标来确定线段与扫描线的交点，然后根据交点的位置关系来更新当前扫描线上的区域。

半平面交算法则是通过不断添加半平面来逐步构建出多边形的边界，最终得到分割后的区域。

总之，平面分割问题在计算几何中具有重要的应用价值，它的解决需要借助于一些基本的数据结构和算法，如点、线段、多边形的表示方法，排序、比较、判定等等。

对于c++程序员来说，熟练掌握这些技术是非常重要的。

- 1 -。

半动态矩形交查询算法
高静波;李新友
【期刊名称】《软件学报》
【年(卷),期】1997(008)008
【摘要】本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O （nlogM）.二维查询算法的查询时间复杂度是O（log2M＋k），更新时间复杂度是O（log2Mlogn），空间复杂度是O（nlog2M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.【总页数】8页(P577-584)
【作者】高静波;李新友
【作者单位】清华大学计算机科学与技术系CAD中心;清华大学计算机科学与技术系CAD中心
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.基于矩形编码的抖动半调图像无损压缩算法 [J], 张萍;孔月萍;江永林
2.基于线段与线段求交的矩形窗口裁剪算法 [J], 刘中琦;秦敬超;聂如春
3.求解二维正交矩形布局问题的动态填空启发式算法 [J], 孙宝金;贺良华
4.基于动态参数差分进化算法的多约束稀布矩形面阵优化 [J], 姚敏立; 王旭健; 张峰干; 戴定成
5.基于动态择优定序的矩形件优化排板算法 [J], 鞠云鹏;常德功
因版权原因，仅展示原文概要，查看原文内容请购买。

半平面交的算法及其应用基本概念半平面：平面上的直线及其一侧的部分，在直角坐标系中可由不等式ax+by+c>=0确定。

在一个有界区域里（在实际计算时不妨设一个足够大的边界），半平面或半平面的交是一个凸多边形区域。

n个半平面的交H1∩H2∩…∩H n是一个至多n条边的凸多边形。

算法半平面交的联机算法procedure intersection of half-planes输入：n个半平面H1,H2,…H n对应的不等式组a i x+b i y+c i>=0，i=1,2,3…n输出：H1∩H2∩…∩H n初始化区域A为整个平面依次用直线a i x+b i y+c i=0，i=1,2,…n切割A，保留使不等式a i x+b i y+c i>=0成立的部分输出A本算法的时间复杂度为O(n*n)，并具有联机的优点。

半平面交的分治算法假设可以在O(m+n)的时间内将m个半平面的交和n个半平面的交合并，则可以有一种O(n*log(n))的分治算法求半平面的交。

Procedure intersection of half-plane (D&C)输入：n个半平面H1,H2,…H n对应的不等式组a i x+b i y+c i>=0，i=1,2,3…n输出：H1∩H2∩…∩H n将H1…H n分成两个大小近似相等的集合在每个子问题中递归地计算半平面的交合并两个凸多边形区域形成H1∩H2∩…∩H n所以问题的关键就是怎样在O(m+n)的时间里求两个凸多边形的交。

形沿平行于y轴方向切割成至多O(m+n)个梯形区域，每两个梯形区域的交可以在O(1)时间内解决。

为了便于操作，确定凸多边形采用了一种特殊的方法。

可以看出凸多边形上方和下方的顶点分别构成了一个x坐标递增序列。

将这两个序列中的顶点分别作为一个链表存储,得到确定凸多边形区域的上界和下界。

算法：procedure intersection of convex polygon输入：两个凸多边形区域A、B输出：C=A∩B1.将两个凸多边形的顶点x坐标分类，得到序列x i,i=1…p2.初始化区域C为空。

算法合集之《欧几里得算法的应用》欧几里得算法，又称为辗转相除法，是求两个正整数的最大公约数的一种简便有效的方法。

它的基本原理是通过一系列的除法运算，将两个数逐渐缩小为它们的公约数，最终得到最大公约数。

在实际应用中，欧几里得算法有着非常广泛的应用。

以下将介绍几个常见的应用场景。

首先，欧几里得算法可以用来简化分数。

假设我们有一个分数a/b，其中a和b都是正整数，并且a大于b。

我们可以使用欧几里得算法求出a和b的最大公约数gcd(a, b)，然后将a和b都除以gcd(a, b)。

这样可以得到一个简化的分数，它与原来的分数等价，但是分子和分母的数值都更小。

这在数学计算和编程中都非常有用，可以提高计算效率和准确性。

其次，欧几里得算法可以用来判断两个数是否互质。

如果两个数a和b的最大公约数是1，那么我们称它们为互质数。

互质数在数论和密码学等领域中有着重要的应用。

例如，在RSA密码算法中，互质数的选择是非常关键的一步，以提高密码的安全性。

此外，欧几里得算法还可以用来求解线性方程。

考虑一个一元线性方程ax + by = c，其中a、b、c都是已知的整数。

如果方程有整数解，那么x和y的取值是有限的。

欧几里得算法可以用来求解这个方程的一个特殊解，我们称之为整数解。

具体方法是通过一系列的除法运算，将方程转化为一个简化的形式。

然后我们可以利用整数解的性质，通过修正系数的方法，逐步缩小方程的规模，最终得到方程的所有整数解。

最后，欧几里得算法还可以用来求解模线性方程组。

模线性方程组是一组形如ax ≡ b (mod m)的方程，其中a、b、m都是已知的整数。

模线性方程组在密码学和通信中有着广泛的应用。

欧几里得算法可以用来求解这个方程组的一个特殊解，我们称之为模线性方程组的基础解集。

基础解集可以通过一系列的除法运算和模运算，将方程组转化为一个简化的形式。

然后我们可以利用基础解集的性质，通过修正参数的方法，逐步缩小方程组的规模，最终得到方程组的所有解。

•Step 1: Separate the h-planes into two sets. One has polar angles of (-½π, ½π], the other has those of (-π, -½π]∪(½π, π].•将半平面分成两部分，一部分极角范围(-½π, ½π]，另一部分范围(-π, -½π]∪(½π, π]•Step 2: Consider the set of h-planes in (-½π, ½π] (the other set should also go through step 3 and 4 similarly). Sort them by the polar angle. For the h-planes with the same polar angle, we can keep only one down (delete all others) according to the constant of these h-planes •考虑(-½π, ½π]的半平面(另一个集合类似地做Step3/4)，将他们极角排序。

对极角相同的半平面，根据常数项保留其中之一。

•Step 3.1: Starting from two h-planes with the least polar angle, compute their intersection.Push them two into a stack.•从排序后极角最小两个半平面开始，求出它们的交点并且将他们押入栈。

•Step 3.2: Each time, add one more h-plane by increasing order of polar angles, and calculate the intersection of it and the top h-plane in stack.•每次按照极角从小到大顺序增加一个半平面，算出它与栈顶半平面的交点。

c xlove的程序员之路艰辛的旅途，but never give upH DU 3761 Jungle Outpost（二分+半平面交）分类： ACM_计算几何 2012-08-28 11:10 117人阅读 评论(0) 收藏举报转载请注明出处，谢谢/acm_cxlove/article/details/7854526 by---cxlove题目：给出一个凸多边形，顶点为一些防御塔，保护范围是凸多形内部，不包括边界，在多边形内部选择一点，使得对方至少需要摧毁的塔防数量最多。

/showproblem.php?pid=3761首先感谢晴天哥哥的悉心指导。

首先需要明白的是一个问题，对于摧毁一定数量的塔防，怎样的方案是使得剩下的保护范围最小。

结论是摧毁连续多个顶点，这样是最优的，可以尝试证明一下。

对于5个顶点的多边形，删除两个顶点，可以尝试连续两个顶点，以及间隔一个顶点。

由于原多边形是凸边形，所以还是比较容易得到连续顶点最优，同理可得其它情况。

题目要求的是使对方尽可能多的摧毁至少需要摧毁的塔防，联系复杂度等等问题二分答案，然后判断是否存在一个区域，保证能受保护。

对于每一次二分，枚举删除连续的顶点，形成新的边界，通过半平面交判断是否存在可行区域。

注意：边界上的点是不受保护的，所以只需要判断多边形的核的面积即可。

当剩余的点在2个以及以下是，是肯定可行的。

避免处理麻烦。

再看一看题目的范围，5W个顶点，半平面交至少肯定是要用nlgn的算法，其实听了晴天哥哥的说明，才知道，这题二分+半平面交的nlgnlgn的算法都要卡掉，顿时吓尿了，难道有o(n)的半平面交算法多亏晴天哥哥的指导，其实zzy的半平面交算法是将所有向量按极角排序之后，维护了一个双端队列，排序部分达到nlgn的复杂度，其实后面只需要o(n)。

然后再看这题，原先给的凸多形是有序的，而之后我们的连线的极角也是循环有序的，线性扫描一遍，找到最小的极角，便可以依次得到有序的向量，O(n)的线性sort,晴天哥哥太神了。

最全“⼀半”模型结论，掌握这些⾯积计算不再难
⼀半模型是等积变换模型的延伸，但是学⽣往往遇到此类题⽬之后很难想到⽤等积变换的⽅
法，所以专门提炼出⼀半模型，帮助学⽣加深此部分知识点的理解，提⾼⾯积计算的应⽤能
⼒。

长⽅形“⼀半”模型
下图当中阴影均占长⽅形ABCD的⼀半，如果把长⽅形换作平⾏四边形，下⾯结论仍然成⽴，只
是在考察当中多以长⽅形形式出现，如果换作平⾏四边形也要理解。

进⼀步可得如下阴影占长⽅形ABCD⾯积的四分之⼀：
如果把P点移动到下图位置，也就是P点在长⽅形两条长所在直线的外部，那可得阴影⾯积差
（⼤减⼩）占长⽅形ABCD⾯积的⼀半。

三⾓形“⼀半”模型
解释⼀下第⼆⾏第⼀个图形，三⾓形的三条中线在三⾓形内部交于⼀点，该点称作重⼼，三条
中线把三⾓形分成6个⼩三⾓形，这6个⼩三⾓形的⾯积是相等的，因此任取3个三⾓形的⾯积和
占三⾓形ABC⾯积的⼀半。

四边形“⼀半”模型
这三个结论⽐较简单，不⽤过多解释，其中中间的四边形对边中点连线把四边形分成四块，这
四块刚好可以拼成⼀个平⾏四边形。

感兴趣的可以拼⼀下试试。

梯形“⼀半”模型
梯形是四边形，所以四边形具备的⾯积性质梯形也具备，不过梯形的⼀组底边平⾏，还具备以
下性质，其中最后⼀个图形表⽰在两腰中点连线上任意取⼀点，所得图中阴影三⾓形占梯形⾯
积的⼀半，该点只要在腰中点连线上，在梯形外部也成⽴。

特殊“⼀半”模型
下图当中的正⽅形和长⽅形的边是平⾏的。

如果不平⾏则不成⽴。

应用半平面解答的边界元法求解位势问题
徐汉忠
【期刊名称】《河海大学学报（自然科学版）》
【年(卷),期】1990(000)005
【摘要】传统的边界元法求解位势问题,均采用拉普拉斯方程的基本解.本文将位势问题的解答设定为有限个半平面解答的线性组合,它精确满足城内方程.然后令解答在N个边界点满足给定的边界条件,求解设定解答中的待定常数.该方法简单,避免了奇异积分。

【总页数】1页(P110)
【作者】徐汉忠
【作者单位】无
【正文语种】中文
【中图分类】O351.3
【相关文献】
1.用自然边界元法计算位势问题的近边界位势梯度 [J], 牛忠荣;杨智勇;周焕林
2.位势问题的边界元法在光弹实验中的应用 [J], 赵奎;黄文钿;张小红
3.半平面体弹性问题的自然边界元法 [J], 李顺才;卓士创
4.用双层位势求解三维Helmholtz方程Neumann问题的边界元法 [J], 金朝嵩
5.半平面问题远域辐射阻尼的时域边界元法模拟研究 [J], 张梅;唐波;李宏军;郝文秀;龚海天
因版权原因，仅展示原文概要，查看原文内容请购买。

计算几何入门题(转)原来在文章里转的，现在放到计算几何专题中来：计算几何题的特点与做题要领：1.大部分不会很难，少部分题目思路很巧妙2.做计算几何题目，模板很重要，模板必须高度可靠。

3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。

如果代码一片混乱，那么会严重影响做题正确率。

4.注意精度控制。

5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。

因为整数不用考虑浮点误差，而且运算比浮点快。

一。

点，线，面，形基本关系，点积叉积的理解POJ 2318 TOYS（推荐）/JudgeOnline/problem?id=2318POJ 2398 Toy Storage（推荐）/JudgeOnline/problem?id=2398一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。

知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。

POJ 3304 Segments/JudgeOnline/problem?id=3304知识点：线段与直线相交，注意枚举时重合点的处理POJ 1269 Intersecting Lines/JudgeOnline/problem?id=1269知识点：直线相交判断，求相交交点POJ 1556 The Doors （推荐）/JudgeOnline/problem?id=1556知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。

POJ 2653 Pick-up sticks/JudgeOnline/problem?id=2653知识点：还是线段相交判断POJ 1066 Treasure Hunt/JudgeOnline/problem?id=1066知识点：线段相交判断，不过必须先理解“走最少的门”是怎么一回事。

POJ 1410 Intersection/JudgeOnline/problem?id=1410知识点：线段与矩形相交。

参数曲面与平面求交的一种新方法
张和明;柯映林
【期刊名称】《工程图学学报》
【年(卷),期】1995(000)002
【摘要】本文提出了一种新的参数曲面与平面求交算法，基于平面的半空间性质，通过参数域平面的二向线性插值，将求交问题转化为一系列简单的离散、判断、比较、排序等运算，能较好的解决曲面片内的交线不连续和交线丢失问题，算法简便，可靠性好，计算精度高，在ＮＣ自动编程中具有广泛的应用场合。

【总页数】7页(P31-37)
【作者】张和明;柯映林
【作者单位】不详;不详
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.两参数曲面求交线的一种新方法 [J], 刘雪梅
2.一种参数曲面与隐式曲面的求交算法 [J], 余正生;彭群生;马利庄
3.直线与参数曲面求交的一种有效算法 [J], 董方敏;袁国刚
4.双三次参数曲面求交的一种新方法 [J], 崔汉国;伍晓宇
5.参数曲面与平面的精确求交及其应用 [J], 张和明;张玉云;熊光楞;柯映林;程耀东因版权原因，仅展示原文概要，查看原文内容请购买。

半值法的原理与应用1. 原理介绍半值法（Half-Value Method）是一种常用的数值计算方法，主要用于求解方程的根。

其基本原理是通过迭代的方式逼近方程的根，直到达到一定的精度要求。

2. 算法步骤使用半值法求解方程的根主要包括以下步骤：•步骤1: 选择一个初始的区间[a, b]，确保方程在该区间内存在唯一根，并满足f(a) * f(b) < 0。

•步骤2: 计算区间的中点c = (a + b) / 2。

•步骤3: 计算函数在中点处的取值f(c)。

•步骤4: 判断f(c)与0的关系，如果f(c)接近0，则c即为方程的根。

如果f(c)与0的符号相同，则更新区间：如果f(c)与f(a)的符号相同，则将c赋值给a；如果f(c)与f(b)的符号相同，则将c赋值给b。

•步骤5: 判断终止条件，如果满足指定的精度要求或迭代次数达到预设值，则停止迭代。

否则，返回步骤2。

3. 应用场景半值法广泛应用于数值计算和方程求根的领域，特别适用于求解非线性方程的根。

以下是一些常见的应用场景：•方程求根: 半值法可以用于求解各种类型的方程，如代数方程、三角方程、指数方程等。

通过设置合适的初始区间和精度要求，可以得到方程的近似解。

•数值计算: 半值法可以用于求解连续函数的零点、极值点等数值计算问题。

通过迭代的方式逼近函数的根，可以得到函数在给定区间内的性质和特征。

•优化问题: 半值法可以用于求解优化问题的最优解。

通过将优化问题转化为方程求根问题，可以利用半值法求取约束条件下的最优解。

4. 优缺点分析半值法作为一种简单而有效的数值计算方法，具有以下优点：•易于实现: 半值法算法简单，易于理解和实现。

只需要通过迭代的方式逼近方程的根，无需涉及复杂的数学推导或定理证明。

•适用性广泛: 半值法可以用于求解各种类型的方程和问题，适用性广泛。

无论是代数方程、三角方程还是更复杂的函数问题，都可以通过半值法进行求解。

•收敛速度较快: 通过合理的初始区间选择和精度要求设置，半值法可以在较短的迭代次数内得到满足精度要求的近似解。

半平面交的新算法及其实用价值Keywords: Half-plane, Intersection, Feasible Region, Algorithm, Polygon, Practical Abstract主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。

最重要的是，我将介绍的算法非常便于实现.§1 introduces what half-plane intersection is. §2 prepares a linear algorithm for convex polygon intersection (abbr. CPI). Equipped with such knowledge, a common solution for HPI is briefly discussed in §3. Then, my new algorithm emerges in §4 detailedly. Not only as a conclusion of the whole paper, §5 also discuss its further usage practically and compares it with the older algorithm described in §3.§1什么是半平面交. §2凸多边形交预备知识. §3简要介绍旧D&C算法. §4揭开我的新算法S&I神秘面纱. §5总结和实际运用.Timestamps: Came up with it in April 2005; implemented partly in June 20051; problem set in July 20052; publicized as a post in USENET, November 6, 20053.1 The sub-problem of HPI appeared in USA Invitational Computing Olympiad contest.1.IntroductionA line in plane is usually represented as ax+by=c. Similarly, its inequality form ax+by≤c represents a half-plane (also named h-plane for short) as one side of this line. Notice that ax+by≤c and -ax-by≤-c show opposite h-planes unlike ax+by=c and -ax-by=-c. Half-Plane Intersection (abbr. HPI) considers the following problem:众所周知，直线常用ax+by=c表示，类似地半平面以ax+by≤(≥)c为定义。

算子半群及应用
《算子半群及应用》这些应用包括在偏微分方程和控制理论中的经典应用、抽象Cauchy问题的L一最大正则性和H6lder正则性、不适定抽象Cauchy问题的正则化等，其中在偏微分方程中的应用是主要的，分布在多个章节。

此外，本书还给出了适当注记和适量习题。

本书内容主要包括：预备知识、半群的基本知识及简单应用、范数连续半群及其子类、逼近和扰动、谱映射定理和稳定性、非齐次Cauchy问题、半线性方程的Cauchy问题及应用、控制理论中的半群、抛物型方程反问题。

《算子半群及应用》可以作为泛函分析、偏微分方程、动力系统、计算数学、控制论方向及理工科相关方向研究生的教材或教学参考书，也可作为相应领域的教师和科研人员的参考书。

本书由黄永忠编著。