Does point fall within polygon? VBA Function

[sijpie]

This is not a question, just a post of some code to help find if a point falls within a (complex) polygon.

I found the original code written in C here:
Determining Whether A Point Is Inside A Complex Polygon

The page also explains the issues with complex polygons. But the code of course also works for simple polygons.

I have modified the code to run as a function in Excel, and so it can be called as any other function.

The function takes as arguments the point to be checked as a range with X & Y, and a range with all the points of the polygon, X & Y.

In my example I am checking if wells drilled in the past are within a certain area.

Excel 2010
	A	B	C	D	E	F	G	H	I
1	Stage 1 Polygon
2						Well Database	SurfaceCoordinates
3							Stereo70		In Stage1 Area
4		x	y
5		549926	313550			Well Name	EastingY[m]	NorthingX[m]	Yes/No
6		549357	313316			1 A Est	559,008.51	309,204.47	FALSE
7		549923	312176			1 Ar Est	550,000.30	313,130.16	TRUE
8		550650	312573			1 Ar Vest	543,011.50	313,106.58	FALSE
9		551164	313205			1 I Est	556,226.56	312,713.64	TRUE
10		549926	313550			1 K Vest-Blejesti	539,357.63	313,165.48	FALSE
11						2 A Est	559,388.41	309,234.32	FALSE
12						2 Ar Est	549,925.25	313,140.10	TRUE
13						2 Ar Vest	543,080.28	312,970.75	FALSE
14						2 I Est	554,430.45	313,551.15	FALSE
15						2 P Vest	545,170.00	310,055.00	FALSE
16						3 A Est	559,722.95	309,279.51	FALSE
Wells inSt1 (2)

Cell Formulas
Range	Formula
I6	=PointInPolygon(G6:H6,Stage1Poly)

Named Ranges
Name	Refers To	Cells
'Wells inSt1 (2)'!Stage1Poly	='Wells inSt1 (2)'!$B$5:$C$9

To use the function, copy the code below. In Excel press Alt-F11 to open the VBA editor. Rightclick on the workbook name in the top left panel, and select Insert/Module. In the right hand pane, paste the code. Now in the workbook you can use the function as shown above. The range holding the polygone nodes is range Stage1Poly, which is B5:C9

The function code is as follows:

<font face=Courier New><SPAN style="color:#00007F">Function</SPAN> PointInPolygon(rXY <SPAN style="color:#00007F">As</SPAN> Range, rpolyXY <SPAN style="color:#00007F">As</SPAN> Range) <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Boolean</SPAN><br>    <SPAN style="color:#007F00">' Function checks if X,Y given in rXY falls within complex _<br>      polygon as defined by node list rpolyXY. _<br>      rXY to be 2 cell range with one X and one Y value _<br>      rpolyXY to be 2 column range with for each node on the polygon _<br>      the X and the Y point</SPAN><br>    <br>    <SPAN style="color:#00007F">Dim</SPAN> i <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Integer</SPAN>, j <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Integer</SPAN>, polySides <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Integer</SPAN><br>    <SPAN style="color:#00007F">Dim</SPAN> oddNodes <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Boolean</SPAN><br>    <SPAN style="color:#00007F">Dim</SPAN> x <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Double</SPAN>, y <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Double</SPAN><br>    <SPAN style="color:#00007F">Dim</SPAN> aXY <SPAN style="color:#00007F">As</SPAN> <SPAN style="color:#00007F">Variant</SPAN><br>    <br>    oddNodes = <SPAN style="color:#00007F">False</SPAN><br>    x = rXY.Cells.Value2(1, 1)<br>    y = rXY.Cells.Value2(1, 2)<br>    aXY = rpolyXY.Value<br>    <br>    polySides = rpolyXY.Rows.Count<br>    j = polySides - 1<br>    <br>    <SPAN style="color:#00007F">For</SPAN> i = 1 <SPAN style="color:#00007F">To</SPAN> polySides<br>        <SPAN style="color:#00007F">If</SPAN> (((aXY(i, 2) < y And aXY(j, 2) >= y) _<br>            <SPAN style="color:#00007F">Or</SPAN> (aXY(j, 2) < y And aXY(i, 2) >= y)) _<br>            And (aXY(i, 1) <= x <SPAN style="color:#00007F">Or</SPAN> aXY(j, 1) <= x)) <SPAN style="color:#00007F">Then</SPAN><br>            oddNodes = oddNodes Xor (aXY(i, 1) + (y - aXY(i, 2)) / (aXY(j, 2) - aXY(i, 2)) * (aXY(j, 1) - aXY(i, 1)) < x)<br>        <SPAN style="color:#00007F">End</SPAN> <SPAN style="color:#00007F">If</SPAN><br>        j = i<br>    <SPAN style="color:#00007F">Next</SPAN> i<br>    PointInPolygon = oddNodes<br><SPAN style="color:#00007F">End</SPAN> <SPAN style="color:#00007F">Function</SPAN><br></FONT>

 

