collision and found a bug in PointInPoly ?

Monkey Forums/Monkey Programming/collision and found a bug in PointInPoly ?

GC-Martijn

(Posted 2015) [#1]

As you probably already know, i'm busy with the png tracer bla bla.
AND I solved IT a few days ago ! :)

I'm testing it very good before i'm posting it.
And yesterday I was testing the next step collision checks.
And what happend was this:

The method PointInPoly is a second collision option, not what I want for the main goal, but I can use that later.
But it does not do what it says, or the Mouse coordinates are wrong ?

When I touch a line from the left, it says its inside the verts[] (that wrong)
When I touch a line from the right, it says its not inside the vers[] (that good)
When the mouse is inside the verts[] is oke !

But behind that method I was searching for this function:
If PointHitTheLineOrIsInsidePoly(MouseX(),MouseY(),verts) Then

If PointInPoly(MouseX(),MouseY(),verts) Then
			hit = True
		Else
			hit = False
		End

'' Found this at monkey forums, at several places
Function PointInPoly:Bool(x:Float, y:Float, poly:Float[])
		Local i:Int, j:Int, c:Bool
		Local v1:Bool, v2:Bool, v3:Bool, v4:Bool, v5#, v6#, v7#
		c = False
		Local p_count% = (poly.Length() / 2)
		
		For i = 0 To p_count-1
			j = (i+1) Mod p_count
			v1 = (poly[i*2+1] <= y)
			v2 = (y < poly[j*2+1])
			v3 = (poly[j*2+1] <= y)
			v4 = (y < poly[i*2+1])
			v5 = (poly[j*2]-poly[i*2]) * (y-poly[i*2+1])
			v6 = (poly[j*2+1]-poly[i*2+1])
			If v6 = 0.0 Then v6 = 0.0001
			v7 = poly[i*2]
			If (((v1 And v2) Or (v3 And v4)) And (x < v5 / v6 + v7)) Then c = Not c
		Next
		Return c
	End

I can create lines from the points like this either.

	Function distanceToPoly:Bool(p:Point,points:Stack<Point>)
		'For Local point:Point = Eachin points
		For Local i:Int = 0 Until points.Length()-1

			Print distToSegment(p,points.Get(i),points.Get(i+1))
		
			If distToSegment(p,points.Get(i),points.Get(i+1))<=0 Then
				Return True
			End

		Next
		Return False
	End
Function distance:Float(x1:Int, y1:Int, x2:Int, y2:Int) 
Local x:Float=Sqrt(((x1 - x2)*(x1 - x2)) + ((y1 - y2)*(y1 - y2)) )
Return x
End Function

Function sqr:Float(x:Float) 
	Return (x * x) 
End
Function dist2:Float(v:Point, w:Point) 
	Return sqr(v.x - w.x) + sqr(v.y - w.y) 
End
	' p = point to check
	' v = start point line
	' w = end point line
Function distToSegmentSquared:Float(p:Point, v:Point, w:Point) 
  Local l2:Float = dist2(v, w)
  If (l2 = 0) Then 
  	Return dist2(p, v) 
  End
  Local t:Float = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2
  If (t < 0) Then 
  	Return dist2(p, v)
  	End
  If (t > 1) Then 
  	Return dist2(p, w) 
  End
  Return dist2(p, New Point(v.x + t * (w.x - v.x),v.y + t * (w.y - v.y) ))
End
Function distToSegment:Float(p:Point, v:Point, w:Point) 
	Return Sqrt(distToSegmentSquared(p, v, w)) 
End

edit: the blue line is a visual line, i'm checking against only the corner points that are inside the blue line.
In this example there are 12 points that creating this figure.
There are in counter / anti clockwise order

Difference

