Point in Polygon function

[AndyA]

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

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.  
6. RANDOMIZE (TIMER)
7. DIM SHARED xp(99) AS DOUBLE
8. DIM SHARED yp(99) AS DOUBLE
9. DIM st AS DOUBLE
10. DIM et AS DOUBLE
11.  
12. SCREEN 12
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
64. WEND
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
92. END FUNCTION
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
100. END SUB
101.  
102. FUNCTION rand% (low%, high%)
103.     rand = INT(RND * (high% - low% + 1)) + low%
104. END FUNCTION
105.  
106. FUNCTION min% (flt1 AS INTEGER, flt2 AS INTEGER)
107.     IF flt1 < flt2 THEN min = flt1 ELSE min = flt2
108. END FUNCTION
109.  
110. FUNCTION max% (flt1 AS INTEGER, flt2 AS INTEGER)
111.     IF flt2 > flt1 THEN max = flt2 ELSE max = flt1
112. END FUNCTION
113.  

[RhoSigma]

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.

[AndyA]

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 :)

[bplus]

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)).

[AndyA]

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. 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 )

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?

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