Author Topic: Space Filling with Polygons  (Read 7791 times)

0 Members and 1 Guest are viewing this topic.

Offline Ashish

  • Forum Resident
  • Posts: 630
  • Never Give Up!
    • View Profile
Re: Space Filling with Polygons
« Reply #15 on: May 01, 2020, 12:23:26 am »
@Ashish,

Cool! but can you use this very code (with slight mod) to fill a big triangle with triangles and maybe squares pentagons, hexagons.... but at least triangles?
Oh.. So this is what you mean @bplus . Ok
Here new MOD. Now, you need to specify the shape in which you are going to do space filling and then you have to specify the shape
which is to be used for filling the area.
That is, you can now have triangles inside Pentagon, or Squares in inside triangles, etc.

Code: QB64: [Select]
  1. 'Space Filling with Polygon
  2. 'By Ashish
  3. 'MOD : RESTRICTED AREA
  4.  
  5. TYPE XY
  6.     x AS SINGLE
  7.     y AS SINGLE
  8.  
  9. _TITLE "Space Filling with Polygon [MOD : RESTRICTED AREA]"
  10. SCREEN _NEWIMAGE(800, 700, 32)
  11.  
  12. INPUT "Enter the number of side for polygon in which SPACE FILLING has to be done : ", a%
  13. IF a% < 3 THEN PRINT "It must be greate than 2!, taking default value of 3. Hit ENTER.": SLEEP: a% = 3
  14. INPUT "Enter the number of side for a polygon to fill in (must be greater than 2) : ", x%
  15. IF x% < 3 THEN PRINT "It must be greate than 2!, taking default value of 3. Hit ENTER.": SLEEP: x% = 3
  16. polySides = x%
  17. DIM tempPoly1(polySides - 1) AS XY, tempPoly2(polySides - 1) AS XY
  18. REDIM polys(polySides - 1) AS XY
  19.  
  20. Dim ShapeArea(a% - 1) as XY
  21. for j = 0 to ubound(ShapeArea)
  22.         ShapeArea(j).x = 400 + COS(j * (_PI(2 / a%))) * 350
  23.     ShapeArea(j).y = 350 + SIN(j * (_PI(2 / a%))) * 350
  24. ' drawPoly ShapeArea(), _RGB(255,255,255)
  25. init = 0
  26. poly_index = 0
  27. i = 1
  28. c = 1.1
  29. failed = 0
  30.         start:
  31.     IF init = 0 THEN
  32.         r = p5random(150, 200)
  33.         ox = p5random(r, _WIDTH - r)
  34.         oy = p5random(r, _HEIGHT - r)
  35.         offAng = p5random(-_PI, _PI)
  36.         FOR j = 0 TO polySides - 1
  37.             polys(j).x = ox + COS(j * (_PI(2 / polySides)) + offAng) * r
  38.             polys(j).y = oy + SIN(j * (_PI(2 / polySides)) + offAng) * r
  39.                         if not pointInsidePoly(polys(j), ShapeArea()) then goto start
  40.         NEXT
  41.         clr~& = midColor(_RGB(255, 255, 0), _RGB(255, 100, 0), map(r, 200, 3, 0, 1))
  42.         drawPoly polys(), clr~&
  43.         init = 1
  44.         poly_index = poly_index + polySides
  45.     ELSE
  46.         r = 200 / (c ^ i)
  47.         ox = p5random(r, _WIDTH - r)
  48.         oy = p5random(r, _HEIGHT - r)
  49.         collided = 0
  50.         offAng = p5random(-_PI, _PI)
  51.         FOR j = 0 TO polySides - 1
  52.             tempPoly1(j).x = ox + COS(j * (_PI(2 / polySides)) + offAng) * r
  53.             tempPoly1(j).y = oy + SIN(j * (_PI(2 / polySides)) + offAng) * r
  54.                         if not pointInsidePoly(tempPoly1(j), ShapeArea()) then goto start
  55.         NEXT
  56.         FOR j = 0 TO UBOUND(polys) STEP polySides
  57.             FOR k = j TO j + polySides - 1
  58.                 tempPoly2(k - j) = polys(k)
  59.             NEXT
  60.             IF polyCollide(tempPoly1(), tempPoly2()) THEN collided = -1: EXIT FOR
  61.         NEXT
  62.         IF NOT collided THEN
  63.             ' _echo "yes"
  64.             REDIM _PRESERVE polys(UBOUND(polys) + polySides) AS XY
  65.             FOR j = poly_index TO poly_index + polySides - 1
  66.                 polys(j) = tempPoly1(j - poly_index)
  67.             NEXT
  68.             clr~& = midColor(_RGB(255, 255, 0), _RGB(255, 100, 0), map(r, 200, 3, 0, 1))
  69.             drawPoly tempPoly1(), clr~&
  70.             poly_index = poly_index + polySides
  71.         ELSE
  72.             failed = failed + 1
  73.             IF failed > (i * 60) THEN i = i + 1: failed = 0
  74.         END IF
  75.     END IF
  76. LOOP UNTIL r < 3
  77.  
  78. FUNCTION midColor~& (clr1 AS _UNSIGNED LONG, clr2 AS _UNSIGNED LONG, v)
  79.     midColor~& = _RGB(map(v, 0, 1, _RED(clr1), _RED(clr2)), map(v, 0, 1, _GREEN(clr1), _GREEN(clr2)), map(v, 0, 1, _BLUE(clr1), _BLUE(clr2)))
  80.  
  81. SUB drawPoly (vert() AS XY, clr AS _UNSIGNED LONG)
  82.     n = UBOUND(vert)
  83.     DIM cx, cy
  84.     FOR i = 0 TO n
  85.         LINE (vert(i).x, vert(i).y)-(vert((i + 1) MOD (n + 1)).x, vert((i + 1) MOD (n + 1)).y), clr
  86.         cx = cx + vert(i).x: cy = cy + vert(i).y
  87.     NEXT
  88.     cx = cx / (n + 1): cy = cy / (n + 1)
  89.     PAINT (cx, cy), clr, clr
  90.  
  91.  
  92. FUNCTION polyCollide (vert1() AS XY, vert2() AS XY)
  93.     DIM n1 AS INTEGER, n2 AS INTEGER
  94.     n1 = UBOUND(vert1): n2 = UBOUND(vert2)
  95.     'checking if any point of polygon 1 inside polygon 2
  96.     FOR i = 0 TO n1
  97.         IF pointInsidePoly(vert1(i), vert2()) THEN polyCollide = -1: EXIT FUNCTION
  98.     NEXT
  99.     'checking if any point of polygon 2 inside polygon 1
  100.     FOR i = 0 TO n2
  101.         IF pointInsidePoly(vert2(i), vert1()) THEN polyCollide = -1: EXIT FUNCTION
  102.     NEXT
  103.     ' checking the edge intersection
  104.     FOR i = 0 TO n1
  105.         FOR j = 0 TO n2
  106.             IF lineIntersect(vert1(i).x, vert1(i).y, vert1((i + 1) MOD (n1 + 1)).x, vert1((i + 1) MOD (n1 + 1)).y, vert2(j).x, vert2(j).y, vert2((j + 1) MOD (n2 + 1)).x, vert2((j + 1) MOD (n2 + 1)).y) THEN polyCollide = -1: EXIT FUNCTION
  107.         NEXT
  108.     NEXT
  109.  
  110. 'from paulbourke.net
  111. FUNCTION pointInsidePoly (p AS XY, polyVert() AS XY)
  112.     DIM ax1, ax2, ay1, ay2
  113.     n = UBOUND(polyVert)
  114.     FOR i = 0 TO n
  115.         ax1 = polyVert(i).x - p.x
  116.         ay1 = polyVert(i).y - p.y
  117.         ax2 = polyVert((i + 1) MOD (n + 1)).x - p.x
  118.         ay2 = polyVert((i + 1) MOD (n + 1)).y - p.y
  119.         ang = ang + angle2D(ax1, ay1, ax2, ay2)
  120.     NEXT
  121.     pointInsidePoly = (ABS(ang) >= _PI)
  122.  
  123. 'from paulbourke.net
  124. FUNCTION angle2D (x1, y1, x2, y2)
  125.     DIM theta1, theta2, ftheta
  126.     theta1 = _ATAN2(y1, x1)
  127.     theta2 = _ATAN2(y2, x2)
  128.     ftheta = theta1 - theta2
  129.     WHILE ftheta > _PI: ftheta = ftheta - _PI(2): WEND
  130.     WHILE ftheta < -_PI: ftheta = ftheta + _PI(2): WEND
  131.     angle2D = ftheta
  132.  
  133. FUNCTION lineIntersect (__x1, __y1, __x2, __y2, __x3, __y3, __x4, __y4)
  134.     DIM x1 AS INTEGER, y1 AS INTEGER, x2 AS INTEGER, y2 AS INTEGER, x3 AS INTEGER, y3 AS INTEGER, x4 AS INTEGER, y4 AS INTEGER
  135.     DIM a1, b1, c1, a2, b2, c2
  136.     DIM a1b2_minus_a2b1, b1c2_minus_b2c1, a2c1_minus_a1c2
  137.     DIM inter_x AS INTEGER, inter_y AS INTEGER
  138.  
  139.     x1 = __x1: x2 = __x2: x3 = __x3: x4 = __x4
  140.     y1 = __y1: y2 = __y2: y3 = __y3: y4 = __y4
  141.    
  142.     IF x1 > x2 THEN SWAP x1, x2
  143.     IF x3 > x4 THEN SWAP x3, x4
  144.     IF y1 > y2 THEN SWAP y1, y2
  145.     IF y3 > y4 THEN SWAP y3, y4
  146.    
  147.     a1 = __y2 - __y1: b1 = -(__x2 - __x1): c1 = (__x2 * __y1) - (__x1 * __y2)
  148.     a2 = __y4 - __y3: b2 = -(__x4 - __x3): c2 = (__x4 * __y3) - (__x3 * __y4)
  149.  
  150.     'check if lines are perfectly vertical or horizontal
  151.     IF a1 = 0 AND a2 = 0 THEN lineIntersect = (__y1 = __y3): _DEST 0: EXIT FUNCTION
  152.     IF b1 = 0 AND b2 = 0 THEN lineIntersect = (__x1 = __x3): _DEST 0: EXIT FUNCTION
  153.     IF a2 = 0 OR b2 = 0 THEN GOTO skip_component_ratio
  154.    
  155.     'check if the whole line segments coincide with each other.
  156.     IF c2 <> 0 THEN
  157.         IF (a1 / a2) = (b1 / b2) AND (b1 / b2) = (c1 / c2) THEN
  158.             lineIntersect = -1: EXIT FUNCTION
  159.         END IF
  160.     END IF
  161.     skip_component_ratio:
  162.     'check if the line segments have same slope.
  163.     IF a1 * b2 = a2 * b1 THEN
  164.         lineIntersect = (c1 = c2) 'special case, when they still coincide (as c1=c2)
  165.         EXIT FUNCTION
  166.     END IF
  167.     'check if the line do intersect between the segments.
  168.     a1b2_minus_a2b1 = (a1 * b2) - (a2 * b1): b1c2_minus_b2c1 = (b1 * c2) - (b2 * c1): a2c1_minus_a1c2 = (a2 * c1) - (a1 * c2)
  169.     inter_x = b1c2_minus_b2c1 / a1b2_minus_a2b1: inter_y = a2c1_minus_a1c2 / a1b2_minus_a2b1
  170.    
  171.     lineIntersect = ((inter_x >= x1 AND inter_x <= x2 AND inter_y >= y1 AND inter_y <= y2)) and ((inter_x >= x3 AND inter_x <= x4 AND inter_y >= y3 AND inter_y <= y4))
  172.  
  173. 'taken from p5js.bas
  174. FUNCTION map! (value!, minRange!, maxRange!, newMinRange!, newMaxRange!)
  175.     map! = ((value! - minRange!) / (maxRange! - minRange!)) * (newMaxRange! - newMinRange!) + newMinRange!
  176.  
  177. FUNCTION p5random! (mn!, mx!)
  178.     IF mn! > mx! THEN
  179.         SWAP mn!, mx!
  180.     END IF
  181.     p5random! = RND * (mx! - mn!) + mn!
  182.  



