point_in_polygon

This code has been declared by its author to be Public Domain code.

point_in_polygon by big10p

2007

Here's a simple demo of point_in_polygon() - a pretty fast, compact function I converted from a C function I found on the web.

Graphics 800,600,0,2
SetBuffer BackBuffer()

SeedRnd MilliSecs()

Const POLY_VERTS = 100

; Create banks to hold polygon's vertex X/Y coords.
bank_x = CreateBank(POLY_VERTS * 4)
bank_y = CreateBank(POLY_VERTS * 4)

; Create a random, convex polygon.
da# = 360.0 / POLY_VERTS
ang# = 0.0

For i = 0 To (BankSize(bank_x) - 1) Step 4
	dist# = Rnd(50,300)
	PokeFloat bank_x, i, (GraphicsWidth() / 2) + (Cos(ang) * dist)
	PokeFloat bank_y, i, (GraphicsHeight() / 2) + (Sin(ang) * dist)
	ang = ang + da
Next
	
; Main loop.
While Not KeyHit(1)

	Cls
		
	inside = point_in_polygon(MouseX(), MouseY(), bank_x, bank_y)
		
	If inside
		Color 255,0,0
		status$ = "INSIDE"
	Else
		Color 255,255,255
		status$ = "OUTSIDE"
	EndIf
		
	draw_polygon(bank_x, bank_y)
		
	Color 255,255,0
	Text 10,10,"Mouse is " + status$ + " polygon!"
		
	Flip 1

Wend

End


;
; Determines whether a point lies inside a convex polygon.
;
; Params:
; x,y    - Coords of point to check.
; vert_x - Float bank holding polygon vertex X coords.
; vert_y - Float bank holding polygon vertex Y coords.
;
; Returns:
; True if the point is inside the polygon, False otherwise.
;
Function point_in_polygon(x#, y#, vert_x, vert_y)

	in = False
	
	last_byte = BankSize(vert_x) - 1

	For i = 0 To last_byte Step 4
	
		If i Then j = (i - 4) Else j = (last_byte - 3)
		
		x1# = PeekFloat(vert_x,i)
		y1# = PeekFloat(vert_y,i)

		x2# = PeekFloat(vert_x,j)
		y2# = PeekFloat(vert_y,j)

		If ((((y1 <= y) And (y < y2)) Or ((y2 <= y) And (y < y1))) And (x < (((x2 - x1) * (y - y1)) / (y2 - y1)) + x1))
			in = Not in
		EndIf

	Next

	Return in
	
End Function


;
; Draws a polygon.
;
; Params:
; vert_x - Float bank holding polygon vertex X coords.
; vert_y - Float bank holding polygon vertex Y coords.
;
Function draw_polygon(vert_x, vert_y)

	last_byte = BankSize(vert_x) - 1

	For i = 0 To last_byte Step 4
	
		If i Then j = (i - 4) Else j = (last_byte - 3)
		
		x1# = PeekFloat(vert_x,i)
		y1# = PeekFloat(vert_y,i)

		x2# = PeekFloat(vert_x,j)
		y2# = PeekFloat(vert_y,j)

		Line x1, y1, x2, y2

	Next

End Function

Comments

Chroma

2011

This is ace. I'm currently using this with verlet and it's works great. Very fast too.

big10p

2011

Glad you found it useful. :)

JBR

2011

I've converted it to arrays for a bit more speed.(37ms vs 57ms). Only downside is arrays are not passed to functions

Graphics 800,600,0,2
SetBuffer BackBuffer()

SeedRnd MilliSecs()

Const POLY_VERTS = 100

; Create arrays to hold polygon's vertex X/Y coords.

Dim A_x#( POLY_VERTS )
Dim A_y#( POLY_VERTS )


; Create a random, convex polygon.
da# = 360.0 / POLY_VERTS
ang# = 0.0

For i = 0 To  POLY_VERTS-1
	dist# = Rnd(50,300)
	A_x#( i ) = (GraphicsWidth() / 2) + (Cos(ang) * dist)
	A_y#( i ) = (GraphicsHeight() / 2) + (Sin(ang) * dist)
	ang = ang + da
Next

A_x# ( POLY_VERTS ) = A_x#(0)		; easy wrapping
A_y# ( POLY_VERTS ) = A_y#(0)
	
