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

AussieChuck · Nov 8, 2013

Hi sijpie,

Thank you for this example. I was looking for precisely an algorithm like this.

Just a small correction. When I used it in my project I got some false positives and after reviewing the original code where you took the algorithm I figured out why.

In their code the variable "j" is assigned the value "polyLines-1" because their arrays start at 0, in your case the arrays start at 1 so the correct assignment is "j=polyLines". After this fix it worked beautifully.

I'm attaching the amended code in case it's of use to anyone.

Cheers,

Code:

Function fPointInPolygon(rXY As Range, rpolyXY As Range) As Boolean

' --------------------------------------------------------------
' Comments:
'   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
'
' 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
' http://www.mrexcel.com/forum/excel-questions/713005-does-point-fall-within-polygon-visual-basic-applications-function.html
' Refrerenced from: http://alienryderflex.com/polygon/ which is the implementation in C++
' 08/11/13      AussieChuck        Changed "j" variable from "=polySides-1" to "=polySides"

        
    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
    
    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
    
    fPointInPolygon = oddNodes
    
End Function

Rick Rothstein · Nov 8, 2013

AussieChuck said:

Hi sijpie,

Thank you for this example. I was looking for precisely an algorithm like this.

Just a small correction. When I used it in my project I got some false positives and after reviewing the original code where you took the algorithm I figured out why.

In their code the variable "j" is assigned the value "polyLines-1" because their arrays start at 0, in your case the arrays start at 1 so the correct assignment is "j=polyLines". After this fix it worked beautifully.

I'm attaching the amended code in case it's of use to anyone.

Cheers,

Code:

Function fPointInPolygon(rXY As Range, rpolyXY As Range) As Boolean

' --------------------------------------------------------------
' Comments:
'   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
'
' 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
' http://www.mrexcel.com/forum/excel-questions/713005-does-point-fall-within-polygon-visual-basic-applications-function.html
' Refrerenced from: http://alienryderflex.com/polygon/ which is the implementation in C++
' 08/11/13      AussieChuck        Changed "j" variable from "=polySides-1" to "=polySides"

        
    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
    
    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
    
    fPointInPolygon = oddNodes
    
End Function

Your function reports the wrong value for the point specified by G12:H12... it returns FALSE, but the point is actually inside the polygon. I would also point out that the original table shows the wrong value for the point specified by G9:H9... it shows the macro the OP used as returning TRUE, but that point is actually outside of the polygon. Here is my code (note the arguments are slightly different... instead of a range for the points being tested, I input the coordinates for the point separately)... while it is slightly shorter than the original function as well as your modification to it, I believe my UDF (user defined function) will always return the correct value.

Code:

Public Function PtInPoly(Polygon As Range, Xcoord As Double, Ycoord As Double) As Boolean
  Dim x As Long, m As Double, b As Double, Poly As Variant, NumSidesCrossed As Long
  Poly = Polygon
  For x = 1 To UBound(Poly) - 1
    If Poly(x, 1) > Xcoord Xor Poly(x + 1, 1) > Xcoord Then
      m = (Poly(x + 1, 2) - Poly(x, 2)) / (Poly(x + 1, 1) - Poly(x, 1))
      b = (Poly(x, 2) * Poly(x + 1, 1) - Poly(x, 1) * Poly(x + 1, 2)) / (Poly(x + 1, 1) - Poly(x, 1))
      If m * Xcoord + b > Ycoord Then NumSidesCrossed = NumSidesCrossed + 1
    End If
  Next
  PtInPoly = NumSidesCrossed Mod 2
End Function

HOW TO INSTALL UDFs
------------------------------------
If you are new to UDFs, they are easy to install and use. To install it, simply press ALT+F11 to go into the VB editor and, once there, click Insert/Module on its menu bar, then copy/paste the above code into the code window that just opened up. That's it.... you are done. You can now use NameOfTheUDF just like it was a built-in Excel function. For example, in the originally posted table of values, put this formula in I6 and copy it down...

=PtInPoly(B$5:C$10,G6,H6)

