计算几何-2007

点在凸多边形内外的判定点在凸多边形内外的判定1. 引言点在凸多边形内外的判定是几何学中的一项基础知识。

它在计算机图形学、地理信息系统以及其他领域中都有很广泛的应用。

判断一个点是否在凸多边形内部可能会涉及到一些数学算法和几何概念，但只要我们理解了其原理，就能够轻松地进行点的位置判断。

2. 原理解析2.1 凸多边形的定义凸多边形是指没有凹陷部分的多边形。

它的内角都小于180度，并且多边形中的任意两点之间的线段都在多边形内部。

这个定义非常关键，因为只有凸多边形才能使用简单的算法进行点的位置判断。

2.2 射线法射线法是一种常见且简单有效的点在凸多边形内外判定方法。

其基本思想是从点向多边形外部发射一条射线，判断射线与多边形的交点数量。

如果交点数量为奇数，则点在多边形内部，否则在外部。

射线法可以通过以下步骤进行：2.2.1 选取一条水平线，使得它能够穿过待判断的点。

2.2.2 从待判断的点沿着水平线方向发射一条射线。

2.2.3 分别计算射线与多边形的各个边的交点。

2.2.4 统计交点的数量。

2.2.5 如果交点数量为奇数，则点在多边形内部；如果交点数量为偶数，则点在多边形外部。

3. 实例分析为了更好地理解点在凸多边形内外判定的过程，我们来看一个简单的例子。

假设有一个凸多边形，顶点分别为A、B、C、D，点P是我们待判断的点。

3.1 射线的选取我们选取一条水平线，穿过待判断的点P。

3.2 射线的发射与交点计算从点P沿着水平线方向发射射线。

射线与多边形的各个边的交点如下：- 射线与边AB的交点为R1；- 射线与边BC的交点为R2；- 射线与边CD的交点为R3；- 射线与边DA的交点为R4。

3.3 交点数量统计统计交点的数量，我们可以得到以下结果：- 交点数量为奇数，点P在多边形内部。

4. 个人观点与总结对于凸多边形内外判定，射线法是一种简单而有效的方法。

射线法的思路清晰，易于理解和实现。

它在实际应用中具有一定的优势，特别是在计算机图形学中。

