Point in Poly?

I've been thinking about this for interface stuff, avoiding making everything rectangular really.

Here's my proposed method ( technique, not even pseudo-code at this point ) and I'd be interested to hear if anyone has a better ( faster! ) method.

For each edge in the polygon, calculate a normal pointing directly outward from the center of the poly. When it comes to testing the point, calculate the dot product of the point relative to one of the edge's vertices and if it's positive, return false. If none of the edges return false, it's inside.

Perhaps coupled with some kind of basic distance check to eliminate precise testing.

How's that?

You can check point in poly with 100% precision by testing which side of each line the point is on. If it is on the inside side of all three, then the point is in the poly.

I think there is a point in poly gunction in the code archives that I put there. But I know there is a function I put there which tells you which side of a line you are on. The code is B3D code, but it is easy enough for you to port.

Actually, going back over it again, the method you describe sounds pretty similar to this method. But you test the dot product of the point and the line's normal, not the vertices. A distance check might speed things up a little, but if you're talking an interface then it is totally uneccessary to optimize it. There's no way you'd test even 1/100000th of the number of polygons you would need to for it to matter.

Here's my InsidePoly routine.

Here is mine, the vertexes are already transformed, X & Y are the screen position of the poly.

Method PointInside(x#,y#)
			Local i, j
			Local bInPoly = 0
			Local xt1#,xt2#,yt1#,yt2#
			j = Self.Col_VertexCount - 1 
			For i = 0 To Self.Col_VertexCount - 1 
				xt1 = Self.ColVertex[j].fx + self.x
				xt2 = Self.ColVertex[i].fx + self.x
				yt1 = Self.ColVertex[j].fy + self.y
				yt2 = Self.ColVertex[i].fx + Self.y
				If x < ( (xt1 - xt2) * (y - yt2) / (yt1 - yt2) + xt2 ) And ((yt2 <= y And y < yt1) Or (yt1 <= y And y < yt2)) Then  bInPoly = 1 - bInPoly
				j = i
			Next
			Return bInPoly
		End Method

Thanks guys, it looks like I was on the right track, but not quite there. I'll try them out and see which is the best fit, and it's good to know that speed won't be an issue for an interface.

I use a bounding box test first, and if it's in that I run another test based on the following :
http://www.geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
which looks like the same method that Indiepath posted.

Don't know if it's faster, but here's my PointInPoly function.

Below is my implementation of the Winding Number method. I ripped this out of my SA_GameMod libraries, so it used to be a method of my one of my GameMod types and it requires a simple struct-style "Point" which I will also post below.

  ' Function arguments: 
  ' _x = Mouse X position
  ' _y = Mouse Y position
  ' Points = An array of SA_GameObject_Point objects
  ' Returns:
  ' 0 if point _x, _y is outside polygon
  ' 1 if point _x, _y is inside polygon
  Function IsIn%(_x#, _y#, Points:SA_GameObject_Point[])
    Local xs% = 0

    For Local i% = 0 To Points.Length-2
    	If (( (Points[i].y <= _y) And (Points[i+1].y > _y) ) Or ( (Points[i].y > _y) And (Points[i+1].y <= _y) ))
    		Local sect# = Float((_y - Points[i].y) / (Points[i+1].y - Points[i].y))
    		If (_x < Points[i].x + sect*(Points[i+1].x - Points[i].x)) xs :+ 1
    	End If
    Next
    Return xs&1
  End Method

The Point type:

' ========================================
' SA_GameObject_Point - A "point" on the
' drawing surface or board defined by X, Y.
' Mainly used to define polygons.
' ========================================

Type SA_GameObject_Point
	Field x#, y#
	
       ' Creates and returns an SA_GameObject_Point
       ' of _x, _y
	Function Create:SA_GameObject_Point(_x#, _y#)
	  Local p:SA_GameObject_Point = new SA_GameObject_Point
		p.x = _x
		p.y = _y
		Return p
	End Function
End Type

Like I said, I ripped this from my SA_GameMod files and made a few quick edits to make it stand-alone but I haven't tested it as stand-alone. It works perfectly in my game mod, though.

SpaceAce