Test Whether A Point Is In A Polygon Or Not

Hi Rick. I registered on this forum just to thank you for your code. I am using it in an application for a client that owns around 200 cranes (mobile cranes used in industry) - a system on the crane sends it's coordinates back to my server where I have pre-defined areas of responsibilities configured. Using your code, I can now determine when a crane enters a new area and alert that foreman (who is responsible for that specific area/polygon) that he is now responsible for that new crane. Brilliant!

Quote:

---

Originally Posted by NinjaTic

Hi Rick. I registered on this forum just to thank you for your code. I am using it in an application for a client that owns around 200 cranes (mobile cranes used in industry) - a system on the crane sends it's coordinates back to my server where I have pre-defined areas of responsibilities configured. Using your code, I can now determine when a crane enters a new area and alert that foreman (who is responsible for that specific area/polygon) that he is now responsible for that new crane. Brilliant!

---

Thank you for letting me know that my function has been so helpful to you in your work... I really appreciate the feedback. Funny, but when I posted that code, I figured it would be of novelty interest only to my readers; but you, and some others who posted above, have indicate that it has a variety of real-world applications... who would have thought. Thank you again for your feedback. By the way, now that you are a registered member of this forum, please come back often... both to "my little corner of the world" here and to the main forum itself (click the big Forum button under the forum's logo above) and posts question that you may have, offer solutions to question others ask when you are able to, or just look around to see what's going on.

NOTE #3: 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).

Apologies if this gets messed up - first posting .....

I have been doing some basic testing and find that generally when on boundary, I'm getting a false values. My thoughts on dealing with this is to check for X/Y values +/- .001% either side and if any return true, it's close enough to on the line to be true.

Can you see any faults with that ? I'm writing code for checking aircraft Centre of Gravity limits, so hoping to be reasonably accurate,

Love your work by the way :-)

TheCloud

Quote:

---

Originally Posted by theCloud

I have been doing some basic testing and find that generally when on boundary, I'm getting a false values. My thoughts on dealing with this is to check for X/Y values +/- .001% either side and if any return true, it's close enough to on the line to be true.

Can you see any faults with that ? I'm writing code for checking aircraft Centre of Gravity limits, so hoping to be reasonably accurate..

---

The following is untested because I do not have a data setup to use, nor a set of prescribed boundary points to check, but I think I modified everything correctly. Since you seem to have the necessary data, I'll let you check it out.:)