(Posted 2015) [#2]

If you need a good PointInPoly, that works with concave polygons, you can use this:

Function IsInsidePoly:Int(polypoints:Float[],x:Float,y:Float) 

	Local  j:Int = polypoints.Length()-2
  	Local oddNodes:Int

	For Local i:Int =0 Until polypoints.Length() Step 2	
		If (polypoints[i+1]< y And polypoints[j+1]>=y )   Or   (polypoints[j+1]< y And polypoints[i+1]>=y) 
			If  (polypoints[i]<=x Or polypoints[j]<=x) 
				If (polypoints[i]+(y-polypoints[i+1])/(polypoints[j+1]-polypoints[i+1])*(polypoints[j]-polypoints[i])<x) 
					oddNodes = 1 ~ oddNodes 
				Endif
			Endif
		Endif
		j=i 
	Next

  Return oddNodes

End Function

GC-Martijn

(Posted 2015) [#3]

Thanks, I will check this later today.
I always wondering how people can create methods like this haha.

Difference

(Posted 2015) [#4]

I think the one I posted originates form : http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

and http://paulbourke.net/geometry/polygonmesh/

GC-Martijn

(Posted 2015) [#5]

Your code is maybe working, but not now at the moment I think that there is something else that I have to check first.
Because several other similar algorithms din't work either.
So i'm going to take one step back and going to create a simple convex box, and hide the default cursor and use one pixel point as the cursor.

That way I can exactly see in osx what the program does.

And in the final game I want to hide the default cursor as well and make a custom one for the desktop target.

I found this on the internet, but don't know how to get the variable window in osx at the moment.
glfwSetInputMode(window, GLFW_CURSOR, GLFW_CURSOR_HIDDEN);

game programming is like solving one big puzzle haha

ImmutableOctet(SKNG)

(Posted 2015) [#6]

@GC-Martijn: A bit off topic, but use 'HideMouse'. If you want to do it directly, you could use 'SetMouseVisible' (Use "BBGame.Game()"). This is effectively the exact same thing as doing it natively.

Finally, if you want to do it directly using GLFW3, you can use 'glfwSetInputMode' like this:

glfwSetInputMode(BBGlfwGame::GlfwGame()->GetGLFWwindow(), GLFW_CURSOR, GLFW_CURSOR_HIDDEN);

I recommend doing it using Mojo or the standard BBGame functionality, though.

GC-Martijn

(Posted 2015) [#7]

Thanks for the info, what I do is checking this page http://www.monkey-x.com/docs/html/Index.html using some keywords.
Yesterday my keywords where: cursor & pointer haha
HideMouse() is the thing I need ;)

EDIT:
@Difference
The funny thing is that your code does the opposite what is oke, because I can use both methods to check if there is a collision.

I have to rename them, and make one whole function from it, but its working ;)

If PointInPoly(MouseX(),MouseY(),verts) Or IsInsidePoly(verts,MouseX(),MouseY())  Then
			hit = True
		Else
			hit = False
		End

Difference

(Posted 2015) [#8]

@Difference
The funny thing is that your code does the opposite what is oke, because I can use both methods to check if there is a collision.

I made a test program for you below. IsInsidePoly() is behaving as it should.

Strict
Import mojo

Class MyApp Extends App

	 Field poly1:Float[10]
	 Field poly2:Float[10]
	 Field inside:int
	 
	Method OnCreate:Int()
		 
		 poly1[0] = 30
		 poly1[1] = 30
		
		 poly1[2] = 430
		 poly1[3] = 130

		 poly1[4] = 530
		 poly1[5] = 430	
		 
		 poly1[6] = 230
		 poly1[7] = 130			 
	
		 poly1[8] = 60
		 poly1[9] = 400		
		 
		 
		 ' make a smaller reverse wound poly: 
		 Local n2:Int = poly1.Length - 2
		 
		 For Local n:Int = 0 Until poly1.Length Step 2
	 		poly2[n] = poly1[n2]   * 0.5 
	 		poly2[n+1] = poly1[n2+1]  * 0.5 
	 		n2 -=2
	 	Next n
		 
		
		Return 0
	End
	
	
	Method OnRender:Int()
	
		Cls 0,0,0
	
		' draw and check poly 1
	 	If IsInsidePoly(poly1,TouchX(0),TouchY(0))
	 		SetColor 255,255,0
	 	Else
	 		SetColor 0,0,255
	 	Endif
	 	
	 	Local n2:Int = poly1.Length - 2
	 
	 	For Local n:Int = 0 Until poly1.Length Step 2
	 		DrawLine poly1[n2],poly1[n2+1],poly1[n],poly1[n+1]
	 		n2 = n
	 	Next n
	 
	 	' draw and check poly 2
	 	If IsInsidePoly(poly2,TouchX(0),TouchY(0))
	 		SetColor 255,255,0
	 	Else
	 		SetColor 0,0,255
	 	Endif
	 	
	 	 n2 = poly2.Length - 2
	 
	 	For Local n:Int = 0 Until poly2.Length Step 2
	 		DrawLine poly2[n2],poly2[n2+1],poly2[n],poly2[n+1]
	 		n2 = n
	 	Next n
	 
		Return 0
	End
End

 


Function Main:Int()
	New MyApp
	Return 0
End


Function IsInsidePoly:Int(polypoints:Float[],x:Float,y:Float) 

	Local  j:Int = polypoints.Length()-2
  	Local oddNodes:Int

	For Local i:Int =0 Until polypoints.Length() Step 2	
		If (polypoints[i+1]< y And polypoints[j+1]>=y )   Or   (polypoints[j+1]< y And polypoints[i+1]>=y) 
			If  (polypoints[i]<=x Or polypoints[j]<=x) 
				If (polypoints[i]+(y-polypoints[i+1])/(polypoints[j+1]-polypoints[i+1])*(polypoints[j]-polypoints[i])<x) 
					oddNodes = 1 ~ oddNodes 
				Endif
			Endif
		Endif
		j=i 
	Next

  Return oddNodes

End Function

GC-Martijn

(Posted 2015) [#9]

@Differcence

Nope, I tested the code again and its not working correct, but I made a fix.
First hide the cursor and draw a dot, was helping me in osx because the cursor shadow din't show exactly where my mouse was.
Then check all the lines , including the bottom corners (left and right)

using your code, some bottom corners din't work, and some lines.
check it with this code.

I don't know how to optimize my polycheck more at the moment, but its working.= :)

Strict
Import mojo

Function Main:Int()
	New MyApp
	Return 0
End

Class MyApp Extends App

	 Field poly1:Float[26]
	 Field inside:int
	 Field hit:Bool

	Method OnCreate:Int()
		 
		HideMouse()
poly1[0] = 22.0
poly1[1] = 130.0
poly1[2] = 31.0
poly1[3] = 130.0
poly1[4] = 31.0
poly1[5] = 45.0
poly1[6] = 210.0
poly1[7] = 45.0
poly1[8] = 210.0
poly1[9] = 130.0
poly1[10] = 219.0
poly1[11] = 130.0
poly1[12] = 219.0
poly1[13] = 45.0
poly1[14] = 240.0
poly1[15] = 45.0
poly1[16] = 240.0
poly1[17] = 1.0
poly1[18] = 1.0
poly1[19] = 1.0
poly1[20] = 1.0
poly1[21] = 45.0
poly1[22] = 22.0
poly1[23] = 45.0
poly1[24] = 22.0
poly1[25] = 129.0	
		 
		Return 0
	End
	
	
	Method OnRender:Int()
		Cls(255,255,255)

		If hit Then
			SetColor(255,0,0)
		Else	
			SetColor(0,0,255)
		End

	 	Local n2:Int = poly1.Length - 2
	 	For Local n:Int = 0 Until poly1.Length Step 2
	 		DrawLine poly1[n2],poly1[n2+1],poly1[n],poly1[n+1]
	 		n2 = n
	 	Next n
 
 		SetColor(0,0,255)
		DrawPoint(MouseX(),MouseY())
		Return 0
	End


	Method OnUpdate:Int()
		If KeyHit(KEY_SPACE) Then
			EndApp()
		End

	 	If PolyCollision(poly1,MouseX(),MouseY()) Then
	 		hit = True
		Else
			hit = False
		End
	 	Return 0
	End
End



' not working if the cursor is on the right side on the line
Function IsInsidePoly:Int(polypoints:Float[],x:Float,y:Float) 

	Local  j:Int = polypoints.Length()-2
  	Local oddNodes:Int

	For Local i:Int =0 Until polypoints.Length() Step 2	
		If (polypoints[i+1]< y And polypoints[j+1]>=y )   Or   (polypoints[j+1]< y And polypoints[i+1]>=y) 
			If  (polypoints[i]<=x Or polypoints[j]<=x) 
				If (polypoints[i]+(y-polypoints[i+1])/(polypoints[j+1]-polypoints[i+1])*(polypoints[j]-polypoints[i])<x) 
					oddNodes = 1 ~ oddNodes 
				Endif
			Endif
		Endif
		j=i 
	Next

  Return oddNodes

End Function


' 0 = no collision
' 1 = line collion
' 2 = point inside
Function PolyCollision:Int(polypoints:Float[],x:Float,y:Float)
	Local j:Int = polypoints.Length()-2
  	Local cn:Int = 0  
	Local cn2:Int = 0 

	For Local i:Int=0 Until polypoints.Length() Step 2
		If i<=polypoints.Length()-3 And (((polypoints[i+1] <= y) And (polypoints[i+3] > y)) Or
         ((polypoints[i+1] > y) And (polypoints[i+3] <=  y))) Then
            Local vt:Float = (y  - polypoints[i+1]) / (polypoints[i+3] - polypoints[i+1])
            If (x < polypoints[i] + vt * (polypoints[i+2] - polypoints[i])) Then
                cn = 1 ~ cn
            End 
        Elseif (polypoints[i+1]<y And polypoints[j+1]>=y) Or (polypoints[j+1]< y And polypoints[i+1]>=y) 
			If (polypoints[i]<=x Or polypoints[j]<=x) 
				If (polypoints[i]+(y-polypoints[i+1])/(polypoints[j+1]-polypoints[i+1])*(polypoints[j]-polypoints[i])<x) 
					cn2 = 1 ~ cn2
				Endif
			Endif
		End
		' corners at the bottem
		If polypoints[i]=x And polypoints[i+1]=y Then
			cn = 1 ~ cn
		End
		j=i
	Next
    Return (cn&1)+(cn2&1)  	
End Function