计算几何的常用算法
1. 矢量减法
设二维矢量 P = (x1,y1) ,Q = (x2,y2)
则矢量减法定义为: P - Q = ( x1 - x2 , y1 - y2 )
显然有性质 P - Q = - ( Q - P )
如不加说明,下面所有的点都看作矢量,两点的减法就是矢量相减;
2.矢量叉积
设矢量P = (x1,y1) ,Q = (x2,y2)
则矢量叉积定义为: P × Q = x1*y2 - x2*y1 得到的是一个标量显然有性质 P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q )
如不加说明,下面所有的点都看作矢量,点的乘法看作矢量叉积;
叉乘的重要性质:
> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q < 0 , 则P 在Q的逆时针方向
> 若 P × Q = 0 , 则P 与Q共线,但可能同向也可能反向
3.判断点在线段上
设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内
4.判断两线段是否相交
我们分两步确定两条线段是否相交:
(1). 快速排斥试验
设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交;
(2). 跨立试验
如果两线段相交,则两线段必然相互跨立对方,如图1所示。在图1中,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
5.判断线段和直线是否相交
如果线段 P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0
6.判断线段、折线、多边形是否在矩形中
因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。
7.判断矩形是否在矩形中
只要比较左右边界和上下边界就可以了。
8.判断圆是否在矩形中
圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。
9.判断点是否在多边形中
以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交,有些情况下交点只能计算一个,有些情况下交点不应被计算(自己画个图就明白了);如果L和多边形的一条边重合,这条边应该被忽略不计。为了统一起见,我们在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。由此得出算法的伪代码如下:
以P为端点,作从右向左的射线L;
for 多边形的每条边s
do if P在边s上
then return true;
if s不是水平的
then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
then count ← count+1
else if s和L相交
then count ← count+1;
if count mod 2 = 1
then return true
else return false;
其中做射线L的方法是:设P'的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),则P和P'就确定了射线L。这个算法的复杂度为O(n)。
10.判断线段是否在多边形内
线段在多边形内的一个必要条件是线段的两个端点都在多边形内;如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边形外。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交;
线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序,这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形内。证明如下:
命题1:
如果线段和多边形的两相邻交点P1 ,P2的中点P' 也在多边形内,则P1, P2之间的所有点都在多边形内。
证明:
假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P'之间,因为多边形是闭合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P'属于多边性内部,P1-Q-P'完全连续,所以P1Q和QP'一定跨越多边形的边界,因此在P1,P'之间至少还有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕
由命题1直接可得出推论:
推论2:
设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多边形内。
在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段上就可以了。
至此我们得出算法如下:
if 线端PQ的端点不都在多边形内
then return false;
点集pointSet初始化为空;
for 多边形的每条边s
do if 线段的某个端点在s上
then 将该端点加入pointSet;
else if s的某个端点在线段PQ上
then 将该端点加入pointSet;
else if s和线段PQ相交 // 这时候可以肯定是内交
then return false;
将pointSet中的点按照X-Y坐标排序,X坐标小的排在前面,
对于X坐标相同的点,Y坐标小的排在前面;
for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
then return false;
return true;
这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n,所以最多是常数级的复杂度,几乎可以忽略不计。
11.判断折线在多边形内只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,则复杂度为O(m*n)。
12.判断多边形是否在多边形内只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。
13.判断矩形是否在多边形内将矩形转化为多边形,然后再判断是否在多边形内。
14.判断圆是否在多边形内只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。
15.判断点是否在圆内计算圆心到该点的距离,如果小于等于半径则该点在圆内。
16.判断线段、折线、矩形、多边形是否在圆内因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。
17.判断圆是否在圆内
设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r1<r2则O2不可能在O1内;否则如果两圆心的距离大于r1 - r2 ,则O2不在O1内;否则O2在O1内。
18.计算点到线段的最近点
如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;
如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt2,斜率为:
k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );
该直线方程为:
y = k* ( x - pt1.x) + pt1.y
其垂线的斜率为 - 1 / k,
垂线方程为:
y = (-1/k) * (x - point.x) + point.y
联立两直线方程解得:
x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x - pt1.x) + pt1.y;
然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足的距离,选择距离垂足较近的端点返回。
19.计算点到折线、矩形、多边形的最近点只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。
20.计算点到圆的最近距离
如果该点在圆心,则返回UNDEFINED
连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为centerPoint.x - radius 或 centerPoint.x + radius, 如图4 (a)所示;如果PO平行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为centerPoint.y + radius 或 centerPoint.y - radius
如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,这时直线PO斜率为
k = ( P.y - O.y )/ ( P.x - O.x )
直线PO的方程为:
y = k * ( x - P.x) + P.y
设圆方程为:
(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2,
联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。
21.计算两条共线的线段的交点
对于两条共线的线段,它们之间的位置关系有图5所示的几种情况。图5(a)中两条线段没有交点;图5 (b) 和 (d) 中两条线段有无穷焦点;图5 (c)中两条线段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了line2的两个端点,则是图5(d)的情况,两线段有无穷交点;如果line1只包含line2的一个端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图5(c)的情况,这时两线段只有一个交点,否则就是图5(c)的情况,两线段也是有无穷的交点;如果line1不包含line2的任何端点,则是图5(a)的情况,这时两线段没有交点。
22.计算线段或直线与线段的交点
设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。
1.首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。
2.如果P1和P2横坐标相同,即L0平行于Y轴
a)若L1也平行于Y轴,
i.若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
ii.否则说明L0和L1平行,他们没有交点;
b)若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交点纵坐标;
3.如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;
4.如果P1和P2纵坐标相同,即L0平行于X轴
a)若L1也平行于X轴,
i.若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
ii.否则说明L0和L1平行,他们没有交点;
b)若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交点横坐标;
5.如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;
6.剩下的情况就是L1和L0的斜率均存在且不为0的情况
a)计算出L0的斜率K0,L1的斜率K1 ;
b)如果K1 = K2
i.如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
ii.如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
c)联立两直线的方程组可以解出交点来
说明:这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部看作直线来考虑。
23.求线段或直线与折线、矩形、多边形的交点分别求与每条边的交点即可。
24.求线段或直线与圆的交点
设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。
1.如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步
2.如果L平行于Y轴,
a)计算圆心到L的距离dis
b)如果dis > r 则L和圆没有交点;
c)利用勾股定理,可以求出两交点坐标,如图6(a)所示;但要注意考虑L和圆的相切情况
3.如果L平行于X轴,做法与L平行于Y轴的情况类似;
4.如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;
5.如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。
上一篇: eslint 缓存配置-摘要
推荐阅读
-
计算几何的常用算法
-
2021年理论计算领域的最高荣誉--哥德尔奖授予了两位中国学者!两位中国学者获奖,AdaBoost 算法也曾获奖。
-
JS 编写计算 24 点的算法
-
Python 计算二十一点游戏的枚举算法
-
计算 24 点的常用方法
-
前端算法入门 I:常用于补习算法问题的基本 JS 知识
-
数值建模中常用的一系列算法--整数线性规划(分支-边界法)、整数非线性规划(蒙特卡罗法)
-
三种主要 Python 模型和十种最常用的算法实例发现
-
深度学习最常用的学习算法:亚当优化算法
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果