一种检测点是否在多边形或多面体内的方法

提出一种新的方法，以检测一个点是否在多边形或多面体内．此方法以射线法的基础，用垂直于射线的直线(或平面)将多边形(或多面体)分成两大部分，检测时，仅仅处理射线所指向的那个部分，根据射线穿过的多边形的折线或多面体的多边形曲面的个数的奇偶性判断检测点是否在多边形或多面体内，在检测过程中该方法只求解少量的方程，不必处理每个面和每条边，实验结果表明，该方法简单，可靠，检测速度快。     

借助梯形分割的点面包含分析

在诸多研究领域中,判断点是否在多边形内是一个非常基本的问题。在分析了解决这一问题的传统方法基础上,提出了一种基于梯形分割的点面包含算法。该算法将多边形分割成若干个梯形网格单元,将判断点是否位于多边形内的问题转化为判断点是否位于梯形网格单元中这一问题。算法已用于GIS平台软件相应的包含分析模块,试验结果证明该算法稳定可靠、适用于任意复杂多边形而无需对奇异情况进行单独处理。     

点与简单多边形关系的新算法

提出一种检测点与多边形关系的新算法，通过扫描建立适合查找的多边形层次结构。检测时，运用二分查找，找到与检测点相关的边，通过该点与相关边的关系判断出点与多边形的关系。实验结果表明，该方法简单有效，有较高的检测速度。     

擂台赛点评

本次擂台赛的题目是要求编一程序,输入多边形的n个顶点及任意一个点的坐标,判断该点是否在该多边形内。 这里介绍一种有效的判断算法,其数学依据为:如果一个点在闭合多边形内则任意从该点出发所引的射线,与多边形的边(线段)所交的点数一定是个奇数个。     

判断检测点是否在多边形或多面体内的新方法

提出一种新方法,以检测一个点是否在多边形或多面体内.该方法通过将多面体的面片和多边形的边组织成层次结构,在检测时运用二分查找算法,不必处理每个面片和每条边.试验结果表明,这种方法简单、有效,有较高的检测速度.     

有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。     

判断点在任意简单多边形内的改进算法

计算机图形处理的许多算法中经常涉及诸如点是否在区域内部的判断,判断点在多面体内的算法和形体的交、并、差布尔运算中都要用到点是否在多边形内的判断。确定一个点在任意简单多边形内的问题是计算几何、计算机图形学的基本问题。本文提出的算法是对判断点在多边形内的射线法的一种改进,对所有可能出现的特殊情况都进行了处理,能够准确地判断出点在任意简单多边形内的位置。本算法结构清晰,易于编程实现。     

基于单调性与相关边的多边形内外点判断算法

为了充分挖掘多边形边的基本性质——单调性，基于检测点与多边形边之间的坐标关系，提出了相关边的概念及一种判断点在多边形内外的新算法。综合运用单调性与相关边技术，将点与我边形之间的位置关系转化为点与茯相关边之间的位置关系，从而尽可能地避免了叉积运算，且无需求交运算，从根本上提高了算法的效率，同时新算法还简单有效地解决了射线法中的临界位置问题。程序验证表明，新算法易于实现，适用于简单多边形，具有运行速度快、稳定性高等优点。     

一个有效的多边形窗口的线裁剪算法

已有的线剪裁算法都是针对矩形窗口或凸多边形窗口的,对于一的多边形窗口（包括凹多边形）的线剪裁,目前尚无有效的算法,而这样的算法却有更普遍的应用意义。该文提出一个对于一般多边形窗口的线剪裁算法。该算法在被裁剪直线的延长线上取一固定点,然后求多边形窗口的每一顶点到该固定点引线的斜率。这样对于每个窗口边只需判断被裁剪直线的斜率是否在该边两顶点到固定点引线斜率之间,就可判定直线与边是否相交,因此,每处理一     

判断点与简单多边形位置关系的新算法

基于射线法提出了一种新的判断点与简单多边形位置关系的算法。该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点。此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度。     

点云数据压缩中的边界特征检测

点云数据压缩是逆向工程产品建模中必要的数据预处理手段之一。常见的数据压缩算法未考虑点云边界数据点的保留问题，因此在大比例压缩过程中会出现边界数据丢失的情况，从而破坏了数据的完整性。为此，提出了一种利用点云数据小邻域内点的相邻关系来检测边界特征点的算法。该算法能检测出点云数据的内、外边界特征点，同时对边界上的点进行排序，检测出边界特征点中的过渡点，最后构建点云轮廓的边界多边线。该算法不仅能满足在点云数据压缩过程中检测并保留边界特征点的要求，而且生成的边界多边线也为后面的3维模型重建奠定了基础。     

