Page 1 of 5 123 ... LastLast
Results 1 to 10 of 43

Thread: Test Whether A Point Is In A Polygon Or Not

  1. #1
    Forum Guru Rick Rothstein's Avatar
    Join Date
    Feb 2012
    Posts
    659
    Rep Power
    13

    Test Whether A Point Is In A Polygon Or Not

    This function is not one that many will find a use for, but if you ever need its functionality, then here it is. The function can be called from other VB code or used as a UDF (user defined function) directly on a worksheet. What it does is tell you whether a point is located inside a polygon (simple or complex, convex or concave) or not. That's it... if you should ever need such a function, this is the code for it...

    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 Poly = Polygon If Not (Poly(LBound(Poly), 1) = Poly(UBound(Poly), 1) And _ Poly(LBound(Poly), 2) = Poly(UBound(Poly), 2)) Then If TypeOf Application.Caller Is Range Then PtInPoly = "#UnclosedPolygon!" Else Err.Raise 998, , "Polygon Does Not Close!" End If Exit Function ElseIf UBound(Poly, 2) - LBound(Poly, 2) <> 1 Then If TypeOf Application.Caller Is Range Then PtInPoly = "#WrongNumberOfCoordinates!" Else Err.Raise 999, , "Array Has Wrong Number Of Coordinates!" End If Exit Function End If 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 m * Xcoord + b > Ycoord Then NumSidesCrossed = NumSidesCrossed + 1 End If Next PtInPoly = CBool(NumSidesCrossed Mod 2) End Function
    The theory behind the function is simplicity itself... start at the point being tested and project a line from that point outward in any direction (I chose straight up as that made some of the math easier) and count how many polygon sides it crosses... if the number of sides is odd, the point lies inside the polygon and if the number of sides is even, the point lies outside of the polygon. The function will return either True, False (for inside/outside respectively) or an error message (see below). The first argument is the X-Coordinate and the second argument is the Y-Coordinate of the point you want to test for being inside the polygon or not. The third argument is either a two-dimensional array of numbers (when called from another VB code procedure) or a range of numbers consisting of two columns and as many rows as needed (when called from a worksheet). The numbers describe the nodes composing the polygon.

    NOTE #1: The polygon must be closed, meaning the first listed point and the last listed point must be the same. If they are not the same, the function will raise "Error #998 - Polygon Does Not Close!" if the function was called from other VB code or it will return #UnclosedPolygon! if called from the worksheet. Normally, if called from a worksheet, you would probably be using the function in a formula something like this...

    =IF(PtInPoly(B9,C9,E18:F37),"In Polygon","Out Polygon")

    In that case, the formula will return a #VALUE! error, not the #UnclosedPolygon! error, because the returned value to the IF function is not a Boolean; however, if you select the "PtInPoly(B9,C9,E18:F37)" part of the function in the Formula Bar and press F9, it will show you the returned value from the PtInPoly function as being #UnclosedPolygon!.

    NOTE #2: The range or array specified for the third argument must be two-dimensional. If it is not, then the function will raise "Error #999 - Array Has Wrong Number Of Coordinates!" if the function was called from other VB code or it will return #WrongNumberOfCoordinates! if called from the worksheet. Error reporting when called from the worksheet will be the same as described in NOTE #1.

    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).

    NOTE #4: While I think error checking is a good thing, the setup for this function is rather straightforward and, with the possible exception of the requirement for the first and last point needing to be the same, easy enough for the programmer to maintain control over during coding. If you feel confident in your ability to meet the needs of NOTE #1 and NOTE #2 without having the code "looking over your shoulder", then the function can be simplified down to this compact code...

    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 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 m * Xcoord + b > Ycoord Then NumSidesCrossed = NumSidesCrossed + 1 End If Next PtInPoly = CBool(NumSidesCrossed Mod 2) End Function
    Attached Files Attached Files
    Last edited by Rick Rothstein; 03-01-2017 at 01:42 AM.

  2. #2
    Forum Guru Rick Rothstein's Avatar
    Join Date
    Feb 2012
    Posts
    659
    Rep Power
    13
    Just replying to this thread to alert people who have looked at this thread previously that I have now included an attachment which will allow you to move a point around a chart showing a polygon using embedded scroll bars... as the point moves in and out of the polygon, a message above the chart shows with the the PtInPoly function thinks the point is inside the polygon or not.

  3. #3

  4. #4
    Junior Member
    Join Date
    Nov 2013
    Posts
    2
    Rep Power
    0
    Hi Rick,

    Thank you for posting. Over the last couple weeks, I've been testing sijpie's code about point in polygon, but I discovered quite a few errors. Your code has worked flawlessly thus far.
    I had one question about the logic and a possibility to increase speed.
    For my task, I loop through 1000's of polygons with anywhere from 10-100 coordinate points in search of the correct pointinpolygon. Is it always necessary to loop through the entire array of polygon coordinates? Would it increase speed to insert a "quit/exit loop" if any of the polygon coordinates does not satisfy the test, or does the logic require all coordinates to be tested? Thanks again!

  5. #5
    Forum Guru Rick Rothstein's Avatar
    Join Date
    Feb 2012
    Posts
    659
    Rep Power
    13
    Quote Originally Posted by Dan1445 View Post
    Hi Rick,

    Thank you for posting. Over the last couple weeks, I've been testing sijpie's code about point in polygon, but I discovered quite a few errors. Your code has worked flawlessly thus far.
    I had one question about the logic and a possibility to increase speed.
    For my task, I loop through 1000's of polygons with anywhere from 10-100 coordinate points in search of the correct pointinpolygon. Is it always necessary to loop through the entire array of polygon coordinates? Would it increase speed to insert a "quit/exit loop" if any of the polygon coordinates does not satisfy the test, or does the logic require all coordinates to be tested? Thanks again!
    If your polygons were always convex, then yes, there might be a way to speed things up, but only a little bit; however, if not, then no, all polygon sides must be tested as non-convex polygons can get quite intricate in shape.

  6. #6
    Junior Member
    Join Date
    Mar 2014
    Posts
    1
    Rep Power
    0

    Thanks... and a tiny clean-up.

    Hi Rick,

    Thanks for sharing this solution. I'm working on an Excel-based scoring system for a cross-country hang gliding contest, and one of the things that needs to be checked while scoring is whether the pilot landed in an off-limits "Do Not Land" (DNL) area (like a pasture owned by an unwelcoming farmer). If he did, then he gets a ZERO! I'm working on adding the polygons describing these DNL areas to the scoring system and using the pilot's reported landing coordinates to automatically check whether he landed in a DNL area. Your function should work beautifully. :-)

    By the way, I see in the function (both versions of it) the declaration of four variables that aren't used: LB1, LB2, UB1, and UB2.

    Thanks again,

    Eric

  7. #7
    Junior Member
    Join Date
    Mar 2014
    Posts
    1
    Rep Power
    0

    Rick you rock! Is it possible to include the polygon geometry in the VBA code?

    Thanks this is a really useful function. I am using it to estimate soil type from Cone Penetration Test data. I digitized a xy plot from a scientific paper with 9 zones predicting soil type and created polygons for each of the zones to test where the point lies. It works great.

    Currently the geometry of the polygons is referenced by cell values in a work sheet, I was wondering however whether it would be possible to include the polygon geometry in the VBA code, so that I can create a UDF that I can call at any time, without the need to reference back to the polygon xy data in a worksheet?

    Thanks
    Neal

  8. #8
    Forum Guru Rick Rothstein's Avatar
    Join Date
    Feb 2012
    Posts
    659
    Rep Power
    13
    Quote Originally Posted by eric.carden View Post
    Hi Rick,

    By the way, I see in the function (both versions of it) the declaration of four variables that aren't used: LB1, LB2, UB1, and UB2.
    Thanks for noting that... I fixed the code in my original article by removing them.

  9. #9
    Forum Guru Rick Rothstein's Avatar
    Join Date
    Feb 2012
    Posts
    659
    Rep Power
    13
    Quote Originally Posted by neal_at_sea View Post
    Thanks this is a really useful function. I am using it to estimate soil type from Cone Penetration Test data. I digitized a xy plot from a scientific paper with 9 zones predicting soil type and created polygons for each of the zones to test where the point lies. It works great.
    Wow, great! I am so glad you made that comment as I often wonder if anyone actually puts any of the stuff I post to practical use.


    Quote Originally Posted by neal_at_sea View Post
    Currently the geometry of the polygons is referenced by cell values in a work sheet, I was wondering however whether it would be possible to include the polygon geometry in the VBA code, so that I can create a UDF that I can call at any time, without the need to reference back to the polygon xy data in a worksheet?
    If I understand you correctly, you have predefined polygons that will not change and you want to bundle their coordinates directly into my function. Rather than do that, I would leave my function as is and create new functions that have the coordinates predefined in them and have that new function call my PtInPoly function passing the predefined array of coordinates to it. Here is an example of what I am thinking using a triangle as the predefined polygon. The triangle coordinates will be (1,2), (9,3) and (4,7). Here is the function I am suggesting you create for this fixed polygon...

    Code:
    Function PtInTriangle(Xcoord As Double, Ycoord As Double) As Boolean
    
      '  Remember, the shape must be closed, so there must
      '  be one array element more than shape corners and
      '  the first and last coordinates must be the same
      Dim Triangle(1 To 4, 1 To 2) As Double
      
      '        Define the Triangle
      '        -------------------
      '     Xcoords     :     Ycoords
      Triangle(1, 1) = 1: Triangle(1, 2) = 2
      Triangle(2, 1) = 9: Triangle(2, 2) = 3
      Triangle(3, 1) = 4: Triangle(3, 2) = 7
      Triangle(4, 1) = 1: Triangle(4, 2) = 2
      
      '  Call the PtInPoly function using the above declared coordinates
      PtInTriangle = PtInPoly(Xcoord, Ycoord, Triangle)
    
    
    End Function
    You can separate the assignments to the Triangle array onto separate lines of code if you want, but I chose to put two per line of code (using the colon operator to separate the two assignments) so you could more easily see the X, Y coordinate relationship. Of course, you would create new function for each of your predefined shapes. One thought depending on how you plan to call your new functions... if you will need to iterate them instead of call specific ones by name, then you can create one new function that include all definitions in it, add an Index argument to your new function's argument list and then use that Index value in a Select Case block to call the particularly iterated polygon.
    Last edited by Rick Rothstein; 03-01-2017 at 01:34 AM.

  10. #10
    Junior Member
    Join Date
    May 2014
    Posts
    1
    Rep Power
    0

    Arrow another silly problem

    Rick ! I appretiate your activities and your willingness to show your knowledge in this forum.
    I need exactly something like this to build simple selection of scroll compressors according the suction and condensing temperatures which are coordinates, which will or wont be in working area of compressor = polygon.

    i have another silly problem with that. ..as i downloaded the excel , and i have tryed to copy the sheet from your excel to mine,
    the function was not operatable..... and i am sure i did copy all the code within VB into the right sheet, via "insert" / "module" , paste there the code , and saved everithing..

    but function in new excel does not work...
    do you have clue, what should be the problem ??

    thank you wery much for your answer
    Richard

    Quote Originally Posted by Rick Rothstein View Post
    Wow, great! I am so glad you made that comment as I often wonder if anyone actually puts any of the stuff I post to practical use.



    If I understand you correctly, you have predefined polygons that will not change and you want to bundle their coordinates directly into my function. Rather than do that, I would leave my function as is and create new functions that have the coordinates predefined in them and have those new function call my PtInPoly function passing the predefined array of coordinates to it. Here is an example of what I am thinking using a triangle as the predefined polygon. The triangle coordinates will be (1,2), (9,3) and (4,7). Here is the function I am suggesting you create for this fixed polygon...

    Code:
    Function PtInTriangle(Xcoord As Double, Ycoord As Double) As Boolean
    
      '  Remember, the shape must be closed, so there must
      '  be one array element more than shape corners and
      '  the first and last coordinates must be the same
      Dim Triangle(1 To 4, 1 To 2) As Double
      
      '        Define the Triangle
      '        -------------------
      '     Xcoords     :     Ycoords
      Triangle(1, 1) = 1: Triangle(1, 2) = 2
      Triangle(2, 1) = 9: Triangle(2, 2) = 3
      Triangle(3, 1) = 4: Triangle(3, 2) = 7
      Triangle(4, 1) = 1: Triangle(4, 2) = 2
      
      '  Call the PtInPoly function using the above declared coordinates
      PtInTriangle = PtInPoly(Xcoord, Ycoord, Triangle)
    
    
    End Function
    You can separate the assignments to the Triangle array onto separate lines of code if you want, but I chose to put two per line of code (using the colon operator to separate the two assignments) so you could more easily see the X, Y coordinate relationship. Of course, you would create new function for each of your predefined shapes. One thought depending on how you plan to call your new functions... if you will need to iterate them instead of call specific ones by name, then you can create one new function that include all definitions in it, add an Index argument to your new function's argument list and then use that Index value in a Select Case block to call the particularly iterated polygon.
    Last edited by rricki; 05-09-2014 at 05:46 PM.

Similar Threads

  1. This is a test Test Let it be
    By Admin in forum Test Area
    Replies: 6
    Last Post: 05-30-2014, 09:44 AM
  2. This is a test of Signature Block Variable Dim
    By alansidman in forum Test Area
    Replies: 0
    Last Post: 10-17-2013, 07:42 PM
  3. Test
    By Excel Fox in forum Den Of The Fox
    Replies: 0
    Last Post: 07-31-2013, 08:15 AM
  4. Replies: 4
    Last Post: 06-10-2013, 01:27 PM
  5. Test
    By Excel Fox in forum Word Help
    Replies: 0
    Last Post: 07-05-2011, 01:51 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •