Does point fall within polygon? VBA Function

sijpie · Jul 10, 2013

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

A2tz4zbUgeWf8OjuIbeJf4e9ZC8KGbFyXYcWSLhi4cE=w267-h201-p-no

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:

Function PointInPolygon(rXY As Range, rpolyXY As Range) As Boolean ' Function checks if X,Y given in rXY falls within 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 Dim i As Integer, j As Integer, polySides As Integer Dim oddNodes As Boolean Dim x As Double, y 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 j = polySides - 1 For i = 1 To polySides 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 PointInPolygon = oddNodes End Function

nira123 · Oct 2, 2020

Rick Rothstein said:
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 · Oct 4, 2020

Rick Rothstein said:
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 · Oct 4, 2020

nira123 said:
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 · Jan 31, 2021

Rick Rothstein said:
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 · Jan 31, 2021

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.

Does point fall within polygon? VBA Function

sijpie

Well-known Member

nira123

New Member

Excel Facts

nira123

New Member

nira123

New Member

Clark McCoy

New Member

Rick Rothstein

MrExcel MVP

Similar threads

Forum statistics

Share this page

Does point fall within polygon? VBA Function

sijpie

Well-known Member

nira123

New Member

Excel Facts

nira123

New Member

nira123

New Member

Clark McCoy

New Member

Rick Rothstein

MrExcel MVP

Similar threads

Forum statistics

Share this page

We've detected that you are using an adblocker.

Which adblocker are you using?

Disable AdBlock

Disable AdBlock Plus

Disable uBlock Origin

Disable uBlock