What I have done is resurrect an old IsNearLine function I had written about the same time I wrote the PtInPoly function (somewhere between 10 and 15 years ago now), modified its argument to accept line end points as defined in the PtInPoly function, and added a Tolerance constant (the Const statement) so you can play around with that value in order to fine-tune it. Since I had to modify part of PtInPoly to accommodate the call out to the IsNearLine function, I am posting all the code you will need below (it replaces you current copy of my PtInPoly function. To repeat, this is all untested, so I cannot guarantee it will work, but in my mind's eye, I do not see why it won't... please let me, and the readers of this thread, know how your experimentation with it works out. I would also note that I expect the calculations to go slower because of the added, repeated calls to the IsNearLine function, but I do not have a feel for how much (maybe you could let us know your impressions on that as well).

Code:

---

Public Function PtInPoly(Xcoord As Double, Ycoord As Double, Polygon As Variant) As Variant
  Dim x As Long, NumSidesCrossed As Long, m As Double, B As Double, Poly As Variant
  Const Tolerance As Double = 0.001
  Poly = Polygon
  For x = LBound(Poly) 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 IsNearLine(Poly(x, 1), Poly(x, 2), Poly(x + 1, 1), Poly(x + 1, 2), Xcoord, Ycoord, Tolerance) Then
        NumSidesCrossed = NumSidesCrossed + 1
      ElseIf m * Xcoord + B > Ycoord Then
        NumSidesCrossed = NumSidesCrossed + 1
      End If
    End If
  Next
  PtInPoly = CBool(NumSidesCrossed Mod 2)
End Function


Function IsNearLine(X1 As Long, Y1 As Long, X2 As Long, Y2 As Long, _
                    PX As Variant, PY As Variant, Tolerance As Variant) As Boolean
  Dim A As Double, B As Double, C As Double, DistPtToLine As Double
  If ((PX - X1) * (PX - X1) + (PY - Y1) * (PY - Y1) < Tolerance * Tolerance) Or _
      ((PX - X2) * (PX - X2) + (PY - Y2) * (PY - Y2) < Tolerance * Tolerance) Then
    IsNearLine = True
  Else
    A = Y2 - Y1
    B = X1 - X2
    C = X2 * Y1 - Y2 * X1
    DistPtToLine = Abs((A * PX + B * PY + C) / Sqr(A * A + B * B))
    If DistPtToLine <= Tolerance Then
      If X2 > X1 And PX > X1 And PX < X2 Then
        If Y2 > Y1 And PY > Y1 And PY < Y2 Or Y2 < Y1 And PY < Y1 And PY > Y2 Then
          IsNearLine = True
        End If
      ElseIf X2 < X1 And PX < X1 And PX > X2 Then
        If Y2 > Y1 And PY > Y1 And PY < Y2 Or Y2 < Y1 And PY < Y1 And PY > Y2 Then
          IsNearLine = True
        End If
      End If
    End If
  End If
End Function

---

Hi Rick,

First, thank you very much for creating this module.

I'm trying to use it for a test procedure for quality control.

The 4 sided polygon that I'm using is very small the X and Y coordinates are in the x0.3200, y0.3300 and x0.3400, y0.3500 range. Out to 4 decimal places.

I'm getting a Compile error: ByRef argument type mismatch.

It has highlighted the following

Code:

---

Public Function PtInPoly(Xcoord As Double, Ycoord As Double, Polygon As Variant) As Variant
  Dim x As Long, NumSidesCrossed As Long, m As Double, B As Double, Poly As Variant
  Const Tolerance As Double = 0.001
  Poly = Polygon
  For x = LBound(Poly) 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 IsNearLine(Poly

---

With "Poly" as being the culprit after If IsNearLine(Poly

I'm using a closed Polygon with 5 x & Y points the last XY being the same as the first one.

In my particular case this is the call out =PtInPoly(B40,C40,S39:T43)

B40 would be X and C40 Y, and S39:T43 the polygon points.

I'm using Excel 2010.

Thank you for your help.

You are providing a great service to us all.

Ps. I'm a Excel Noob.

Google CIE 1931

Hi Rick,

I was able to get the first code to work!

Thanks so much.

You really helped me a lot.

Cheers,

Hagen

Good day Rick,

Your code 'Public Function PtInPoly(Xcoord As Double, Ycoord As Double, Polygon As Variant) As Variant' works very well. I am writing to say thank you for creating it and also for answering questions and posting potential pitfalls.

Next, is this code offered as freeware, shareware, or another sort of fee schedule? I am not using it for any sort of profit at the present time, but if I elect to in the future I would like to know if there are any potential strings attached. Obviously I will cite you with credit as to the creator and authorship of the code where used. Please respond at our convenience. Thank you for your time.

Respectfully,


Brett

Cultural Resource Management
Master's Candidate
St. Cloud State University

Quote:

---

Originally Posted by Goodwood

Good day Rick,

Your code 'Public Function PtInPoly(Xcoord As Double, Ycoord As Double, Polygon As Variant) As Variant' works very well. I am writing to say thank you for creating it and also for answering questions and posting potential pitfalls.

Next, is this code offered as freeware, shareware, or another sort of fee schedule? I am not using it for any sort of profit at the present time, but if I elect to in the future I would like to know if there are any potential strings attached. Obviously I will cite you with credit as to the creator and authorship of the code where used. Please respond at our convenience. Thank you for your time.

---

Hi Brett,

Thank you for you nice comments... much appreciated. As for using the code... there are no strings attached... if I post something online without specifically marking it copyrighted or "restricted use" or some other such marking, then you are free to use it in anyway you see fit. With that said, if you make a commercial product using it, I would hope you would contact me and make a donation of some kind to me for my efforts, but that would be strictly voluntary on your part... to repeat, if not marked otherwise, you are free to use anything I post in anyway you see fit.

Hello,

first of all, thank you for your code. Im an optical engineer, and i need to mesh a polygon (equally distribute points) to calculate the homogenity of the luminance at these points, this is why your code is helpful to me.

However, i have a couple questions:

• Code:

  ---

  Poly = Polygon

  ---

  why is this line needed? declaring an other variable seems to be unnecessary to me, can i use just polygon instead of poly?
  
• Code:

  ---

  PtInPoly = CBool(NumSidesCrossed Mod 2)

  ---

  what is the exact purpose of CBool? NumSidesCrossed Mod 2 gives 1 or 0 (remember, PtInPoly is a variant, not boolean) which can be used as the condition input for IF, no need to make the code longer with CBoolean.
  
• you mention that the first and last point of the polygon have to be the same. Since this is a _must_ condition, why not write the code in such a way, that the last point would be added as the first point. this way no error correction would be necessary, since the last point would be automatically copied from the first point.
  
  

Quote:

---

Originally Posted by qetuol

However, i have a couple questions:

Code:

---

Poly = Polygon

---

why is this line needed? declaring an other variable seems to be unnecessary to me, can i use just polygon instead of poly?

---

The Polygon argument can be either a two-dimensional VBA array or a two-dimensional range. If it is a range, assigning that range to a Variant variable converts it to a two-dimensional VBA array so that the rest of the code ends up with the same kind of array as when a real two-dimensional array is inputted. The reason the assignment has to take place within the code is because the coercion to an array does not take place via the argument itself even if that argument is a Variant. So, that line of code makes the overall function flexible enough to handle a real array (assigning such an array to the Variant variable does not change its structure) or a range (because the range gets converted to a real array).

Quote:

---

Originally Posted by qetuol

Code:

---

PtInPoly = CBool(NumSidesCrossed Mod 2)

---

what is the exact purpose of CBool? NumSidesCrossed Mod 2 gives 1 or 0 (remember, PtInPoly is a variant, not boolean) which can be used as the condition input for IF, no need to make the code longer with CBoolean.

---

I wanted the function to return either TRUE or FALSE directly in case the function was to be used directly in a MessageBox or to fill a TextBox or any other number of uses besides as the argument to an IF function... the idea being the user can implement the function without having to take special steps to format the output for the occasion. As for why PtInPoly is a Variant and not a Boolean... that was so it could accommodate the error messages when called as a UDF directly on a worksheet.

Quote:

---

Originally Posted by qetuol

you mention that the first and last point of the polygon have to be the same. Since this is a _must_ condition, why not write the code in such a way, that the last point would be added as the first point. this way no error correction would be necessary, since the last point would be automatically copied from the first point.

---

It was a design decision to help a user not make a mistake. If the user accidentally grabbed the wrong number of rows from a table of coordinates and inputted that too short range of values, the function would alert the user to the error because the last point did not equal the first point... if I made the function close the polygon automatically, it would blindly calculate values and the user would not be aware some of the answers were incorrect... by forcing the user to make sure the polygon closed, he/she could never make a mistake of accidentally inputting too few points.