Note the polygon range must close (meaning the first point's coordinates must also appear at the bottom of the range as well) and also note the arguments, in order, are the polygon range (containing the x and y coordinates), the X-coordinate of the point being tested and the Y-coordinate of the point being tested.

Rick Rothstein · Nov 8, 2013

Rick Rothstein said:
I believe my UDF (user defined function) will always return the correct value.

I think I may need to add to the above slightly. Points extremely close to, or theoretically lying on, the polygon borders may or may not report back correctly... the vagrancies of floating point math, coupled with the limitations that the "significant digits limit" in VBA imposes, can rear its ugly head in those circumstances producing values that can calculate to either side of the polygon border being tested (remember, a mathematical line has no thickness, so it does not take too much of a difference in the significant digits to "move" a calculated point's position to one side or the other of such a line).

sijpie · Nov 11, 2013

Interesting. I never tested the function I had for complicated polygons. The one I needed it for was a 'normal' five sided polygon. Anyway good to know there is something really correct, I'll compare the results of the two if I get some time. I have to confess that the values in the table are incorrect, I modified them but not the results, as the original coordinates could be sensitive info....

And talking about points really close to the border reminds me of the Mandelbrot figures....

Rick Rothstein · Nov 11, 2013

For those who might be interested, I posted a mini-blog article here...

Test Whether A Point Is In A Polygon Or Not

which includes an expanded PtInPoly function that includes some error checking. The article also includes an attachment where you can see the function perform its action visually.

AussieChuck · Nov 21, 2013

Rick Rothstein said:
Your function reports the wrong value for the point specified by G12:H12... it returns FALSE, but the point is actually inside the polygon. I would also point out that the original table shows the wrong value for the point specified by G9:H9... it shows the macro the OP used as returning TRUE, but that point is actually outside of the polygon. Here is my code (note the arguments are slightly different... instead of a range for the points being tested, I input the coordinates for the point separately)... while it is slightly shorter than the original function as well as your modification to it, I believe my UDF (user defined function) will always return the correct value.

Code:

Public Function PtInPoly(Polygon As Range, Xcoord As Double, Ycoord As Double) As Boolean Dim x As Long, m As Double, b As Double, Poly As Variant, NumSidesCrossed As Long Poly = Polygon For x = 1 To UBound(Poly) - 1 If Poly(x, 1) > Xcoord Xor Poly(x + 1, 1) > Xcoord Then m = (Poly(x + 1, 2) - Poly(x, 2)) / (Poly(x + 1, 1) - Poly(x, 1)) b = (Poly(x, 2) * Poly(x + 1, 1) - Poly(x, 1) * Poly(x + 1, 2)) / (Poly(x + 1, 1) - Poly(x, 1)) If m * Xcoord + b > Ycoord Then NumSidesCrossed = NumSidesCrossed + 1 End If Next PtInPoly = NumSidesCrossed Mod 2 End Function

HOW TO INSTALL UDFs
------------------------------------
If you are new to UDFs, they are easy to install and use. To install it, simply press ALT+F11 to go into the VB editor and, once there, click Insert/Module on its menu bar, then copy/paste the above code into the code window that just opened up. That's it.... you are done. You can now use NameOfTheUDF just like it was a built-in Excel function. For example, in the originally posted table of values, put this formula in I6 and copy it down...

=PtInPoly(B$5:C$10,G6,H6)

Note the polygon range must close (meaning the first point's coordinates must also appear at the bottom of the range as well) and also note the arguments, in order, are the polygon range (containing the x and y coordinates), the X-coordinate of the point being tested and the Y-coordinate of the point being tested.

Hi Rick,

Just for the sake of clarity, I'm not sure why you say the reported value for G12:H12 (2 Ar Est) is incorrect, please see attached image of the function run over the sample data. The function correctly reports the only two points inside the polygon.

[TABLE="width: 291"]
<colgroup><col><col span="2"><col></colgroup><tbody>[TR]
[TD]NorthingX[m][/TD]
[TD]Yes/No[/TD]
[TD][/TD]
[TD][/TD]
[/TR]
[TR]
[TD]1 A Est[/TD]
[TD="align: right"]559,008.51[/TD]
[TD="align: right"]309,204.47[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]1 Ar Est[/TD]
[TD="align: right"]550,000.30[/TD]
[TD="align: right"]313,130.16[/TD]
[TD="align: center"]TRUE[/TD]
[/TR]
[TR]
[TD]1 Ar Vest[/TD]
[TD="align: right"]543,011.50[/TD]
[TD="align: right"]313,106.58[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]1 I Est[/TD]
[TD="align: right"]556,226.56[/TD]
[TD="align: right"]312,713.64[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]1 K Vest-Blejesti[/TD]
[TD="align: right"]539,357.63[/TD]
[TD="align: right"]313,165.48[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]2 A Est[/TD]
[TD="align: right"]559,388.41[/TD]
[TD="align: right"]309,234.32[/TD]
[TD="align: center"]FALSE
[/TD]
[/TR]
[TR]
[TD]2 Ar Est[/TD]
[TD="align: right"]549,925.25[/TD]
[TD="align: right"]313,140.10[/TD]
[TD="align: center"]TRUE[/TD]
[/TR]
[TR]
[TD]2 Ar Vest[/TD]
[TD="align: right"]543,080.28[/TD]
[TD="align: right"]312,970.75[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]2 I Est[/TD]
[TD="align: right"]554,430.45[/TD]
[TD="align: right"]313,551.15[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]2 P Vest[/TD]
[TD="align: right"]545,170.00[/TD]
[TD="align: right"]310,055.00[/TD]
[TD="align: center"]FALSE[/TD]
[/TR]
[TR]
[TD]3 A Est[/TD]
[TD="align: right"]559,722.95[/TD]
[TD="align: right"]309,279.51[/TD]
[TD="align: center"]FALSE
[/TD]
[/TR]
</tbody>[/TABLE]

-- removed inline image ---

Rick Rothstein · Nov 21, 2013

AussieChuck said:
Hi Rick,

Just for the sake of clarity, I'm not sure why you say the reported value for G12:H12 (2 Ar Est) is incorrect, please see attached image of the function run over the sample data. The function correctly reports the only two points inside the polygon.

AussieChuck said:
Hi Rick,
Just for the sake of clarity, I'm not sure why you say the reported value for G12:H12 (2 Ar Est) is incorrect, please see attached image of the function run over the sample data. The function correctly reports the only two points inside the polygon.

You are right and I was wrong... you formula does report the correct values. I saw what I did wrong that led me to post what I did (because I just did it again when I retested your code). I wrote this formula in J6 (the column I tested your function in)...

=fPointInPolygon(G6:H6,C5:D10)

and copied I down, but I had forgotten to "lock" the polygon range using $ signs like this...

=fPointInPolygon(G6:H6,C$5:D$10)

so the polygon coordinates changed as I copied the formula down. I apologize for my mistake and the fact that it caused me to conclude your function did not work when, in fact, it appears to work quite correctly.

chrism216 · Dec 2, 2014

Wow

This is GOLD

i work with KMZ layers all the time, this will be EXTREMELY useful!!!

Thank you!

Rick Rothstein · Dec 2, 2014

chrism216 said:
Wow

This is GOLD

i work with KMZ layers all the time, this will be EXTREMELY useful!!!

I have no idea what KMZ layers are, nor am I sure whose function you found useful (mine or AussieChuck's) in dealing with them, but I am glad you found something in this thread helpful.

chrism216 said:
Thank you!

I am sure AussieChuck would join me in saying, "You are quite welcome!"

Does point fall within polygon? VBA Function

sijpie

Well-known Member

Excel Facts

AussieChuck

New Member

Rick Rothstein

MrExcel MVP

Rick Rothstein

MrExcel MVP

sijpie

Well-known Member

Rick Rothstein

MrExcel MVP

AussieChuck

New Member

Rick Rothstein

MrExcel MVP

chrism216

Board Regular

Rick Rothstein

MrExcel MVP

Similar threads

Forum statistics

Share this page

Does point fall within polygon? VBA Function

Well-known Member

Excel Facts

New Member

MrExcel MVP

MrExcel MVP

Well-known Member

MrExcel MVP

New Member

MrExcel MVP

Board Regular

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