; Main loop.
While Not KeyHit(1)

	Cls
	
	x# = MouseX()
	y# = MouseY()
	time=MilliSecs()
	
	For i=1 To 10000
		
		inside = point_in_polygon(x#, y#)
		
	Next
	Text 0,0,MilliSecs()-time
		
	If inside
		Color 255,0,0
		status$ = "INSIDE"
	Else
		Color 255,255,255
		status$ = "OUTSIDE"
	EndIf
		
	draw_polygon()
		
	Color 255,255,0
	Text 10,10,"Mouse is " + status$ + " polygon!"
		
	Flip 1

Wend

End


;
; Determines whether a point lies inside a convex polygon.
;
; Params:
; x,y    - Coords of point to check.
;
; Returns:
; True if the point is inside the polygon, False otherwise.
;
Function point_in_polygon(x#, y#)

	in = False
	
	For i = 0 To POLY_VERTS-1
	
		x1# = A_x#(i)
		y1# = A_y#(i)

		x2# = A_x#(i+1)
		y2# = A_y#(i+1)

		If ((((y1 <= y) And (y < y2)) Or ((y2 <= y) And (y < y1))) And (x < (((x2 - x1) * (y - y1)) / (y2 - y1)) + x1))
			in = Not in
		EndIf

	Next

	Return in
	
End Function


;
; Draws a polygon.
Function draw_polygon()

	For i = 0 To POLY_VERTS-1
	
		x1# = A_x#(i)
		y1# = A_y#(i)

		x2# = A_x#(i+1)
		y2# = A_y#(i+1)

		Line x1, y1, x2, y2

	Next

End Function

Charrua

2011

hi

"Only downside is arrays are not passed to functions"

use Blitz arrays, only restriction is that must be unidimensional

Local A#[10], i

For i=0 To 10
 A[i]=0.1*i
 DebugLog a[i]
Next

ClearArray(a)

For i=0 To 10
 DebugLog a[i]
Next

WaitKey

End

Function ClearArray(array#[10])
	Local i
	For i=0 To 10
		array[i]=0
	Next
End Function

Juan

Bobysait

2015

Here is the most optimised version I get at the moment

(50-75% faster than JBR's code)

Const POLY_VERTS% = 100; max vertices allowed
			; this is just an arbitrary value.
			; you can adjust it to fit your needs.

Type TPoly
	Field p#[POLY_VERTS*2]; vertices coordinates (x,y)
	Field n; vertices count
	Field x0#, y0#, x1#, y1#; polygon bounds
End Type


Function newPoly.TPoly()
	Return New TPoly;
End Function

Function polyAdd(p.TPoly, x#,y#)
	; prevent from <out of range> error
	If p\n>=POLY_VERTS Then Return False;
	
	; coordinates of the new point
	p\p[p\n*2+0]=x;
	p\p[p\n*2+1]=y;
	
	; initialize bounds with first point
	If p\n=0
		p\x0 = x
		p\y0 = y
		p\x1 = x
		p\y1 = y
	Else
		; update bounds
		If x<p\x0 Then p\x0=x;
		If y<p\y0 Then p\y0=y;
		If x>p\x1 Then p\x1=x;
		If y>p\y1 Then p\y1=y;
	EndIf
	; increase vertices count.
	p\n=p\n+1;
End Function



Function point_in_polygon(poly.TPoly, x#, y#)
	
	; not enough points to make a single triangle
	If poly\n<3 Then Return;
	
	; outside polygon boundaries
	If x<poly\x0 Then Return False;
	If y<poly\y0 Then Return False;
	If x>poly\x1 Then Return False;
	If y>poly\y1 Then Return False;
	
	; first point is the last (to close the shape)
	Local x2# = poly\p[poly\n*2-2];
	Local y2# = poly\p[poly\n*2-1];
	
	Local x1#,y1#
	
	Local in% = False
	Local i%
	
	For i = 0 To poly\n-1
		
		x1=poly\p[i*2+0];
		y1=poly\p[i*2+1];
		
		; separate x and y tests to reduice time processing
		If (y1<=y)
			If (y<y2)
				If (x < x1 + (((x2 - x1) * (y - y1)) / (y2 - y1)))
					in = Not in
				EndIf;
			EndIf;
		Else
			If (y2<=y)
				If (x < x1 + (((x2 - x1) * (y - y1)) / (y2 - y1)))
					in = Not in
				EndIf;
			EndIf;
		EndIf;
		
		x2=x1;
		y2=y1;
		
	Next;
	
	Return in
	
End Function


Function draw_polygon(poly.TPoly)
	
	If poly\n<3 Then Return;
	
	Local x1#,y1#
	Local x2# = poly\p[poly\n*2-2];
	Local y2# = poly\p[poly\n*2-1];
	
	Local i%
	For i = 0 To poly\n-1
		
		x1=poly\p[i*2+0];
		y1=poly\p[i*2+1];
		
		Line x1, y1, x2, y2;
		
		x2 = x1;
		y2 = y1;
		
	Next;
	
End Function












Graphics	( 800,600,0,2 );
SetBuffer	( BackBuffer() );

SeedRnd		( MilliSecs() );

; Create a polygon container
Local poly.TPoly = newPoly();

; add random points
Local da# = 360.0 / POLY_VERTS;
Local ang# = 0.0;

Local i%
For i = 0 To  POLY_VERTS-1
	Local dist# = Rnd(50,300);
	polyAdd ( poly, GraphicsWidth()*.5 + dist*Cos(ang), GraphicsHeight()*.5 + dist*Sin(ang) );
	ang = ang + da;
Next;

; process the full screen and export the result to an image
Local img = CreateImage(GraphicsWidth(), GraphicsHeight());
	SetBuffer ImageBuffer(img);
		LockBuffer();
			Local t0 = MilliSecs();
			Local iw = ImageWidth(img)-1;
			Local ih = ImageHeight(img)-1;
			Local ix%, iy%;
			For iy = 0 To ih
			For ix = 0 To iw
				If point_in_polygon(poly, ix, iy)
					WritePixelFast(ix, iy, $FFFF8000);
				Else
					WritePixelFast(ix, iy, $FF202080);
				EndIf;
			Next;
			Next;
			Local imgTime = MilliSecs() - t0;
		UnlockBuffer();
	SetBuffer BackBuffer();
	

; Main loop.
Local status$

While Not KeyHit(1)

	Cls
	
	Local x# = MouseX()
	Local y# = MouseY()
	
	Local time=MilliSecs()
	For i=1 To 10000
		point_in_polygon(poly, x, y)
	Next
	Local testTime% = MilliSecs()-time;
	
	If point_in_polygon(poly, x, y)
		Color 255,0,0
		status$ = "INSIDE"
	Else
		Color 255,255,255
		status$ = "OUTSIDE"
	EndIf
	
	DrawImage img, 0,0
	
	draw_polygon(poly)
		
	Color ( 255,255,0 );
	Text ( 10,10, "Mouse is " + status$ + " polygon!" );
	Text ( 10,25, "test time : "+testTime+".ms" );
	Text ( 10,40, "full image processed in "+imgTime+".ms" );
	Flip ( True );

Wend;

End;

Flanker

2016

Thanks guys for the code. Bobysait's version is lightning fast !

Bobysait

2016

I didn't remember this code ...
Good to add to my library, here is a blitzmax conversion
(so much faster than blitz3d version -> like 2 or 3 times faster)

Framework brl.glmax2d
Import brl.random

Graphics 800,600,0,0

Type TPoly
	
	Field p#[], x0#, y0#, x1#, y1#;
	
	Method add(x#, y#)
		If p.length
			x0 = min(x0,x); y0 = min(y0,y); x1 = max(x1,x); y1 = max(y1,y);
		Else
			x0 = x; y0 = y; x1 = x; y1 = y;
		EndIf;
		p :+ [x,y];
	End Method
	
	Method pointIn@(x#, y#)
		
		' less than 3 points -> no triangle to test
		Local n% = p.length;
		If n<6 Then Return False;
		
		' point outside polygon boundaries
		If x<x0 Then Return False;
		If y<y0 Then Return False;
		If x>x1 Then Return False;
		If y>y1 Then Return False;
		
		' First POINT is the Last (To Close the shape)
		Local lx2# = p[n-2], ly2# = p[n-1], lx1#, ly1#;
		Local in@ = 0, i%;
		
		For i = 0 Until n Step 2
			lx1=p[i+0]; ly1=p[i+1];
			If (ly1<=y)
				If (y<ly2) Then If (x < lx1+(((lx2-lx1)*(y-ly1))/(ly2-ly1))) Then in = Not(in);
			Else
				If (ly2<=y) Then If (x < lx1 + (((lx2-lx1)*(y-ly1))/(ly2-ly1))) Then in = Not(in);
			EndIf;
			lx2=lx1; ly2=ly1;
		Next;
		
		Return in
		
	End Method
	
	Method Draw()
		Local n%= p.length; If n<6 Then Return;
		Local lx2#=p[n-2], ly2#=p[n-1], lx1#, ly1#, i%;
		For i = 0 Until n Step 2
			lx1=p[i+0]; ly1=p[i+1];
			DrawLine lx1, ly1, lx2, ly2;
			lx2 = lx1; ly2 = ly1;
		Next;
	End Method
	
End Type










Graphics	( 800,600,0,2 );
SeedRnd		( MilliSecs() );

Local nVerts% = 100;

' Create a polygon container
Local poly:TPoly = New TPoly;

' add random points
Local da# = 360.0 / nVerts;
Local ang# = 0.0;

Local i%;
For i = 0 Until nVerts
	Local dist# = Rnd(50,300);
	poly.add ( GraphicsWidth()*.5 + dist*Cos(ang), GraphicsHeight()*.5 + dist*Sin(ang) );
	ang :+ da;
Next;

' process the full screen and export the result to an image
Local img:TPixmap = CreatePixmap(GraphicsWidth(), GraphicsHeight(), PF_RGBA8888);
	Local t0% = MilliSecs();
	Local iw% = img.width;
	Local ih% = img.Height;
	Local ix%, iy%;
	For iy = 0 Until ih
		Local t@ ptr = img.PixelPtr(0,iy);
		For ix = 0 Until iw
			If poly.pointin(ix, iy)
				t[0]=$FF; t[1]=$80; t[2]=$00
			Else
				t[0]=$20; t[1]=$20; t[2]=$80
			EndIf;
			t[3]=$FF;
			t:+4;
		Next;
	Next;
	Local imgTime% = MilliSecs() - t0;
	
' Main loop.
Local Status$=""

While Not KeyHit(KEY_ESCAPE)

	Cls
	
	Local x# = MouseX(), y# = MouseY()
	
	Local time=MilliSecs()
	For i=1 To 10000
		poly.pointin(x, y)
	Next
	Local testTime% = MilliSecs()-time;
	
	If poly.pointin( x, y)
		SetColor 255,0,0
		Status = "INSIDE"
	Else
		SetColor 255,255,255
		Status = "OUTSIDE"
	EndIf
	
	DrawPixmap img, 0,0
	
	poly.Draw();
	
	SetColor ( 255,255,0 );
	DrawText ( "Mouse is " + Status$ + " polygon!", 10,10 );
	DrawText ( "test time : "+testTime+".ms", 10,25 );
	DrawText ( "full image processed in "+imgTime+".ms", 10,40 );
	Flip ( True );

Wend;

End;

BlitzSupport

2016

Wow, that's amazing, Bobysait -- your version has gone from ~14ms down to ~2ms -- the .bb version could easily take up most of a frame, but the .bmx version is way faster than "2 or 3 times" here!

Bobysait

2016

Glad you like it, just take care that the speed is not due to you test outside of the bounding box, there is two tests instead of one :
- the first step is a simple bounding rect test, very fast while it removes lots of potential useless tests, it also does not show the worst cases.
So if you tested with cursor out of the bounding rect, you only get the first step.

But yeah, even in worst case, it's still really faster (and that's due to blitzmax essentially, the code has not really been improved, it's just a bit more OOP)

And BTW, this is a small improvment for the b3d version (around 30-40% faster if you use Float array, 100% if you use Int array)

Const POLY_VERTS% = 100; max vertices allowed
			; this is just an arbitrary value.
			; you can adjust it to fit your needs.

Const POLY_LENGTH% = 5+POLY_VERTS*2

Type TPoly
	Field p%[POLY_LENGTH]; vertices coordinates (x,y)
End Type


Function newPoly.TPoly()
	Return New TPoly;
End Function

Function polyAdd(p.TPoly, x%,y%)
	; prevent from <out of range> error
	If p\p[4]>=POLY_VERTS Then Return False;
	
	Local n% = p\p[4];
	; coordinates of the new point
	p\p[5+n*2+0]=x;
	p\p[5+n*2+1]=y;
	
	; initialize bounds with first point
	If n=0
		p\p[0] = x
		p\p[1] = y
		p\p[2] = x
		p\p[3] = y
	Else
		; update bounds
		If x<p\p[0] Then p\p[0]=x;
		If y<p\p[1] Then p\p[1]=y;
		If x>p\p[2] Then p\p[2]=x;
		If y>p\p[3] Then p\p[3]=y;
	EndIf
	; increase vertices count.
	p\p[4]=p\p[4]+1
End Function

Function point_in_polygon_array(p%[POLY_LENGTH],x,y)
	
	; not enough points to make a single triangle
	Local n% = p[4] : If n<3 Then Return;
	
	; outside polygon boundaries
	If x<p[0] Then Return False;
	If y<p[1] Then Return False;
	If x>p[2] Then Return False;
	If y>p[3] Then Return False;
	
	; first point is the last (to close the shape)
	Local x2% = p[5+n*2-2], y2% = p[5+n*2-1], x1%, y1%, in% = False, i%
	
	For i = 0 To n-1
		
		x1=p[5+i*2+0];
		y1=p[5+i*2+1];
		
		; separate x and y tests to reduice time processing
		If (y1<=y)
			If (y<y2)
				If (x < x1 + (((x2 - x1) * (y - y1)) / (y2 - y1)))
					in = Not in
				EndIf;
			EndIf;
		Else
			If (y2<=y)
				If (x < x1 + (((x2 - x1) * (y - y1)) / (y2 - y1)))
					in = Not in
				EndIf;
			EndIf;
		EndIf;
		
		x2=x1;
		y2=y1;
		
	Next;
	
	Return in
	
End Function

Function point_in_polygon(poly.TPoly, x%, y%)
	Return point_in_polygon_array(poly\p, x,y)
End Function


Function draw_polygon_array(p%[POLY_LENGTH])
	Local n% = p[4] : If n<3 Then Return;
	Local x1%,y1%, x2% = p[5+n*2-2], y2% = p[5+n*2-1], i%
	For i = 0 To n-1
		x1=p[5+i*2+0];
		y1=p[5+i*2+1];
		Line x1, y1, x2, y2;
		x2 = x1;
		y2 = y1;
	Next;
End Function

Function draw_polygon(poly.TPoly)
	draw_polygon_array poly\p
End Function












Graphics	( 800,600,0,2 );
SetBuffer	( BackBuffer() );

SeedRnd		( MilliSecs() );

; Create a polygon container
Local poly.TPoly = newPoly();

; add random points
Local da# = 360.0 / POLY_VERTS;
Local ang# = 0.0;

Local i%
For i = 0 To  POLY_VERTS-1
	Local dist# = Rnd(50,300);
	polyAdd ( poly, GraphicsWidth()*.5 + dist*Cos(ang), GraphicsHeight()*.5 + dist*Sin(ang) );
	ang = ang + da;
Next;

; process the full screen and export the result to an image
Local img = CreateImage(GraphicsWidth(), GraphicsHeight());
	SetBuffer ImageBuffer(img);
		LockBuffer();
			Local t0 = MilliSecs();
			Local iw = ImageWidth(img)-1;
			Local ih = ImageHeight(img)-1;
			Local ix%, iy%;
			For iy = 0 To ih
			For ix = 0 To iw
				If point_in_polygon(poly, ix, iy)
					WritePixelFast(ix, iy, $FFFF8000);
				Else
					WritePixelFast(ix, iy, $FF202080);
				EndIf;
			Next;
			Next;
			Local imgTime = MilliSecs() - t0;
		UnlockBuffer();
	SetBuffer BackBuffer();
	

; Main loop.
Local status$

While Not KeyHit(1)

	Cls
	
	Local x% = MouseX()
	Local y% = MouseY()
	
	Local time=MilliSecs()
	For i=1 To 10000
		point_in_polygon(poly, x, y)
	Next
	Local testTime% = MilliSecs()-time;
	
	If point_in_polygon(poly, x, y)
		Color 255,0,0
		status$ = "INSIDE"
	Else
		Color 255,255,255
		status$ = "OUTSIDE"
	EndIf
	
	DrawImage img, 0,0
	
	draw_polygon(poly)
		
	Color ( 255,255,0 );
	Text ( 10,10, "Mouse is " + status$ + " polygon!" );
	Text ( 10,25, "test time : "+testTime+".ms" );
	Text ( 10,40, "full image processed in "+imgTime+".ms" );
	Flip ( True );

Wend;

End;

using Int instead of float reduice by 2 the time compute the tests and using a static array to store polygon data (box and vertex count) is faster than using "Fields".
> convert the "%" to "#" to use floats instead of Ints, it will still work faster.

and here is a small improvment for the blitzmax version

Framework brl.glmax2d
Import brl.random

Graphics 800,600,0,0

Type TPoly
	
	Field p#[], x0#, y0#, x1#, y1#;
	
	Method add(x#, y#)
		If p.length
			x0 = min(x0,x); y0 = min(y0,y); x1 = max(x1,x); y1 = max(y1,y);
		Else
			x0 = x; y0 = y; x1 = x; y1 = y;
		EndIf;
		p :+ [x,y];
	End Method
	
	Method pointIn@(x#, y#)
		
		' less than 3 points -> no triangle to test
		Local n% = p.length;
		If n<6 Then Return False;
		
		' point outside polygon boundaries
		If x<x0 Then Return False;
		If y<y0 Then Return False;
		If x>x1 Then Return False;
		If y>y1 Then Return False;
		
		' First POINT is the Last (To Close the shape)
		Local pt# ptr = p;
		Local lx2# = p[n-2], ly2# = p[n-1], lx1#, ly1#;
		Local in@ = 0, i%;
		
		For i = 0 Until n Step 2
			lx1=pt[0]; ly1=pt[1];
			If (ly1<=y)
				If (y<ly2) Then If (x < lx1+(((lx2-lx1)*(y-ly1))/(ly2-ly1))) Then in = Not(in);
			Else
				If (ly2<=y) Then If (x < lx1 + (((lx2-lx1)*(y-ly1))/(ly2-ly1))) Then in = Not(in);
			EndIf;
			lx2=lx1; ly2=ly1;
			pt:+2
		Next;
		
		Return in
		
	End Method
	
	Method Draw()
		Local n%= p.length; If n<6 Then Return;
		Local lx2#=p[n-2], ly2#=p[n-1], lx1#, ly1#, i%;
		For i = 0 Until n Step 2
			lx1=p[i+0]; ly1=p[i+1];
			DrawLine lx1, ly1, lx2, ly2;
			lx2 = lx1; ly2 = ly1;
		Next;
	End Method
	
End Type










Graphics	( 800,600,0,2 );
SeedRnd		( MilliSecs() );

Local nVerts% = 100;

' Create a polygon container
Local poly:TPoly = New TPoly;

' add random points
Local da# = 360.0 / nVerts;
Local ang# = 0.0;

Local i%;
For i = 0 Until nVerts
	Local dist# = Rnd(50,300);
	poly.add ( GraphicsWidth()*.5 + dist*Cos(ang), GraphicsHeight()*.5 + dist*Sin(ang) );
	ang :+ da;
Next;

' process the full screen and export the result to an image
Local img:TPixmap = CreatePixmap(GraphicsWidth(), GraphicsHeight(), PF_RGBA8888);
	Local t0% = MilliSecs();
	Local iw% = img.width;
	Local ih% = img.Height;
	Local ix%, iy%;
	For iy = 0 Until ih
		Local t@ ptr = img.PixelPtr(0,iy);
		For ix = 0 Until iw
			If poly.pointin(ix, iy)
				t[0]=$FF; t[1]=$80; t[2]=$00
			Else
				t[0]=$20; t[1]=$20; t[2]=$80
			EndIf;
			t[3]=$FF;
			t:+4;
		Next;
	Next;
	Local imgTime% = MilliSecs() - t0;
	
' Main loop.
Local Status$=""

While Not KeyHit(KEY_ESCAPE)

	Cls
	
	Local x# = MouseX(), y# = MouseY()
	
	Local time=MilliSecs()
	For i=1 To 10000
		poly.pointin(x, y)
	Next
	Local testTime% = MilliSecs()-time;
	
	If poly.pointin( x, y)
		SetColor 255,0,0
		Status = "INSIDE"
	Else
		SetColor 255,255,255
		Status = "OUTSIDE"
	EndIf
	
	DrawPixmap img, 0,0
	
	poly.Draw();
	
	SetColor ( 255,255,0 );
	DrawText ( "Mouse is " + Status$ + " polygon!", 10,10 );
	DrawText ( "10000 tests time : "+testTime+".ms", 10,25 );
	DrawText ( "full image processed in "+imgTime+".ms", 10,40 );
	Flip ( True );

Wend;

End;

It uses a float ptr to traverse the points in the test.

Flanker

2016

I noticed that the routine will return false if we are actually on one edge. It can be fixed if necessary by using <= and >= in the point_in_polygon() function checks. I presume it uses the crossing method with odd and even numbers replaced by "in = Not in".

Code Archives Forum