测试点在多边形内部

PNPOLY-PointInclusioninPolygonTestW.RandolphFranklin(WRF)Thisisanexpansionoftheanswerinthecomp.graphics.algorithmsFAQquestion2.03,HowdoIfindifapointlieswithinapolygon?TableofContents1.TheCCode2.TheMethod3.Originality4.TheInequalityTestsareTricky5.CSemantics6.Pointona(Boundary)Edge7.ConcaveComponents,MultipleComponents,andHoles8.TestingWhichOneofManyPolygonsContainsthePoint9.Explanationoffor(i=0,j=nvert-1;invert;j=i++)10.FortranCodeforthePointinPolygonTest11.ConvertingtheCodetoAllIntegers12.LicensetoUse13.InclusionTestingbySubtendedAngles14.ConvexPolygons,suchasRectangles15.AlmostConvexPolygons16.3DPolygons17.TestingPointInclusioninaPolyhedron18.IfYouHaveaSuggestionorFindanError19.AcknowledgementsTheCCodeHereisthecode,forreference.Excludinglineswithonlybraces,thereareonly7linesofcode.intpnpoly(intnvert,float*vertx,float*verty,floattestx,floattesty){inti,j,c=0;for(i=0,j=nvert-1;invert;j=i++){if(((verty[i]testy)!=(verty[j]testy))&&(testx(vertx[j]-vertx[i])*(testy-verty[i])/(verty[j]-verty[i])+vertx[i]))c=!c;}returnc;}ArgumentMeaningnvertNumberofverticesinthepolygon.Whethertorepeatthefirstvertexattheendisdiscussedbelow.vertx,vertyArrayscontainingthex-andy-coordinatesofthepolygon'svertices.testx,testyX-andy-coordinateofthetestpoint.TheMethodIrunasemi-infiniterayhorizontally(increasingx,fixedy)outfromthetestpoint,andcounthowmanyedgesitcrosses.Ateachcrossing,therayswitchesbetweeninsideandoutside.ThisiscalledtheJordancurvetheorem.Thecaseoftheraygoingthruavertexishandledcorrectlyviaacarefulselectionofinequalities.Don'tmesswiththiscodeunlessyou'refamiliarwiththeideaofSimulationofSimplicity.Thispretendstoshifttherayinfinitesimallydownsothatiteitherclearlyintersects,orclearlydoesn'ttouch.Sincethisismerelyaconceptual,infinitesimal,shift,itnevercreatesanintersectionthatdidn'texistbefore,andneverdestroysanintersectionthatclearlyexistedbefore.Therayistestedagainsteachedgethus:1.Isthepointinthehalf-planetotheleftoftheextendededge?and2.Isthepoint'sYcoordinatewithintheedge'sY-range?Handlingendpointshereistricky.OriginalityImakenoclaimtohavinginventedtheidea.Howeverin1970,IdidproducetheFortrancodegivenbelowonmyown,andincludeitinapackageofcartographicSWpublicly-distributedbyDavidDouglas,DeptofGeography,SimonFraserUandUofOttawa.TheCcodeintheFAQismycode,lightlyedited.Earlierimplementationsofpoint-in-polygontestingpresumablyexist,thothecodemightneverhavebeenreleased.Pointerstopriorart,especiallypubliclyavailablecode,arewelcome.Oneearlypublication,whichdoesn'thandlethepointonanedge,andhasatypo,isthis:MShimrat,Algorithm112,PositionofPointRelativetoPolygon,Comm.ACM5(8),Aug1962,p434.Awell-writtenrecentsummaryisthis:EHaines,PointinPolygonStrategies,(Boundary)EdgePNPOLYpartitionstheplaneintopointsinsidethepolygonandpointsoutsidethepolygon.Pointsthatareontheboundaryareclassifiedaseitherinsideoroutside.1.Anyparticularpointisalwaysclassifiedconsistentlythesameway.Inthefollowingfigure,considerwhatPNPOLYwouldsaywhentheredpoint,P,istestedagainstthetwotriangles,TLandTR.Dependingoninternalroundofferrors,PNPOLYmaysaythatPisinTLorinTR.HoweveritwillalwaysgivethesameanswerwhenPistestedagainstthosetriangles.Thatis,ifPNPOLYfindsthatPisinTL,thenitwillfindthatPisnotTR.IfPNPOLYfindsthatPisnotinTL,thenitwillfindthatPisinTR.2.Ifyouwanttoknowwhenapointisexactlyontheboundary,youneedanotherprogram.ThisisonlyoneofmanyfunctionsthatPNPOLYlacks;italsodoesn'tpredicttomorrow'sweather.YouarefreetoextendPNPOLY'ssourcecode.3.Thefirstreasonforthisisthenumericalanalysispositionthatyoushouldnotbetestingexactequalityunlessyourinputisexact.Eventhen,computationalroundofferrorwouldoftenmaketheresultwrong.4.Thesecondreasonisthat,ifyoupartitionaregionoftheplaneintopolygons,i.e.,formaplanargraph,thenPNPOLYwilllocateeachpointintoexactlyonepolygon.Inotherwords,PNPOLYconsiderseachpolygontobetopologicallyasemi-openset.Thismakesthingssimpler,i.e.,causesfewerspecialcases,ifyouusePNPOLYaspartofalargersystem.Examplesofthisincludelocatingapointinaplanargraph,andintersectingtwoplanargraphs.ConcaveComponents,MultipleComponents,andHoles1.Thepolygonmaybeconcave.However,ifavertexisveryclosetoanedge(thatthevertexisnotanendof)thenbewareofroundofferrors.2.Thedirectionthatyoulistthevertices(clockwiseorcounterclockwise)doesnotmatter.3.Thepolygonmaycontainmultipleseparatecomponents,and/orholes