Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: AndyA on December 02, 2019, 01:23:30 am

Title: Point in Polygon function
Post by: AndyA on December 02, 2019, 01:23:30 am
Here's a nice and fast 'Point in Polygon' function.

The demo code fills a randomly generated polygon and tests each point inside of the bounding box of the polygon. Not very efficient, but demonstrates the speed of testing lots of points using this function.

I've used this function for two types of 'games', a jigsaw puzzle game in JustBasic, and in an SDL Basic hidden object game by Johnno56.

The Just Basic jigsaw puzzle DL's are still available at http://jbfilesarchive.com/phpBB3/viewtopic.php?f=4&t=2123 (http://jbfilesarchive.com/phpBB3/viewtopic.php?f=4&t=2123)

Of course you'll need to DL and install JustBasic to run the jigsaw puzzles. (Windows only! Sorry linux and Mac users. Though should work fine with Wine)

For the SDL Basic hidden object game, maybe Johnno56 can help me out with a link to the game and a good link for the SDL Basic install.

Another use that comes to mind is one that Qwerky/Richard Notely has already made for QB64. A shooting gallery game.

And a mirror object game.



Code: QB64: [Select]
  1. 'http://alienryderflex.com/polygon/
  2. 'QB64 version by Andy Amaya
  3.  
  4. _TITLE "Point in Polygon Function (screen 12)"
  5.  
  11.  
  13. COLOR 15, 1
  14.  
  15. WHILE again% = 0
  16.  
  17.     CLS
  18.     LINE (0, 0)-(639, 479), 1, BF
  19.     pip& = 0
  20.     minX% = 9999
  21.     maxX% = 0
  22.     minY% = 9999
  23.     maxY% = 0
  24.     numVerts% = rand(3, 4)
  25.     FOR i% = 0 TO numVerts% - 1
  26.         xp(i%) = rand(100, 540)
  27.         yp(i%) = rand(80, 440)
  28.         minX% = min(minX%, xp(i%))
  29.         maxX% = max(maxX%, xp(i%))
  30.         minY% = min(minY%, yp(i%))
  31.         maxY% = max(maxY%, yp(i%))
  32.     NEXT
  33.     COLOR 14, 1
  34.     PRINT "Number of vertices: "; numVerts%
  35.  
  36.     st = TIMER(.001)
  37.     FOR yy# = minY% TO maxY%
  38.         FOR xx# = minX% TO maxX%
  39.             test% = pointInPoly(xx#, yy#, numVerts%)
  40.             IF test% = 1 THEN
  41.                 PSET (xx#, yy#)
  42.                 pip& = pip& + 1
  43.             END IF
  44.         NEXT
  45.     NEXT
  46.     'drawPoly numVerts%, 5
  47.     et = TIMER(.001) - st
  48.  
  49.     COLOR 14, 1
  50.     PRINT "Number of points in polygon: "; pip&
  51.     total& = maxX% * maxY%
  52.     PRINT "Total number of points tested: "; total&
  53.     PRINT "Elapsed time: "; USING "###"; (et * 1000);
  54.     PRINT " milliseconds"
  55.  
  56.     SLEEP
  57.     a$ = INKEY$
  58.     IF a$ = " " THEN
  59.         again% = 0
  60.     ELSE
  61.         'a$ = ""
  62.         again% = 1
  63.     END IF
  65.  
  66.  
  67. FUNCTION pointInPoly% (x AS DOUBLE, y AS DOUBLE, verts AS INTEGER)
  68.     DIM i AS INTEGER
  69.     DIM j AS INTEGER
  70.     DIM c AS INTEGER
  71.     DIM v1 AS DOUBLE
  72.     DIM v2 AS DOUBLE
  73.     DIM v3 AS DOUBLE
  74.     DIM v4 AS DOUBLE
  75.     DIM v5 AS DOUBLE
  76.     DIM v6 AS DOUBLE
  77.     DIM v7 AS DOUBLE
  78.     c = 0
  79.     FOR i = 0 TO verts - 1
  80.         j = (i + 1) MOD verts
  81.         v1 = (yp(i) <= y)
  82.         v2 = (y < yp(j))
  83.         v3 = (yp(j) <= y)
  84.         v4 = (y < yp(i))
  85.         v5 = (xp(j) - xp(i)) * (y - yp(i))
  86.         v6 = (yp(j) - yp(i))
  87.         IF v6 = 0.0 THEN v6 = 0.000001
  88.         v7 = xp(i%)
  89.         IF (((v1 AND v2) OR (v3 AND v4)) AND (x < v5 / v6 + v7)) THEN c = 1 - c
  90.     NEXT
  91.     pointInPoly = c
  93.  
  94. SUB drawPoly (verts AS INTEGER, colr AS INTEGER)
  95.     j% = verts - 1
  96.     FOR i% = 0 TO verts - 1
  97.         LINE (xp(j%), yp(j%))-(xp(i%), yp(i%)), colr%
  98.         j% = i%
  99.     NEXT
  101.  
  102. FUNCTION rand% (low%, high%)
  103.     rand = INT(RND * (high% - low% + 1)) + low%
  105.  
  106. FUNCTION min% (flt1 AS INTEGER, flt2 AS INTEGER)
  107.     IF flt1 < flt2 THEN min = flt1 ELSE min = flt2
  109.  
  110. FUNCTION max% (flt1 AS INTEGER, flt2 AS INTEGER)
  111.     IF flt2 > flt1 THEN max = flt2 ELSE max = flt1
  113.  
Title: Re: Point in Polygon function
Post by: RhoSigma on December 02, 2019, 01:47:44 am
Hi Andy,
see you already made your 2nd polygon function based on http://alienryderflex.com/. Before you go for the next one you should have a look on my DRF-Polygons library, which have some those functions ready since years. However, if it's for educational purpose, then just go ahead with your own implementations.

Just in case you wanna save yourself some work, my DRF-Polygons library is part of the QB64-Library.7z archive available in the Bonus section of the download page mentioned below in my signature. Sample programs and a nice HTML-Documentation included.

Title: Re: Point in Polygon function
Post by: AndyA on December 02, 2019, 02:02:10 am
Hi RhoSigma,

I've been using those functions since 2011. Mostly in BlitzPlus basic and JustBasic for a jigsaw puzzle game. Also used those in SDL Basic later on.

Will look into your QB64 LIB, sounds interesting.

Cheers :)

Title: Re: Point in Polygon function
Post by: bplus on December 02, 2019, 10:27:35 am
Hi Andy,

Seems like we are close to painting enclosed (or framed by screen) areas, an exercise we recently experimented with in the Paint Image thread. I wonder how this code compares?

Andy do you know about working images in separate destination and using as needed with _PUTIMAGE or _MAPTRIANGLE, setup a drawing area and handle& with _NEWIMAGE. Also in QB64 you can pass arrays and arrays of TYPE like points (unlike JB and SDL (actually don't remember if SDL could or couldn't)).
Title: Re: Point in Polygon function
Post by: AndyA on December 04, 2019, 11:10:40 pm
Quote
Seems like we are close to painting enclosed (or framed by screen) areas, an exercise we recently experimented with in the Paint Image thread. I wonder how this code compares?

I would use the scan line polygon fill to accomplish filling an area when ever possible https://www.qb64.org/forum/index.php?topic=1946.0 (https://www.qb64.org/forum/index.php?topic=1946.0). For simple polygon shapes, polyFill is the way to go. What I mean by simple is that the number of polygon vertices should be below a threshold of 100 vertices. There is no practical limit to the number of vertices that can be processed by this algo, but the monotonous effort of converting all of the vertices of let's say of a 'perfect' maze image with an entrance and an exit to x/y coordinates would be a nightmare. You could of course use a polygon editor to plot all of those vertices to x/y coords, but it is still very tedious. (Link for JB Polygon Editor http://jbfilesarchive.com/phpBB3/download/file.php?id=1614 (http://jbfilesarchive.com/phpBB3/download/file.php?id=1614) )

With the Scan Line Filled Polygon link above, the 62 vertices jigsaw piece shaped polygon is filled within 2ms - 3ms on my laptop. Is that fast or slow when compared to yours and Steve's method?

Quote
Andy do you know about working images in separate destination and using as needed with _PUTIMAGE or _MAPTRIANGLE, setup a drawing area and handle& with _NEWIMAGE.

I know conceptually how to do all of those things in QB64 but still am figuring out all the syntactic nuances. In BlitzPlus basic I'd use 'imagehandle% - CreateImage(width, height) just like 'imagehandle& = _NewImage(width, height, 32), easy peasy.

It's the _Source, _Dest, _PutImage while easy enough to understand the concepts, the syntax is a bit of a drain on my nerves, not that there's anything wrong with the commands, just saying...
Text Only | Text with Attachments