Ive come across the need to determine if a point is inside of a region or not. Yes, Windows API provides this functionality, as does .Net. But I’ve heard that the Windows API does not work on all platforms, and the .Net approach is inherently tied to GDI which makes it messy. Instead, a simple evaluation using a rather simple principle is much easier.

For theory on why this works, as well as where I got the original C++ code: http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/

Why am I posting this if it is just converted code? Because it took me ages to find that algorithm. I spent tons of time trying different keyword searches, checking my notes on Topology from calculus class, etc before I found it. So I figured I’d post this up in case someone searches for something similar.

Here is my VB.Net code. Quite simple. For non-.Net folk, the variable type Drawing.PointF is merely a structure that holds a floating point coordinate. It can easily be replaced with your own structure.

Function InsidePolygon(ByVal polygon() As Drawing.PointF, ByVal point As Drawing.PointF) As Integer
        '-Polygon() is the array of points that make up the polygon
        '--point is the point in question.  This function will return a 0 if
        '--point is outside the polygon, a 1 if it is inside
 
        '-- See http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/ for why this works
 
        Dim i As Integer
        Dim j As Integer
        Dim c As Integer = 0
 
        '-npol is the number of points in the polygon, which also happens 
        '--to be the number of sides
        Dim npol As Int32 = UBound(polygon) + 1
        i = 0
        j = npol - 1
 
        '-To the best of my knowledge, here is what happens:
        '--Take the point in questin and draw a ray from it to the right.  If it intersects
        '--an even number of lines, it is outside the polygon.  If odd, it is inside
        '--Since each point connects with the next point in the array to form a line,
        '--and the polygon is closed, we can check to see if we "go through" it.
        Do While i < npol
            If (((polygon(i).Y <= point.Y) AndAlso (point.Y < polygon(j).Y)) OrElse ((polygon(j).Y <= point.Y) AndAlso (point.Y < polygon(i).Y)))  AndAlso (point.X < (polygon(j).X - polygon(i).X) * (point.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X) Then
                c = Not c
            End If
            j = i
            i += 1
        Loop
 
        '1=inside
        '0=outside
        Return c
    End Function

Function PointInPolygon(ByVal Point As TV_2DVECTOR, ByVal Polygon As TV_2DVECTOR()) As Boolean
    If Polygon.Length < 3 Then Return False
 
    Dim V1 As TV_2DVECTOR, V2 As TV_2DVECTOR
    Dim Inside As Boolean = False
    Dim Old As TV_2DVECTOR = Polygon(Polygon.Length - 1)
 
    For Each V As TV_2DVECTOR In Polygon
        If V.x > Old.x Then
            V1 = Old : V2 = V
        Else
            V1 = V : V2 = Old
        End If
 
        If (V.x < Point.x) = (Point.x <= Old.x) AndAlso _
            (Point.y - V1.y) * (V2.x - V1.x) < (V2.y - V1.y) * (Point.x - V1.x) Then
 
            Inside = Not Inside
        End If
 
        Old = V
    Next
 
    Return Inside
End Function

Obligatory pic to show that it works: