第17卷第6期2005年6月计算机辅助设计与图形学学报JOURNALOFCOMPUTER�AIDEDDESIGN&COMPUTERGRAPHICSVol�17,No�6June,2005��收稿日期:2003-12-25;修回日期:2004-07-26�基金项目:中国科学院知识创新工程领域前沿项目(CXNIGLAS�A02�012)基于边方向角长度表示的多边形方向、凹凸性及点包含算法丁�健1,2,3)�江�南1)�芮�挺3)1)(中国科学院南京地理与湖泊研究所地理信息科学研究室�南京�210008)2)(中国科学院研究生院�北京�100039)3)(解放军理工大学工程兵工程学院�南京�210007)(ydjian@yahoo�com�cn)摘要�提出矢量边方向角的长度表示概念,用于解决多边形方向识别、顶点凹凸性识别和点包含判断三个问题�给出了基于矢量边方向角长度概念描述多边形边方向角的单调连续函数,当方向角从0�增加到360�时,函数值从0增加到8,该函数可以准确地表达多边形中边矢量的方向角,也可以准确地表达待检测点与多边形顶点连线所形成矢量的方向角�建立了基于矢量边方向角长度概念的多边形相邻边左右侧走向关系判定规则�该规则可用于判定相邻边方向关系,实现多边形方向识别和顶点凹凸性识别;计算待检测点与多边形顶点连线之间所夹有向边方向角长度和,实现点包含判断�给出了三个问题的实现算法,该算法与目前最优算法复杂度相同,但计算量较最优算法少1次乘除类运算,同时保证了高可靠性、稳定性和执行效率�实现了三个问题解决方法在几何概念上的统一,而在其他同类算法中几何概念是相互独立的�关键词�多边形;方向识别;顶点凹凸性识别;点包含判断;矢量边方向角长度中图法分类号�TP301;TP391Orientation,Convexity�ConcavityandInclusionQueryAlgorithmsforPolygonsUsingtheEdge�Azimuth�LengthConceptDingJian1,2,3)�JiangNan1)�RuiTing3)1)(GeoinfomaticsDepartment,NanjingInstituteofGeographyandLimnology,ChineseAcademyofSciences,Nanjing�210008)2)(GraduateSchooloftheChineseAcademyofSciences,Beijing�100039)3)(EngineeringInstituteofEngineeringCorps,PLAUniversityofScience&Technology,Nanjing�210007)Abstract��Ametricsquarewitheachsideof2unitslongisconstructedinsidethegivenpolygon,andtheazimuthofaradialvector,takingy�axisasnorthdirection,isrepresentedintermsofedge�azimuth�length(EAL),i�e�theoveralllengthofthesquareedgesincludedbetweentheircrossingpointswithy�axisandthegivenradialvector,resultinginamonotonicallycontinuousfunctionvaluerangingfrom0to8,astheazimuthincreasingfrom0�to360��Orientationofapolygonandconvexity�concavityofavertexcanbede�tectedbyverifyingwhethertheEALvaluesofconsecutiveedgesareincreasingmonotonicallyornot,whilepointinclusionquerycanbeclarifiedbytakingthegivenpointasoriginandsumming�uptheincrementalEALvalueofeachedge:8meansincludedand0meansnot�Keywords�polygon;orientationidentification;convexity�concavityidentification;point�in�polygonquery;edge�azimuth�length1�引��言多边形方向、顶点凹凸性识别及其与点之间的包含关系判断在科学计算可视化、地理信息系统等领域均有应用,相关算法研究一直受到学者们的关注,多年来研究人员已经提出了许多以提高计算效率和稳定性为目标的算法,目前仍处于不断改进过程中�如地理信息系统中,用鼠标点击实现对多边形图形要素的选择、多边形图形要素与点图形要素的拓扑叠加查询,都要重复地调用点包含判断算法�因此,用优化算法来提高多边形方向、顶点凹凸性和点包含三个判断过程的时间效率具有十分重要的实际应用意义�目前,最优的多边形方向、顶点凹凸性与点包含判断三个算法具有各自独立的几何概念,相互之间处于割裂状态,没有联系�在多边形方向、顶点凹凸性问题上,执行效率较高的是顶点前后相邻边矢量叉积法[1�5],基于4个极值顶点必为凸点的性质,根据其前后相邻边矢量叉积结果的符号(正或负)得到多边形的方向(逆时针或顺时针),非极值顶点凹凸性的判断也通过计算相邻边矢量叉积得到,叉积结果符号与极点叉...