2007级《解析几何》课程试题（A 卷）合分人： 复查人：一、填空题（每空3分，共36分）1．已知仿射坐标系下，a =)3,2,1(-，),5,0,1(=b )3,2,1(--=c，则c b a +-2的坐标为 ， c b a,,是否共面？答 。

2． 通过点 )2,0,1(-和 )5,1,3(-，且平行于x 轴的平面方程为 。

3． 直线⎩⎨⎧=+--=--03302z y x z y x 的对称式方程是 。

4． 在直角坐标系下，无心二阶曲面的标准方程有 种标准形式，其中和 是直纹曲面。

5． 在射影平面上，取射影坐标系{}E O O O ;,,21，由A(2,0,1), B(0,3,1)所决定的直线的坐标为 。

6． 空间中的等距变换，或者是刚体运动，或者是在刚体运动后，再作一次 ；而且等距变换下，向量的长度 。

7．在直角坐标系下，抛物柱面)0(22≠=p py x 的非渐进主方向为 ，主径平面为 。

证明：三角形的三条中线长度的平方和等于三边长度平方和的3/4 。

已知b a B A 2-=, b a D A 3-=. 其中 ,5=a ,3=b 6/),(π=∠b a， 求平行四边形ABCD 的面积。

二、（共12分）三、（共8分）求经过直线 ⎩⎨⎧=++-=+-+023402:1z y x z y x l 且与直线 ⎩⎨⎧=+-=31:2y x z l 平行的平面方程。

四、（共10分）已知准线方程为： ⎪⎩⎪⎨⎧==-+1194222z z y x ，母线平行于直线z y x ==，求柱面的方程。

六、（共10分）给定二阶曲面0142222:222=------+∑x yz xz xy z y x（1） 求曲面上渐进方向满足的方程；（4分） （2） 求与平面 012=+-+z y x 平行的径平面及其共轭方向。

（6分）五、（共10分）七、（共14分）在直角坐标系下，给定二阶曲面014 4 8 126 2 2 5:222=+-+--+-++∑z y x yz xz xy z y x（1 求∑的主方向； （6分）（2） 求出∑的标准方程并说明它是什么图形；（4分） （3） 求将∑化为标准方程的直角坐标变换。

2007全国高中数学联赛平面几何：证法2：充分性，若P 是△ABC 的垂心，由于△BDF 、△CDE 的外心分别是BP 、CP 的中点，因此，△ABC 的九点圆过F E O O ,,,21，即F E O O ,,,21四点共圆。

必要性。

若F E O O ,,,21四点共圆，则 180121=∠+∠EFO E O O 。

因为21,O O 分别是BP 、CP 的中点，所以21O O ∥BC ，且BCA APE AFE ∠=∠=∠， 所以E PO P O O E O O 22121∠+∠=∠PCE PCB ∠+∠=2PCE BCA ∠+∠=，11180BFO AFE EFO ∠-∠-=∠PBF BCA ∠-∠-=180，故ECP FPB ∠=∠。

方法1：由于△BP F ∽△CPE ，则CB DACDAB PEPF CDBP cos cos sin sin =∠∠==。

因为AC AB <，所以1cos cos ≠CB 。

故点P 在阿波罗尼斯（Apolonius ）圆上。

注意到AD 在BC 的上方与该圆恰有一个交点，且△ABC 的垂心H 满足，CB H B DH C D CHBH cos cos sin sin =∠∠=，故P 与H 重合，即P 是△ABC 的垂心。

方法2：由ECP FBP ∠=∠cos cos ，可得BPAB APBPAB⋅-+2222CPAC APCPAC⋅-+=2222，所以ECPCP AC FBPAP AB S S CDBD ACPABP ∠⋅∠⋅==∆∆sin 21sin 21222222APCPADAP BP AB -+-+=2222222222)()(PD AD CDPDCDADPD AD BD PD BD AD --+++--+++=PDAD CDPD AD BD ⋅+⋅+=222222，于是BDPD AD BD ⋅+CDPD AD CD ⋅+=，从而)(DC BD DCBD PD AD CD BD -⋅⋅=-，因为0≠-DC BD ，所以ADDCBD PD ⋅=。

一种凸多边形的交、并求解算法黄俊华;闫遂军;朱小龙;李景文【摘要】凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列.提出了以顶点与多边形的空间拓扑关系为基础,将不同拓扑关系的顶点进行重新组合的方法来解决任意2个凸多边形交、并的求解问题.算法易于编程实现,能够较好的求解二维凸多边形区域各种情况的交与并,可为GIS应用中矢量多边形之间的关系计算提供算法基础.【期刊名称】《桂林理工大学学报》【年(卷),期】2007(027)004【总页数】4页(P589-592)【关键词】计算几何;凸多边形;相交;相并【作者】黄俊华;闫遂军;朱小龙;李景文【作者单位】武汉大学,遥感信息工程学院,武汉,430079;广西区国土资源厅,南宁,530023;桂林工学院,土木工程系,广西,桂林,541004;桂林工学院,土木工程系,广西,桂林,541004;桂林工学院,土木工程系,广西,桂林,541004【正文语种】中文【中图分类】TP301.6;P208研究2个平面凸多边形的交、并求解算法是GIS应用中矢量多边形之间关系计算的基本问题之一［1，2］.现有的一些算法虽然能够解决这一问题，但是它们多是以多边形的边与另外一个多边形的空间关系为依据，计算得到交、并多边形，不仅顶点序列维护困难，而且需要大量的存储空间.笔者从多边形的顶点与另外一个多边形的空间关系的角度考虑，将不同拓扑关系的顶点和2个多边形的交点进行合并，得到了结果多边形顶点序列，从而实现了凸多边形的交、并求解运算，较好的维护顶点序列的存储顺序.1 算法的描述1.1 简单凸多边形的定义平面多边形是由N个点V1，V2，V3，…，Vn首尾相连的闭合折线段表示，Vi(i=1，2，…，n)为多边形顶点，V1V2，V2V3，…，Vn-1Vn，VnV1为多边形的边.对于任意非相邻边不相交的多边形称为平面简单多边形.凸多边形是简单多边形的一种特例，如果简单多边形的任意顶点Vi(i=1，2，…，n)对应的多边形内角θi∈(0，π)，则称此多边形为平面简单凸多边形.除去凸多边形以外的简单多边形都是凹多边形.简单凸多边形是客观世界中空间实体常用的描述形式，其交、并求解算法是空间实体逻辑关系判断的常用方法.1.2 算法思想2个凸多边形在平面上存在的位置关系有:分离、包含、相交和相切.对于2个凸多边形为分离、包含和相切的情况，其交集和并集较容易表示出来.本文主要讨论2个凸多边形相交情况下的交、并的求解算法.算法的基本思想是:将参与求解过程的2个凸多边形的顶点集按照顶点与多边形的拓扑关系进行双向筛选，再将筛选出的2组顶点和2个多边形的交点，按照多边形顶点序列逆时针顺序存储的原则合并共同存储为一个顶点序列，即可得到结果多边形的顶点序列(图1).2 算法实现的过程2.1 凸多边形交集求解算法的实现过程多边形的顶点集采用变长数组进行表示，按照逆时针顺序存储顶点，在图2中，凸多边形的顶点序列表示为P(P1，P2，P3，…，Pn)和Q(Q1，Q2，Q3，…，Qn).图1 算法思想Fig.1 Basic idea of the algorithm图2 凸多边形Fig.2 Two convex polygons凸多边形交集求解算法的多边形顶点的筛选条件:判断顶点与另一个多边形的拓扑关系，如果顶点为内部点，则存储待用.定义点序列P_Q由多边形P的顶点序列中包含在多边形Q内部的顶点(图2中的P2，P3，P4)和多边形P、Q的交点(图2中的M1，M2)组成；定义点序列Q_P由多边形Q的顶点序列中在多边形P内部的顶点和多边形P、Q的交点组成.点序列P_Q、Q_P合并即可得到交集多边形的顶点序列.2.1.1 求解点序列P_Q和Q_P点序列P_Q的求解算法描述如下.Step 1:初始化i=1，n为多边形P当前的顶点数目，m为多边形Q当前的顶点数目；然后在顶点序列P、Q尾部分别插入点P1、Q1.Step 2:判断Pi是否在多边形Q内部，如果在，则将Pi点存储到点序列P_Q中. Step 3:定义变量j=1.Step 4:判断线段PiPi+1、QiQi+1是否有交点，如果有交点，则将交点插入到点序列P_Q中.Step 5:判断j是否与m相等，如果不相等，则执行j++，再跳回Step 4.Step 6:判断i是否与n相等，如果不相等，则执行i++，再跳回Step 2.Step 7:分别将顶点序列P、Q最后一个顶点(在Step 1中插入的P1、Q1)删除. Step 8:求解过程完成，退出.按照此算法的点序列P_Q为(M1，P2，P3，P4，M2)；同理可以得到点序列Q_P 为(Q1，M1，M2).2.1.2 合并点序列P_Q和Q_P合并点序列P_Q、Q_P即可得到多边形P、Q的交集多边形的顶点序列，合并过程中必须维护交集多边形顶点序列的逆时针存储方式，而多边形P、Q的交点是点序列P_Q、Q_P合并的依据.本文所采用的合并算法是将点序列Q_P的每个顶点插入到点序列P_Q中相应的位置，从而得到交集多边形的顶点序列.合并算法的步骤如下.Step 1:对点序列Q_P进行调整，调整的目标是让顶点序列中首顶点成为点序列P_Q中的一个顶点.调整的原则是:将首顶点取出来并将其后边的值依次向前移动一个位置，最后再将刚才取出来的顶点插入到末顶点后边.Step 2:对点序列P_Q进行调整，调整目标是使点序列P_Q的末顶点与点序列Q_P的首顶点相等，调整的原则同Step 1中的调整原则.Step 3:点序列Q_P的首顶点删除，后边的顶点向前.Step 4:判断点序列Q_P的首顶点是否包含在点序列P_Q的顶点集中，如果不包含，则将首顶点插入到点序列P_Q的末顶点后边，并跳回Step 3.Step 5:如果点序列Q_P的顶点集不为空，则跳回Step 2.Step 6:点序列P_Q即为多边形P、Q相交的结果多边形的顶点序列.按照算法运算，实例合并过程中状态演示如表1.表1 顶点序列合并过程演示Table 1 Union of ordered vertices2.1.3 存在的特殊情况及解决方法如图3所示，多边形P(P1，P2，P3，P4，P5)，多边形Q(Q1，Q2，Q3，Q4，Q5，Q6，Q7).如果按前面介绍的求解点序列P_Q、Q_P的算法计算，可以得到点序列P_Q(M1，P2，P3，M2，M3，P5，M4)，点序列Q_P(M1，M4，M2，Q6，M3).图3 算法中存在的特殊的情况Fig.3 Special case of the algorithm此时，点序列Q_P的顶点序列中M1和M4存储顺序违背了逆时针存储的原则，因此在上述算法的基础上对相关步骤进行了如下改进.(1)在Step 1中定义变量number初始化为0，用于标识一条线段与另一个多边形的交点个数.(2)在Step 4判断线段PiPi+1、QjQj+1的关系，如果存在交点则进行一次number++操作.(3)在Step 5后插入一步运算，即判断number的大小:当number＞1，将点序列P_Q的顶点集的最后number个顶点按照与顶点Pi的距离从小到大的顺序重新存储；当number≤1时，直接进入下一步.在下一步的操作中将number重置为0.用改进算法重新计算得到的点序列Q_P(M4，M1，M2，Q6，M3)，满足了存储顺序的要求.图4为改进后的算法流程图.2.2 凸多边形并集求解算法的实现凸多边形并集求解算法中多边形顶点的筛选条件为判断顶点与另一个多边形的拓扑关系，如果顶点为外部点，则存储待用.定义点序列P_Q由多边形P的顶点序列中包含在多边形Q外部的顶点和多边形P、Q的交点组成；定义点序列Q_P由多边形Q的顶点序列中在多边形P外部的顶点和多边形P、Q的交点组成.将点序列P_Q、Q_P进行合并就可以得出结果多边形的定点序列.并集求解算法中点序列P_Q的求解流程图与图4中交集求解算法中点序列P_Q的计算流程图不同之处:将流程图中(*)步的判断条件改为“Pi是否在多边形Q外部”，即如果Pi在多边形Q外部时，则将Pi点插入到点序列P_Q中.图4 交集求解算法中点序列P_Q的计算流程图Fig.4 Flowing chart of solvingP_Q如图2，凸多边形P(P1，P2，P3，…，Pn)和凸多边形Q(Q1，Q2，Q3，…，Qn).通过上面的算法可以得到点序列P_Q为(P1，M1，M2，P5，P6)；同理可以得到点序列Q_P为(M1，Q2，Q3，Q4，Q5，Q6，M2).点序列P_Q、Q_P的顶点合并后得到并集多边形的定点序列为(P5，P6，M1，Q2，Q3，Q4，Q5，Q6，M2).图3中的特殊情况也会在求并集的过程中出现，但是在求交集过程中对特殊情况的处理方法同样在此适用.凸多边形交、并求解算法的运行效果如图5所示.图5 算法的运行结果Fig.5 Results of the algorithm2.3 凸多边形交、并求解算法的扩展本文在对凸多边形的交、并问题研究过程中，对凹多边形的情况作了探讨:1)当运算的2个多边中有1个为凹多边形时，首先利用剖分算法［3，4］将凹多边形剖分为1个凸多边形集合，然后将剖分后得到的凸多边形集合的每一个元素与凸多边形进行求交、并求解运算.2)当运算的2个多边形都为凹多边形，将2个凹多边形分别剖分为凸多边形集合，然后将剖分后得到的2个凸多边形集合交叉进行交、并求解运算.图6a中，将凹多边形Q进行剖分，得到图6b，然后将剖分后的多边形1、2、3分别与凸多边形P求交.交集求解的结果由2个部分组成，它们分别是多边形1、2与多边形P求交的结果，如图6c.图6 凹多边形的交集运算Fig.6 Intersection of the concave polygon3 结论(1)本文提出的凸多边形的交、并求解算法能够较好的解决二维矢量多边形之间的关系计算问题，为GIS应用中几何图形的叠置分析计算提供参考.(2)算法采用Visual C++6.0编程实现，实例证明此算法不仅解决了顶点序列维护困难的问题，而且减少了存储空间，便于快速解决1∶N多边形之间的交、并求解问题.【相关文献】［1］Preparate F，Shamos putational Geometry:An Introduction［M］.Springer－Verlag，1985.［2］庞明勇，卢章平.计算两凸多边形的并集多边形及其面积的计算机算法与实现［J］.工程图学学报，2004(1):90－94.［3］王正旋.一个加权剖分简单多边形为凸多边形的算法［J］.计算机学报，1998，21(3):229－233.［4］肖忠辉.简单多边形凸单元剖分的编码算法［J］.计算机学报，1996，19(6):477－481.。

