MapWinGIS:SampleCode-VB Net:PartsContainingPoint

This is a back-up of the WIKI.
Not all links might work
We're working on a new wiki.

Main Page | Recent changes | View source | Page history | Log in / create account |

Printable version | Disclaimers | Privacy policy

Parts of a Polygon Containing a Point

This assumes you have a Polygon type shape, and want to determine which parts if any contain a point. If you have multiple parts to a shape, this can be important. It uses a combination of code from the MapWinGIS source code for PointInShape, and what I learned from the following link: Determining if a Point is in a Polygon from the Crossing Number. I am still learning this, and haven't tested it yet, so this is by no means guaranteed to work.

     'Returns Nothing or an Integer array of part numbers.
     'If the result is nothing, or the number of parts is even, then the point can also
     'be thought of as being outside the shape.
     Public Function PartsContainingPoint(ByVal InShape As MapWinGIS.Shape, ByVal InPoint As MapWinGIS.Point) As Object
         Dim OutParts() As Integer
         Dim OutPartCount As Integer = -1
         Dim nPart, nPoint, nPointMax As Integer
         Dim CrossCount As Integer = 0
         Dim x1, x2, y1, y2, y1y2 As Double
         Dim dx, dy, xint As Double
         Dim DoNotCross As Boolean = True
         'Count Crossings of a ray extending out from P along X axis
         'Additional Crossing Rules:
         '1.    an upward edge includes its starting endpoint, and excludes its final endpoint; 
         '2.    a downward edge excludes its starting endpoint, and includes its final endpoint; 
         '3.    horizontal edges are excluded; and 
         '4.    the edge-ray intersection point must be strictly right of the point P. 
         For nPart = 0 To InShape.NumParts - 1
             nPointMax = InShape.Part(nPart + 1) - 1
             For nPoint = InShape.Part(nPart) To nPointMax
                 x1 = InShape.Point(nPoint).x - InPoint.x
                 y1 = InShape.Point(nPoint).y - InPoint.y
                 If nPoint = nPointMax Then
                     'Loop to first point in part to ensure a closed shape
                     x2 = InShape.Point(InShape.Part(nPart)).x - InPoint.x
                     y2 = InShape.Point(InShape.Part(nPart)).y - InPoint.y
                     x2 = InShape.Point(nPoint + 1).x - InPoint.x
                     y2 = InShape.Point(nPoint + 1).y - InPoint.y
                 End If
                 y1y2 = y1 * y2
                 If y1y2 > 0.0 Then
                     'If the signs are the same then it does not cross
                     nPoint = nPoint + 1
                     GoTo Continue1
                 ElseIf (y1y2 = 0.0) Then
                     'Ray has intersected a vertex
                     If y1 = 0.0 Then 'Starting EndPoint intersects ray
                         If y2 < 0.0 Then 'Downward Edge
                             'Excludes Starting Endpoint y1
                             nPoint = nPoint + 1
                             GoTo Continue1
                         End If
                     Else 'Final Endpoint Intersects Ray
                         If y1 < 0.0 Then  'Upward Edge
                             'Excludes Final Endpoint y2
                             nPoint = nPoint + 1
                             GoTo Continue1
                         End If
                     End If
                 End If
                 If y1 = y2 Then
                     'Horizontal Edges are Excluded
                     nPoint = nPoint + 1
                     GoTo Continue1
                 End If
                 If (x1 > 0 And x2 > 0) Then
                     'both points are right of P
                     CrossCount = CrossCount + 1
                     nPoint = nPoint + 1
                     GoTo Continue1
                 End If
                 'Calculate Intersection with Y = 0 to see if it is right of P
                 'Given a constant slope, (xint - x1)/(0 - y1) = (x2 - x1)/(y2 - y1)
                 'substitute: (xint - x1) / (0 - y1) = dx/dy
                 '        so:  xint - x1 = -y1 * dx/dy
                 '       and:  xint = x1 - y1 * dx/dy
                 dy = y2 - y1
                 dx = x2 - x1
                 xint = x1 - y1 * (dx / dy)
                 If xint > 0.0 Then
                     CrossCount = CrossCount + 1
                 End If
             Next nPoint
             'If Crosscount is Odd, Point is in nPart
             If CrossCount Mod 2 = 1 Then
                 OutPartCount = OutPartCount + 1
                 ReDim Preserve OutParts(OutPartCount)
                 OutParts(OutPartCount) = nPart
             End If
         Next nPart
         PartsContainingPoint = OutParts
     End Function

Code Posted by Shade1974 on 12/20/2005

Retrieved from ""

This page has been accessed 2,295 times. This page was last modified on 20 December 2005, at 15:30.