[nira123]

I would first point you to Message #4 in this thread. Then I would refer you to the original article in my mini-blog where I first posted my code...

Test Whether A Point Is In A Polygon Or Not

The following are responses I gave as follow ups to people's questions within the above linked article. If you read through the entire thread, you will see them. If you do not want to read the entire thread, I believe these three responses I gave might be of interest to you...

See this link for the answer I gave someone with the same question you are asking...

Test Whether A Point Is In A Polygon Or Not - Page 2

Some thoughts I had about points lying on the polygon itself (note the two links below take you to different Messages even though their text reads the same)...

Test Whether A Point Is In A Polygon Or Not - Page 3

Test Whether A Point Is In A Polygon Or Not - Page 3

Hi Rick many thanks for the reply. It seems it's developed advance to see within tolerance. I am trying to get the output by changing the same code you originally published.

Cheers, Shan

 

[nira123]

I would first point you to Message #4 in this thread. Then I would refer you to the original article in my mini-blog where I first posted my code...

Test Whether A Point Is In A Polygon Or Not

The following are responses I gave as follow ups to people's questions within the above linked article. If you read through the entire thread, you will see them. If you do not want to read the entire thread, I believe these three responses I gave might be of interest to you...

See this link for the answer I gave someone with the same question you are asking...

Test Whether A Point Is In A Polygon Or Not - Page 2

Some thoughts I had about points lying on the polygon itself (note the two links below take you to different Messages even though their text reads the same)...

Test Whether A Point Is In A Polygon Or Not - Page 3

Test Whether A Point Is In A Polygon Or Not - Page 3

Following are the edited code to check points on the polygon in addition to points on the polygon:

Function fpointinpolygon(rXY As Range, rpolyXY As Range) As Boolean
' --------------------------------------------------------------
' Comments:
' Function checks if X,Y given in rXY falls within or on complex
' polygon as defined by node list rpolyXY.
' rXY to be 2 cell range with one X and one Y value
' rpolyXY to be 2 column range with for each node on the polygon _
' the X and the Y point
'
' Arguments:
' rXY (Range) = Coordinates of point to be checked
' rpolyXY (Range) = Coordinates of points defining the polygon
'
' Date Developer Comment
' --------------------------------------------------------------
' 10/07/13 sijpie Initial version. Taken from mrexcel.com forums
' Does point fall within polygon? VBA Function
' Refrerenced from: Determining Whether A Point Is Inside A Complex Polygon which is the implementation in C++
' 08/11/13 AussieChuck Changed "j" variable from "=polySides-1" to "=polySides"
' 5/10/20 Nira123 Added extra codes accept points on the polygon


Dim i As Integer, j As Integer, polySides As Integer
Dim oddNodes As Boolean
Dim x As Double, y As Double
Dim p, q, r, s, t, u, v As Double
Dim aXY As Variant

oddNodes = False
x = rXY.Cells.Value2(1, 1)
y = rXY.Cells.Value2(1, 2)
aXY = rpolyXY.Value

polySides = rpolyXY.Rows.Count
voidSides = rXY.Rows.Count - 1

j = polySides



For i = 1 To polySides

p = (y - aXY(i, 2))
q = (x - aXY(i, 1))
r = (aXY(j, 2) - aXY(i, 2))


