[bb] point_in_polygon by big10p [ 1+ years ago ]

[BlitzBot]

Title : point_in_polygon
Author : big10p
Posted : 1+ years ago

Description : 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.

Code :

Code: BlitzBasic

1. Graphics 800,600,0,2
2. SetBuffer BackBuffer()
3.  
4. SeedRnd MilliSecs()
5.  
6. Const POLY_VERTS = 100
7.  
8. ; Create banks to hold polygon's vertex X/Y coords.
9. bank_x = CreateBank(POLY_VERTS * 4)
10. bank_y = CreateBank(POLY_VERTS * 4)
11.  
12. ; Create a random, convex polygon.
13. da# = 360.0 / POLY_VERTS
14. ang# = 0.0
15.  
16. For i = 0 To (BankSize(bank_x) - 1) Step 4
17.         dist# = Rnd(50,300)
18.         PokeFloat bank_x, i, (GraphicsWidth() / 2) + (Cos(ang) * dist)
19.         PokeFloat bank_y, i, (GraphicsHeight() / 2) + (Sin(ang) * dist)
20.         ang = ang + da
21. Next
22.        
23. ; Main loop.
24. While Not KeyHit(1)
25.  
26.         Cls
27.                
28.         inside = point_in_polygon(MouseX(), MouseY(), bank_x, bank_y)
29.                
30.         If inside
31.                 Color 255,0,0
32.                 status$ = "INSIDE"
33.         Else
34.                 Color 255,255,255
35.                 status$ = "OUTSIDE"
36.         EndIf
37.                
38.         draw_polygon(bank_x, bank_y)
39.                
40.         Color 255,255,0
41.         Text 10,10,"Mouse is " + status$ + " polygon!"
42.                
43.         Flip 1
44.  
45. Wend
46.  
47. End
48.  
49.  
50. ;
51. ; Determines whether a point lies inside a convex polygon.
52. ;
53. ; Params:
54. ; x,y    - Coords of point to check.
55. ; vert_x - Float bank holding polygon vertex X coords.
56. ; vert_y - Float bank holding polygon vertex Y coords.
57. ;
58. ; Returns:
59. ; True if the point is inside the polygon, False otherwise.
60. ;
61. Function point_in_polygon(x#, y#, vert_x, vert_y)
62.  
63.         in = False
64.        
65.         last_byte = BankSize(vert_x) - 1
66.  
67.         For i = 0 To last_byte Step 4
68.        
69.                 If i Then j = (i - 4) Else j = (last_byte - 3)
70.                
71.                 x1# = PeekFloat(vert_x,i)
72.                 y1# = PeekFloat(vert_y,i)
73.  
74.                 x2# = PeekFloat(vert_x,j)
75.                 y2# = PeekFloat(vert_y,j)
76.  
77.                 If ((((y1 <= y) And (y < y2)) Or ((y2 <= y) And (y < y1))) And (x < (((x2 - x1) * (y - y1)) / (y2 - y1)) + x1))
78.                         in = Not in
79.                 EndIf
80.  
81.         Next
82.  
83.         Return in
84.        
85. End Function
86.  
87.  
88. ;
89. ; Draws a polygon.
90. ;
91. ; Params:
92. ; vert_x - Float bank holding polygon vertex X coords.
93. ; vert_y - Float bank holding polygon vertex Y coords.
94. ;
95. Function draw_polygon(vert_x, vert_y)
96.  
97.         last_byte = BankSize(vert_x) - 1
98.  
99.         For i = 0 To last_byte Step 4
100.        
101.                 If i Then j = (i - 4) Else j = (last_byte - 3)
102.                
103.                 x1# = PeekFloat(vert_x,i)
104.                 y1# = PeekFloat(vert_y,i)
105.  
106.                 x2# = PeekFloat(vert_x,j)
107.                 y2# = PeekFloat(vert_y,j)
108.  
109.                 Line x1, y1, x2, y2
110.  
111.         Next
112.  
113. End Function

Comments :


Chroma(Posted 1+ years ago)

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


big10p(Posted 1+ years ago)

 Glad you found it useful.


JBR(Posted 1+ years ago)

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

Code: [Select]

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(Posted 1+ years ago)

 hi"Only downside is arrays are not passed to functions"use Blitz arrays, only restriction is that must be unidimensional

Code: [Select]

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(Posted 1+ years ago)

 Here is the most optimised version I get at the moment(50-75% faster than JBR's code)

Code: [Select]

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
>=POLY_VERTS Then Return False;

; coordinates of the new point
pp[p
*2+0]=x;
pp[p
*2+1]=y;

; initialize bounds with first point
If p
=0
px0 = x
py0 = y
px1 = x
py1 = y
Else
; update bounds
If x<px0 Then px0=x;
If y<py0 Then py0=y;
If x>px1 Then px1=x;
If y>py1 Then py1=y;
EndIf
; increase vertices count.
p
=p
+1;
End Function



Function point_in_polygon(poly.TPoly, x#, y#)

; not enough points to make a single triangle
If poly
<3 Then Return;

; outside polygon boundaries
If x<polyx0 Then Return False;
If y<polyy0 Then Return False;
If x>polyx1 Then Return False;
If y>polyy1 Then Return False;

; first point is the last (to close the shape)
Local x2# = polyp[poly
*2-2];
Local y2# = polyp[poly
*2-1];

Local x1#,y1#

Local in% = False
Local i%

For i = 0 To poly
-1

x1=polyp[i*2+0];
y1=polyp[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
<3 Then Return;

Local x1#,y1#
Local x2# = polyp[poly
*2-2];
Local y2# = polyp[poly
*2-1];

Local i%
For i = 0 To poly
-1

x1=polyp[i*2+0];
y1=polyp[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(Posted 1+ years ago)

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


Bobysait(Posted 1+ years ago)

 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)

Code: [Select]

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(Posted 1+ years ago)

 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(Posted 1+ years ago)

 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)

Code: [Select]

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 pp[4]>=POLY_VERTS Then Return False;

Local n% = pp[4];
; coordinates of the new point
pp[5+n*2+0]=x;
pp[5+n*2+1]=y;

; initialize bounds with first point
If n=0
pp[0] = x
pp[1] = y
pp[2] = x
pp[3] = y
Else
; update bounds
If x<pp[0] Then pp[0]=x;
If y<pp[1] Then pp[1]=y;
If x>pp[2] Then pp[2]=x;
If y>pp[3] Then pp[3]=y;
EndIf
; increase vertices count.
pp[4]=pp[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(polyp, 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 polyp
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

Code: [Select]

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(Posted 1+ years ago)

 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". [/i]