Screenshot_0.png


Squares inside pentagon


 
Screenshot_1.png


Pentagons inside triangle
if (Me.success) {Me.improve()} else {Me.tryAgain()}


My Projects - https://github.com/AshishKingdom?tab=repositories
OpenGL tutorials - https://ashishkingdom.github.io/OpenGL-Tutorials

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Space Filling with Polygons
« Reply #16 on: May 01, 2020, 02:48:24 am »
@Ashish,

Nailed it! :)

Offline _vince

  • Seasoned Forum Regular
  • Posts: 422
    • View Profile
Re: Space Filling with Polygons
« Reply #17 on: May 01, 2020, 06:35:48 am »
Nice pattern guys ;-) ;-)

Here is my experiment
Code: [Select]
defdbl a-z
const sw = 1024
const sh = 768
pi = 4*atn(1)

screen _newimage(sw, sh, 32)
line (0,0)-(sw,sh),_rgb(0,0,0),bf

a = sh
bplus sw/2, sh/2, a, 0, _rgb(50,0,0), _rgb(0,0,0)
c = 1.5
n = 7
for i=2 to n
        a = sh/(i^(c*c))
        for j=0 to 2000
                x = sw/2 - a*(i^(c*c))/2 + a*(i^(c*c))*rnd
                y = sh/2 - a*(i^(c*c))/2 + a*(i^(c*c))*rnd
                rot = 2*pi*rnd'*(i - 1)
                bplus x, y, a, rot, _rgb(50 + (i-1)*205/n,0,0), _rgb(50,0,0)
        next