If (((aXY(i, 2) < y And aXY(j, 2) >= y) _
Or (aXY(j, 2) < y And aXY(i, 2) >= y)) _
And (aXY(i, 1) <= x Or aXY(j, 1) <= x)) Then
oddNodes = oddNodes Xor ((aXY(i, 1) + (y - aXY(i, 2)) / (aXY(j, 2) - aXY(i, 2)) * (aXY(j, 1) - aXY(i, 1)) <= x))
End If


j = i
Next i



For i = 1 To polySides - 1
p = (y - aXY(i, 2))
q = (x - aXY(i, 1))
s = aXY(i + 1, 2) - aXY(i, 2)
t = (aXY(i + 1, 1) - aXY(i, 1))
u = VBA.Sqr(s ^ 2 + t ^ 2)
v = VBA.Sqr(p ^ 2 + q ^ 2)

If (q = 0 And p = 0) Then
oddNodes = True
i = polySides

ElseIf q = 0 Or t = 0 Then
oddNodes = oddNodes

ElseIf ((p / q) = (s / t) And (u / v) >= 1) Then
oddNodes = True
i = polySides
Else
oddNodes = oddNodes

End If

Next




fpointinpolygon = oddNodes

End Function

 

[nira123]

Following are the edited code to check points on the polygon in addition to points on the polygon:

Function fpointinpolygon(rXY As Range, rpolyXY As Range) As Boolean
' --------------------------------------------------------------
' Comments:
' Function checks if X,Y given in rXY falls within or on complex
' polygon as defined by node list rpolyXY.
' rXY to be 2 cell range with one X and one Y value
' rpolyXY to be 2 column range with for each node on the polygon _
' the X and the Y point
'
' Arguments:
' rXY (Range) = Coordinates of point to be checked
' rpolyXY (Range) = Coordinates of points defining the polygon
'
' Date Developer Comment
' --------------------------------------------------------------
' 10/07/13 sijpie Initial version. Taken from mrexcel.com forums
' Does point fall within polygon? VBA Function
' Refrerenced from: Determining Whether A Point Is Inside A Complex Polygon which is the implementation in C++
' 08/11/13 AussieChuck Changed "j" variable from "=polySides-1" to "=polySides"
' 5/10/20 Nira123 Added extra codes accept points on the polygon


Dim i As Integer, j As Integer, polySides As Integer
Dim oddNodes As Boolean
Dim x As Double, y As Double
Dim p, q, r, s, t, u, v As Double
Dim aXY As Variant

oddNodes = False
x = rXY.Cells.Value2(1, 1)
y = rXY.Cells.Value2(1, 2)
aXY = rpolyXY.Value

polySides = rpolyXY.Rows.Count
voidSides = rXY.Rows.Count - 1

j = polySides



For i = 1 To polySides

p = (y - aXY(i, 2))
q = (x - aXY(i, 1))
r = (aXY(j, 2) - aXY(i, 2))


If (((aXY(i, 2) < y And aXY(j, 2) >= y) _
Or (aXY(j, 2) < y And aXY(i, 2) >= y)) _
And (aXY(i, 1) <= x Or aXY(j, 1) <= x)) Then
oddNodes = oddNodes Xor ((aXY(i, 1) + (y - aXY(i, 2)) / (aXY(j, 2) - aXY(i, 2)) * (aXY(j, 1) - aXY(i, 1)) <= x))
End If


j = i
Next i



For i = 1 To polySides - 1
p = (y - aXY(i, 2))
q = (x - aXY(i, 1))
s = aXY(i + 1, 2) - aXY(i, 2)
t = (aXY(i + 1, 1) - aXY(i, 1))
u = VBA.Sqr(s ^ 2 + t ^ 2)
v = VBA.Sqr(p ^ 2 + q ^ 2)

If (q = 0 And p = 0) Then
oddNodes = True
i = polySides

ElseIf q = 0 Or t = 0 Then
oddNodes = oddNodes

ElseIf ((p / q) = (s / t) And (u / v) >= 1) Then
oddNodes = True
i = polySides
Else
oddNodes = oddNodes

End If

Next




fpointinpolygon = oddNodes

End Function

Sorry. I meant
edited code to check points on the polygon in addition to points inside the polygon

 

