November 24, 2020, 06:27:58 AM

### Author Topic: [bb] point_in_polygon by big10p [ 1+ years ago ]  (Read 780 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] point_in_polygon by big10p [ 1+ years ago ]
« on: June 29, 2017, 12:28:38 AM »
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

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)

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,2SetBuffer 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_VERTSang# = 0.0For 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 + daNextA_x# ( POLY_VERTS ) = A_x#(0) ; easy wrappingA_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 1WendEnd;; 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 NextEnd 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], iFor i=0 To 10 A[i]=0.1*i DebugLog a[i]NextClearArray(a)For i=0 To 10 DebugLog a[i]NextWaitKeyEndFunction ClearArray(array#[10]) Local i For i=0 To 10 array[i]=0 NextEnd 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 boundsEnd TypeFunction newPoly.TPoly() Return New TPoly;End FunctionFunction 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 FunctionFunction 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 FunctionFunction 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 FunctionGraphics ( 800,600,0,2 );SetBuffer ( BackBuffer() );SeedRnd ( MilliSecs() );; Create a polygon containerLocal poly.TPoly = newPoly();; add random pointsLocal 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 imageLocal 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.glmax2dImport brl.randomGraphics 800,600,0,0Type 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 TypeGraphics ( 800,600,0,2 );SeedRnd ( MilliSecs() );Local nVerts% = 100;' Create a polygon containerLocal poly:TPoly = New TPoly;' add random pointsLocal 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 imageLocal 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*2Type TPoly Field p%[POLY_LENGTH]; vertices coordinates (x,y)End TypeFunction newPoly.TPoly() Return New TPoly;End FunctionFunction 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]+1End FunctionFunction 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 FunctionFunction point_in_polygon(poly.TPoly, x%, y%) Return point_in_polygon_array(polyp, x,y)End FunctionFunction 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 FunctionFunction draw_polygon(poly.TPoly) draw_polygon_array polypEnd FunctionGraphics ( 800,600,0,2 );SetBuffer ( BackBuffer() );SeedRnd ( MilliSecs() );; Create a polygon containerLocal poly.TPoly = newPoly();; add random pointsLocal 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 imageLocal 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.glmax2dImport brl.randomGraphics 800,600,0,0Type 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 TypeGraphics ( 800,600,0,2 );SeedRnd ( MilliSecs() );Local nVerts% = 100;' Create a polygon containerLocal poly:TPoly = New TPoly;' add random pointsLocal 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 imageLocal 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]