Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
Testing for Points on Border or Interior of a Polygon
It is often necessary to numerically test whether a point is within a specified polygon or on its border. Here we will develop some functions for this purpose, which might be useful, for example, in problems that compute the electrostatic potential outside systems of electrodes in two dimensions.
Gives True if the point is inside of the polygon. | |
Gives True if the point is on the border of the polygon. |
Functions testing for points on border or interior of a polygon.
Make sure the package is loaded.
In[1]:=
Needs["QuantumMob`DrawingTools`"]
Introduction
We define a polygon as a list of vertices whose first and last points coincide, such that =. Suppose that the point is an interior point of . Let represent the interior angles formed between lines from to each , as sketched below. If we interpret the points as lying in the complex plane, these angles can be computed easily according to
={,,⋯,,}
z
1
z
2
z
n
z
n+1
z
n+1
z
1
p
{,,⋯,}
α
1
α
2
α
n
n
p
z
i
α
i
z
i+1
z
i
The identification of interior points is based upon the winding number
W=
1
2π
n
∑
i=1
α
i
that counts the number of times winds around in a positive (counter-clockwise) sense; a negative winding number corresponds to a clockwise loop. A point is interior to iff and is exterior otherwise.
p
p
W≠0
In[6]:=
p={1,2};poly={{3,4},{1,5},{-2,3},{2,-1},{3,4}};ListPlot[Append[poly,p],PlotStyleAbsolutePointSize[4],Epilog{Line[poly],Dashing[{0.02,0.02}],Table[Line[{p,poly〚k〛}],{k,Length[poly]}]}]
Out[8]=
Implementation
Winding number, wn
Winding number, wn
The following function evaluates the winding number. The dot products with convert the Cartesian coordinates to the complex numbers needed by Arg. Chop ensures that vanishing winding numbers are returned as 0 instead of a numerically insignificant number. Note that this function is undefined for points that coincide with any of the vertices.
{1,}
In[9]:=
fWindingNumber[Polygon[poly_],pt:{_,_}]:=With[{zz=Complex@@@poly-Complex@@pt},Rationalize@N[Total[MapThread[Arg[#1/#2]&,{Rest@zz,Most@zz}]]/(2Pi)]]
To test this function, we construct a closed polygon with several loops. Selected points are numbered in the diagram. Point 1 is clearly surrounded once in a positive sense, point 2 once in a negative sense, point 3 twice in a negative sense, and point 4 is exterior. Also observe that point 5 is not enclosed while point 6 is encompassed once in a negative sense. As shown below, our function successfully computes these winding numbers.
In[38]:=
poly={{0,4},{7,4},{7,-3},{-2,-3},{0,2},{5,2},{3,-2},{-4,3},{-5,0},{-3,-3},{0,4}};pts={{-3,-1},{5,3},{2,1},{-2,4},{-1.85,-1.5},{-0.6,1.5}};Graphics[{Polygon@poly,Red,PointSize[0.02],Point/@pts,MapThread[Text[Framed[#1],#2,-{1,1}]&,{Range@Length@pts,pts}]},PlotRangePadding1]
Out[40]=
In[43]:=
more={poly〚2〛,0.27poly〚2〛+0.73poly〚3〛};Graphics[{Polygon@poly,PointSize[0.02],Red,Point/@pts,MapThread[Text[Framed[#1],#2,-{1,1}]&,{Range@Length@pts,pts}],Blue,Point/@more},PlotRangePadding1]
Out[44]=
In[16]:=
fWindingNumber[Polygon@poly,#]&/@pts//Chop
Out[16]=
{1,-1,-2,0,0,-1}
OnBoundaryQ
OnBoundaryQ
Notice that the winding number vanishes for points that are on the boundary but not on any vertex. For example,
In[17]:=
fWindingNumberPolygon@poly,
2poly〚2〛+3poly〚3〛
5
Out[17]=
0
The following function determines whether there is a solution to the equation
0≤t≤1
pt+(1-t)
z
i
z
i+1
for any vertex . The Table produces a list of True|False for each vertex and MemberQ asks whether there is a True in that list.
1≤i≤n
In[23]:=
 | OnBoundaryQ |
Out[23]=
{False,False,False,False,False,False,True,True}
Notice that vertices are on the boundary. The boundary need not be closed.
InPolygonQ
InPolygonQ
Finally, combines these functions into a single query that returns True for points enclosed by the polygon or on its boundary and False otherwise. If given an open curve, it closes the polygon by connecting the first and last points. The interior and boundary tests are included explicitly so that this function is self-contained.
In[29]:=
| InPolygonQ |
Out[29]=
{True,True,True,False,True,True,True,True}
 |
|
|
""