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: