基于拓扑映射的多边形顶点凸凹判别算法

通过拓扑映射，多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题。首先求得相邻边在两条射影直线上的映射点，基于一般映射点归纳得到顶点凸凹判别的4条规则，然后将两条射影直线上的映射点归结为一条射影直线，从而得到更有效的映射点求取方法，顶点凸凹判别规则统一为两条；进一步考虑非固有映射点的求取方法，提高了算法的稳定性，实验结果表明，该算法实现简单、速度快、稳定可靠。     

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

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

面向骨骼受损类型判别的体素模板构建

针对骨骼受损类型判断较为困难的问题,提出一种面向骨骼受损类型判别的体素模板构建方法,旨在指导医生进行快速判断。首先,在骨骼平均化点云模型的基础上构建最小包围盒,根据空间分辨率对包围盒进行划分,遍历判断后生成体素骨骼模板;然后,建立受损类型与体素模板之间的对应信息,生成受损类型库;最后,将目标骨骼映射到模板上,根据映射后模板上的受损体素区域指导医生判断出受损类型。实验结果表明,该方法能辅助医生直观、快速地判断目标骨骼受损类型,有利于后期面向目标骨骼进行自动判别研究。     

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

证明了文献[1](张宁宁,张树有,谭建荣.映射相关边概念的多边形内外点判别算法.计算机辅助设计与图形学学报, 2004, 16(7): 935-938)中密切边(定义3)是不正确的.在此基础上重新定义了密切边的概念,改进了文献[1]的算法,并增加了检测点在特殊位置时的判定,增强了算法的稳定性和可靠性.     

基于斜率的多边形内外点快速判别算法

多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。     

基于拓扑映射的视图轮廓信息自动获取算法

为克服轮廓信息提取中现有方法计算量大和角度判别复杂等问题,提出了基于拓扑映射的视图轮廓信息求取方法。该方法是基于拓扑映射原理,首先将各候选路径上的点变换为射影直线上的映射点,然后利用映射点与候选路径走向排序的拓扑不变性来进行路径判别,这样将路径分支处的下一路径走向判别转化为映射点在射影直线上的走向判别。若射影直线为水平,则映射点的求取非常简单、方便。该方法由于避免了复杂的角度计算,因而计算效率显著提高,其对工程图视图的自动划分、装配图处理及尺寸布置等有着重要的作用。     

基于边方向角长度表示的多边形方向、凹凸性及点包含算法

提出矢量边方向角的长度表示概念,用于解决多边形方向识别、顶点凹凸性识别和点包含判断三个问题.给出了基于矢量边方向角长度概念描述多边形边方向角的单调连续函数,当方向角从0°增加到360°时,函数值从0增加到8,该函数可以准确地表达多边形中边矢量的方向角,也可以准确地表达待检测点与多边形顶点连线所形成矢量的方向角.建立了基于矢量边方向角长度概念的多边形相邻边左右侧走向关系判定规则.该规则可用于判定相邻边方向关系,实现多边形方向识别和顶点凹凸性识别;计算待检测点与多边形顶点连线之间所夹有向边方向角长度和,实现点包含判断.给出了三个问题的实现算法,该算法与目前最优算法复杂度相同,但计算量较最优算法少1次乘除类运算,同时保证了高可靠性、稳定性和执行效率.实现了三个问题解决方法在几何概念上的统一,而在其他同类算法中几何概念是相互独立的.     

基于链码和特征形的多边形内外点判断算法

通过对多边形各个顶点与待测点相对位置进行判别,给出了多边形的垂直（水平）链码序列生成方法．该方法根据多边形的链码将原多边形中对判别无关的冗余边或冗余点删除,形成多边形的特征形;待测点在特征形与原多边形内外位置关系上具有一致性,从而大大简化了运算．同时给出了一种点在多边形内外点判断算法,把点在原多边形内外的判断转化为点与其特征形的位置判断,特征形的提取过程是一个线性扫描及条件判断过程,可以避免大量的又积运算,从而有效地提高了多边形内外点判断算法的效率．程序验证表明：文中算法易于实现,具有运行速度快、稳定性高等优点．     

基于方向包围盒投影转换的轮廓线拼接算法

基于轮廓线拼接算法重构三维模型时,由于拼接对象的复杂性,任何一种拼接方法都不能完全涵盖所有情况。为此,提出一种基于方向包围盒(OBB)投影转换的轮廓线拼接算法：首先判断多边形的顶点凹凸性,对于凹顶点,将其转换到对应的凸包上;然后计算凸包的方向包围盒,旋转平移矩形包围盒,并求包围盒内接椭圆,将每个顶点都按比例投影此椭圆上;基于投影后的点进行轮廓线拼接,寻找相邻轮廓线顶点之间的对应关系;最后还原实际坐标,进行原始模型的三维重构。     

