资源描述：
《边方向角长度和点包含算法的改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、·186·中国科协第二届优秀博士生学术年会论文集边方向角长度和点包含算法的改进①丁健1,2,3江南，苗材(I.中国科学院南京地理与湖泊研究所南京2100082.中国科学院研究生院北京1000393.解放军理工大学工程兵工程学院南京210007)摘要对丁健[1,2]的边方向角长度和点包含判断算法提出改进方法。定义了多边形半平面连续链概念，建立了半平面连续链整体计算定理，通过计算连续链两个端点之间的边方向角长度差值，直接得到链上各边的边方向角长度差值之和，从而跨过了中间边的计算，减少了计算量。给出改进算法，算法先对多边形进行半平面连续链划分，然后以链为单位，逐条链整体计算，最后对边方向角
2、长度差值进行累加，用累加值判断点的内外性。分析表明，改进算法在顶点数大于4时，可以减少计算量，提高算法效率。关键词多边形点包含判断边方向角长度边方向角长度和半平面连续链TheImprovementofPoint一in一PolygonAlgorithmBasedonEdge一azimuth一lengthDingJiant'Z'3,JiangNan'，RuiTing3(1.NanjingInstituteOfGeographyAndLimnology,TheChineseAcademyofSciences,Nanjing210008,China;2.GraduateSchoolofthe
3、ChineseAcademyofScience,TheChineseAcademyofSciences,Be巧ing100039,China;3.EngineeringInstituteOfEngineeringCorps,PLAUST,Nanjing210007，China)AbstractTheimprovementforDingjiantpoint一in一polygonalgorithmwhichqueryaboutwhetherapointlieswithinapolygonornotisgiven.Anewconcept,thecontinuouschaininhalfpl
4、aneisdefined,thewholecalculationmethodforcontinuouschainisfounded,whichgetthesumofEdge一azimuth一lengthofthecontainededges,场directlycalculatingthediferencebetweenthetwoendpoints.Allin-termediateedges'calculationinacontinuouschainareomitedandavioded,thusthecomputationtimeiscutdown.Theimprovedalgor
5、ithmpartitionthepolygonedgestocontinuouschainsfirst,thencalculateeachchain'sEdge一azimuth一lengthdiference,andaccumulatethemtoasum.Bycomparingthesumwith16,8，and0,whetherthepointlieswithinthepolygonornotwillbeidentified.Analysisshowstheimprovedalgorithmisfasterthantheoriginal,specialyforconvexpoly
6、gon.Keywordspolygon,point一in一polygonquery,Edge一azimuth一length,thesumofEdge一azimuth-length,continuouschaininhalfplane①本研究得到中国科学院知识创新工程领域前沿项目(CXNIGLAS-A02-012)资助。本研究还应用于“东南沿海野营供水地理信息系统”课题中，该课题获2004年度军队科技进步二等奖。信息科技1871引言点在多边形内外的判断，也即点包含判断，是计算机图形学、地理信息系统、科学计算可视化等领域中的基本问题，几十年来，国内外学者针对点包含算法的设计、改进、优化等
7、工作从来没有中断过。笔者给出了点包含判断的新颖、高效算法—边方向角长度和算法，该算法基于相邻的检测点与顶点连线之间，边方向角长度差值累加之和为固定值(0，土8n，土16n，其中n为自然数)的原理，适用于简单、自交、含岛和合并等一般意义上的多边形，在时间复杂度与执行效率方面都有先进之处f}.zl。文献〔1,21算法主要耗时部分是每条连线的边方向角长度计算，每对相邻连线间的边方向角长度差值计算，以及累加计算。本文的研究找出了无需计算的中间连线，提出了基于多边形