映射相关边概念的多边形内外点判别算法

提出映射相关边、密切边的概念，将点在多边形内外的判别转化为点与密切边关系的判别．通过X方向的一次映射快速求取判别点的相关边，对相关边的二次映射可得到判别点的密切边．证明了根据密切边的矢量方向就可以判别点在多边形内外．在运算效率上对射线法进行改进，当多边形的边数较多时，更能体现文中算法优越性．     

基于面向对象的线画图立体图形的实体模型设计

文中应用面向对象的设计方法，针对消除隐藏线算法，为由点，直线段，多边形构成的立体图形设计了一种实体模型，该实体模型具有封装性和可维护性等面向对象设计方法的优点，同时由于记录了大量的立体图形的点、边、面的拓扑关系，使消除隐藏线算法减少很多已知点，边、面查找相关的点、边、面的运算，从而提高了算法的效率，使在显示进行平移，放缩，旋转等变换的立体图形时，可较好地满足消除隐藏线的实时性的要求。     

线点包容检测算法

提出的算法是先以快速的方法判断线与多边形是否有交点,如有,则求出线与多边形的各个交点,将交点进行排序,将此线按交点顺序分为多段;如果无交点,则此线只有一段。检测各段中点是否位于多边形内,如果位于内部,则此段在内,否则此段在外。以倾斜射线法检测点的包容性,其特点是此射线不与多边形的顶点或边重合,无须作特殊情况的处理,计算区域小,因而计算量小,对自相交多边形及带孔多边形等多类情况同样适用。通过编写程序计算验证表明,此算法简单有效、稳定可靠,适用于多类情况。     

基于顶点与邻边相关性的多边形填充算法

为了加快多边形填充算法的运算速度，在深入挖掘顶点与相邻边关系对填充算法影响的基础上，提出了一种基于顶点与邻边相关性的多边形填充算法。该算法首先归纳了多边形顶点与邻边相关性的5种典型类型，然后依据顶点与邻边的相关性，对原有多边形进行了分割与重新组合，使其完全由简单的三角形和梯形这样的单元区域组成，这样就将复杂的多边形填充问题转化为这些单元区域的填充问题，并由此将扫描线与多边形边求交的乘除计算转化为加减运算。通过实验分析，新算法大大减少了运算的时间和复杂度，从而为多边形填充创造了一种有效的新途径。     

人工目标图像中的消失点检测

在人工目标检测中,消失点信息比边缘、拐角等特征更加鲁邦。根据累计空间的不同,消失点检测方法可划分为有限空间检测和无限空间检测两大类。在有限空间检测方法中,Barnard提出的基于高斯映射的消失点检测,因同时适用于有限远和无穷远消失点的检测,最为引人关注。但该方法因累计空间划分不均匀,容易造成统计计算的偏差。文章针对人工目标固有特征,提出了长度优先的向量叉积候选消失点检测方法,在避免了因累计单元大小不均而造成计算偏差的同时,强调了人工目标的主体特征。同时利用三个彼此正交的方向信息,反算相机的内部参数,用以判定三个正交方向选择的合理性。从而使得消失点的确定,能够更好地满足人工目标特征的提取要求。     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.     

基于网格中心点的点在多边形内的高效判定

提出一种基于均匀网格的点在多边形内的高效判定算法.它首先建立均匀网格,并从左至右依次计算每个网格单元中心点的位置属性.每个单元中心点的位置属性直接依据其左侧邻接单元已知位置属性的中心点快速获得.在判定点的位置时,确定被测点所在单元,并依据该单元中心点的位置属性判定被测点的位置属性.由于预处理和判定时均利用邻近点的已知位置属性来确定未知点位置属性,可以很好地进行局部化的计算.因此,新方法比现有方法快很多,并且其预处理时间复杂度也由同类网格算法的O(N3/2)下降为O(N).同时,新方法可以统一处理含有自相交及重叠边的非流形多边形.实验结果表明,相比于其他基于均匀网格的方法,新方法可将预处理的速度提高几倍,将判断计算的速度提高十几到几十倍.其速度甚至优于具有该问题最低判定计算时间复杂度O(logN)的基于凸剖分的判定算法.