基于动态分区的多边形顶点凹凸性判别

基于判别顶点对应的边，对平面进行动态分区，形成全正区、全负区和非全正负区，将顶点凹凸性判别转化为后继顶点所在区域位置判别。而全正区、全负区情况只需通过简单判别即可确定顶点的凹凸性，避免乘法运算，其复杂度按概率为(n／4)次乘法(n为多边形顶点数)。试验结果表明，该算法速度快，稳定可靠。     

基于轨迹计算的临界多边形求解算法

将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题．该算法的基本原理是：1）求解多边形顶点相对于另一多边形的轨迹线;2）求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形．该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度．     

基于拓扑映射的背向面去除算法

场景往往由多边形逼近表示,提出的背向面去除算法首先将场景中的多边形法向量正则化为单位向量,并将起始点移至原点,这些单位向量必定位于单位圆球上;然后将单位圆球分成若干个中心对称的区域,每个区域进行拓扑映射得到参考平面,可以求得每个多边形法向量所在的区域,并求出多边形法向量在区域边界圆盘面上的拓扑映射坐标．对同一场景而言,这些计算只需进行一次,称为前置运算．当视点向量位置改变时,则需动态计算视点向量和正背向分界线在每个区域的拓扑映射坐标;然后在一维射影直线上根据视点向量、法向量和分界线之间的拓扑映射坐标位置关系,判断该多边形是否为背向面．实验结果表明,算法运行可靠,有较高的检测速度,尤其是对同一场景,当视点变化时的多次检测效果显著．     

简单多边形可见核的扫描线填充算法

简单多边形的可见核是位于多边形内部的一个点集，可见核内的任意一点与多边形边界上的任意一点的连线都处于该多边形的内部。由于可见核具有这一性质，对简单多边形的可见核的计算在很多方面都有着适用。本文考察了简单多边形的核的性质与特点，在结合了其他相关的可见核顶点的算法之后，提出了一个对可见核进行填充的快速算法。这一算法由于通过避免在填充多边形的核之前进行计算可见核的顶点的过程，从而可以较快地对可见核进行填充。这一算法不仅容易理解，而且便于实现。     

基于Strip-Tree的无级比例尺GIS多边形化简技术

无级比例尺GIS(geographicinformationsystem)多边形化简的基础是多边形弧段的线综合,而直接对多边形的弧段施加线综合操作可能造成输出数据的拓扑错误,主要表现为化简后弧段出现相交.以往的研究并未对这个问题给予足够的重视和给出自动化的解决方法.在对此问题进行全面分析的基础上,提出了一种基于Strip-Tree的多边形图层化简策略,在保持输出数据拓扑结构正确的前提下化简多边形图层,且保持了较高的时空效率.该策略成功地应用于国家863项目“时空一体化智能城建信息系统”,并获得了满意的效率和结果.     

Guarding galleries and terrains

Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation algorithms for finding the smallest set G of points of P so that each point of P is seen by at least one point of G, and the points of G are constrained to be belong to the set of vertices of an arbitrarily dense grind. We also present similar algorithms for terrains and polygons with holes.     

Updating Polygonizations*

In this paper we consider polygonizations that are robust when faced with changes in the vertices that are present or in their position. We analyze the dynamic maintenance of different types of polygonizations (monotone, star-shaped…) and we introduce monotone half-convex polygonizations that are specially interesting because they provide minimum cost per insertion or deletion. If we had to delete not only one point but several external layers of the set, then the onion polygonizations would be suited, because they can be updated in constant time. We also consider the case of points that can be moved to contiguous positions and we show how to polygonize the set for updating in linear time. We deal too with security problems for a polygon: What is the maximum distance the vertices of a polygon could be moved away of their position in such a way that the topology on the boundary of the polygon (or its convexity) remains the same?.     

简单多边形凸凹性自识别算法

提出一种基于极值顶点构造凸多边形和矢量叉乘的自动识别简单多边形方向性，凸凹性的算法，该算法在稳定性方面采取了有效的措施，避免因极值顶点的奇异性而导致多边形方向性，凸凹性的错误识别，具有良好的可靠性和稳定性，算法原理直观简单，效率高，时间复杂度为O（n).     

多边形方向可视剖分技术

为实现简单多边形内的线燃烧轨迹计算,首先提出线视下方向可视的概念,指出8种可视的直线类型,并总结出7种桥结构模型。通过方向投影把多边形区域分成两个点可视区和两个方向可视区,利用主线和从线的遮挡关系来找桥头和桥尾以完成桥的构造,并实现多边形边界的方向可视剖分。其次,结合点可视剖分算法实现多边形的深度方向可视剖分,并进一步推导出多边形内任意点到任意线段的最短路径。最后,把该算法应用到多边形的线燃烧轨迹计算,取得良好的效果。