[Clark McCoy]

I would first point you to Message #4 in this thread. Then I would refer you to the original article in my mini-blog where I first posted my code...

Test Whether A Point Is In A Polygon Or Not

The following are responses I gave as follow ups to people's questions within the above linked article. If you read through the entire thread, you will see them. If you do not want to read the entire thread, I believe these three responses I gave might be of interest to you...

See this link for the answer I gave someone with the same question you are asking...

Test Whether A Point Is In A Polygon Or Not - Page 2

Some thoughts I had about points lying on the polygon itself (note the two links below take you to different Messages even though their text reads the same)...

Test Whether A Point Is In A Polygon Or Not - Page 3

Test Whether A Point Is In A Polygon Or Not - Page 3

Mr Rothstein,
Thanks for all the efforts and guidance provided on this topic.
I am working on a mapping project that involves identifying in which EMS District an address is located.

I have the address Long and Lat.

I have a KML file that contains the polygon data for each district. There are 8 districts. 4 of them are contiguous. The other 4 have polygons with "HOLES" in them due to "finger incorporation" of the district. (ie. the City incorporated subdivisions that are not in the outerboudary of the city's district. These finger incorporations are part of the city's district and are excluded from the neighboring district by use of the innerboundary that effectively puts a hole in the neighboring district. There are multiple innerboundaries that represent multiple subdivisions

I hope I explained that okay.


My question is: How would I represent the polygon data so the hole is considered as "not in the polygon"? or... is this function only for contiguous polygons with no "holes"?

If it is only of contiguous polygons, I am guessing that I could create polygons for each of the inner boundaries and evaluate the results to determine the innermost polygony that contains the point to determine the correct "district"?

example of the KML with outerboundary and innerboundary (truncated outerboundary in the first polygon due to character constraints:


<Placemark id="ID_00007">
<name>clarkville-ranch</name>
<Polygon>
<outerBoundaryIs><LinearRing><coordinates> -76.93033272036598,35.65822177734783,0 -76.93035141402507,35.65907157144127,0 -76.9303657620038,35.66005851889526,0 -76.93038066956753,35.66092473605358,0 -76.93039594078232,35.66180968032866,0 -76.93040975391376,35.66285054812393,0 -76.93042547335926,35.66391566425705,0 -76.93044489269735,35.66516547406745, -76.93033272036598,35.65822177734783,0 </LinearRing></innerBoundaryIs>
<innerBoundaryIs><LinearRing><coordinates> -77.02245280814664,35.53501304645273,0 -77.02244186517248,35.53501372835619,0 -77.02242675079226,35.53501313690408,0 -77.02240913374452,35.5350118194867,0 -77.02240494551198,35.53501123647255,0 -77.02240075730155,35.53501065255707,0 -77.02239656487342,35.53501024167734,0 -77.02238816753956,35.53500993181545,0 -77.02238060919251,35.53500963832138,0 -77.02237474179654,35.53500902615634,0 -77.02236972904628,35.53500774270398,0 -77.02245280814664,35.53501304645273,0</coordinates></LinearRing></innerBoundaryIs>
</Polygon>
<Polygon>
<outerBoundaryIs><LinearRing><coordinates> -77.01556102306847,35.55556465556606,0 -77.01552573990345,35.55559122126887,0 -77.01505219245399,35.55595179549939,0 -77.01510508349175,35.55597301306856,0 -77.01568523577878,35.55620574582098,0 -77.01620794614536,35.55582646818655,0 -77.01621679936345,35.55582004474963,0 -77.01616829332295,35.55580051221799,0 -77.0158587294157,35.55567585719047,0 -77.01556853358196,35.5555590000255,0 -77.01556102306847,35.55556465556606,0</coordinates></LinearRing></outerBoundaryIs>
</Polygon>
</Placemark>

 

[Rick Rothstein]

The "is it in the polygon" algorithm assumes no holes in the polygon. It sounds like you have figured out how to handle the holes though... make separate polygons for the district as a whole and for each hole in it, then test your point against each making sure the point lies in your district's polygon but not in any of the hole's polygons. Given how the algorithm works (counting lines crossed, that is the only approach that I can think of which would work.