next

sleep
system

sub bplus (x0, y0, a, rot, cc as _integer64, cp as _integer64)
        p = 50/400
        q = 20/400

        dim img as long
        img = _newimage(a, a, 32)

        _dest img
        line (0,0)-(a,a),cp,bf
        for y=0 to a - 1
        for x=0 to a - 1
                if (((x + p*a)^2 + (y - a/2)^2) > a*a*(q + 0.5)^2) and (((x - a - p*a)^2 + (y - a/2)^2) > a*a*(q + 0.5)^2) or (((y + p*a)^2 + (x - a/2)^2) > a*a*(q + 0.5)^2) and (((y - a - p*a)^2 + (x - a/2)^2) > a*a*(q + 0.5)^2) then pset (x, y), cc
        next
        next

        dim tl as long, tr as long, bl as long, br as long
        dim r as integer, g as integer, b as integer

        yes = 1
        a2 = a*(sqr(2) - 0.5)
        _dest 0
        for y=-a2 to a + a2
        for x=-a2 to a + a2
                xx = (x - a/2)*cos(rot) - (y - a/2)*sin(rot) + a/2
                yy = (x - a/2)*sin(rot) + (y - a/2)*cos(rot) + a/2

                if (xx >= 0 and xx < a-1 and yy >= 0 and yy < a-1) then
                        _source img
                        if point (xx, yy) <> cp then
                                _source 0
                                if point(x0 - a/2 + x, y0 - a/2 + y) <> cp then yes = 0
                        end if
                end if
        next
        next

        if yes then
                _dest 0
                for y=-a2 to a + a2
                for x=-a2 to a + a2
                        xx = (x - a/2)*cos(rot) - (y - a/2)*sin(rot) + a/2
                        yy = (x - a/2)*sin(rot) + (y - a/2)*cos(rot) + a/2

                        if (xx >= 0 and xx < a-1 and yy >= 0 and yy < a-1) then
                                _source img
                                if int(xx) > a-1 or int(yy) > a-1 then tl = cp else tl = point(int(xx), int(yy))
                                if int(xx) > a-1 or int(yy) > a-1 or int(xx)+1 > a-1 then tr = cp else tr = point(int(xx) + 1, int(yy))
                                if int(xx) > a-1 or int(yy) > a-1 or int(yy)+1 > a-1 then bl = cp else bl = point(int(xx), int(yy) + 1)
                                if int(xx) > a-1 or int(yy) > a-1 or int(xx)+1 > a-1 or int(yy)+1 > a-1 then br = cp else br = point(int(xx) + 1, int(yy) + 1)

                                dx = xx - int(xx)
                                dy = yy - int(yy)

                                r = _round((1 - dy)*((1 - dx)*  _red(tl) + dx*  _red(tr)) + dy*((1 - dx)*  _red(bl) + dx*  _red(br)))
                                g = _round((1 - dy)*((1 - dx)*_green(tl) + dx*_green(tr)) + dy*((1 - dx)*_green(bl) + dx*_green(br)))
                                b = _round((1 - dy)*((1 - dx)* _blue(tl) + dx* _blue(tr)) + dy*((1 - dx)* _blue(bl) + dx* _blue(br)))

                                if point (xx, yy) <> cp then pset (x0 - a/2 + x, y0 - a/2 + y), _rgb(r,g,b)
                        end if
                next
                next
        end if

        _freeimage img
end sub
qb64sfx.png
* qb64sfx.png (Filesize: 84.29 KB, Dimensions: 1024x1536, Views: 324)

Offline Ashish

  • Forum Resident
  • Posts: 630
  • Never Give Up!
    • View Profile
Re: Space Filling with Polygons
« Reply #18 on: May 01, 2020, 08:52:12 am »
Hi _vince, that screenshots is awesome! :D
But, your program is running slowly. Is this my PC fault or your program do lot of calculations?
if (Me.success) {Me.improve()} else {Me.tryAgain()}


My Projects - https://github.com/AshishKingdom?tab=repositories
OpenGL tutorials - https://ashishkingdom.github.io/OpenGL-Tutorials

Offline _vince

  • Seasoned Forum Regular
  • Posts: 422
    • View Profile
Re: Space Filling with Polygons
« Reply #19 on: May 01, 2020, 09:09:00 am »
It's not really optimized, it does pixel by pixel overlap detection.  I let it run and came back an hour later for a slightly bigger picture but not as pretty as I was hoping

qb64sf3.png
* qb64sf3.png (Filesize: 189.18 KB, Dimensions: 1680x1050, Views: 318)