Using the research method of literature, meansof observation, behavioralapproach, con ceptual an alysis and the patter n of in formati on-seek ing of local and overseas were an alyzed and compared, Basic pattern strategies of tech no logy in formatio n-seeki ng2007年高考数学试题汇编一一立体几何（二）二、填空题19.（全国I ?理?16题）一个等腰直角三角形的三个顶点分别在正三棱柱的三条侧棱上。

已知正三棱柱的底面边长为 2,则该三角形的斜边长为【解答】一个等腰直角三角形 DEF 的三个顶点分别在正三棱柱的三条侧棱上，/EDF=90° ,已知正三棱柱的底面边长为 AB=2，则该三角形的斜边 EF 上的中线 DG= ',20.（全国n ?理?15题）一个正四棱柱的各个顶点在一个直径为 2cm 的球面上。

如果 正四棱柱的底面边长为 1cm ，那么该棱柱的表面积为 _ - ’ 4 J 二 【解答】一个正四棱柱的各个顶点在一个直径为 2cm 的球面上。

正四棱柱的对角线的长为球的直径，现正四棱柱底面边长为 1cm ，设正四棱柱的高为 h ，二2R=2=山■-匸■'解得h= ，那么该棱柱的表面积为 2+4 ” - cm2.21.（安徽？理?15题）在正方体上任意选择 4个顶点，它们可能是如下各种几何形体的4个顶点，这些几何形体是 ____________ （写出所有正确结论的编号）。

cm2。

•••斜边EF①矩形；②不是矩形的平行四边形；③有三个面为等腰直角三角形，有一个面为等边三角形的四面体；④每个面都是等边三角形的四面体；⑤每个面都是直角三角形的四面体。