QB64.org Forum

Active Forums => Programs => Topic started by: david_uwi on February 04, 2020, 07:01:11 pm

Title: Joining the points of regular polygons
Post by: david_uwi on February 04, 2020, 07:01:11 pm
What is the minimum length of lines required to join the points of a regular polygon?
3 (triangle) is fairly easy, but what about a square (or a pentagon)?
As I was going through my old programs I found this (below) to do a triangle (iteratively).
The puzzle is normally phrased as a road building exercise - what is the minimum length of road needed to join four towns which happen to be at the vertices of a square.
So as a challenge can you do the same for 4 towns as I have done for 3. If that is too easy try 5.

Code: QB64: [Select]
  1. nn = 3
  2. rsummin = 10000: m = 1: n = 200
  3. WHILE m < 1000
  4.     x1 = (RND * 360)
  5.     y1 = (RND * 300)
  6.     IF m > 2 THEN
  7.         x1 = xa - n / m + RND * 2 * n / m
  8.         y1 = ya - n / m + RND * 2 * n / m
  9.     END IF
  10.     m = m + .1
  11.     x(1) = 60: y(1) = 300
  12.     x(2) = 360: y(2) = 300
  13.     x(3) = 210: y(3) = 40
  14.     FOR i = 1 TO nn
  15.         r(i) = SQR((x1 - x(i)) ^ 2 + (y1 - y(i)) ^ 2)
  16.     NEXT i
  17.     rsum = r(1) + r(2) + r(3)
  18.     IF rsum < rsummin THEN
  19.         rsummin = rsum
  20.         xa = x1: xb = x2: ya = y1: yb = y2
  21.         m = m + 1
  22.         CLS
  23.         FOR i = 1 TO nn
  24.             CIRCLE (x(i), y(i)), 10
  25.             LINE (x1, y1)-(x(i), y(i))
  26.         NEXT i
  27.         CIRCLE (x1, y1), 5
  28.         LOCATE 1, 1
  29.         q1 = SQR((x(1) - x(3)) ^ 2 + (y(1) - y(3)) ^ 2)
  30.         q2 = SQR((x(2) - x(3)) ^ 2 + (y(2) - y(3)) ^ 2)
  31.         PRINT rsummin * 20 / (q1 + q2)
  32.         tt = TIMER
  33.         WHILE TIMER - tt < .2: WEND
  34.     END IF
  35. LOCATE 3, 1
  36. PRINT "Finished"
  37. xx$ = INPUT$(1)
  38.  
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 07:12:59 pm
This sounds like calculating the centroid of a set of points, is that wrong?
Title: Re: Joining the points of regular polygons
Post by: david_uwi on February 04, 2020, 07:18:49 pm
No, you will find for a square that the shortest distance is not drawing two diagonals.
So if the sides of the square are 10. Around the perimeter is 30, drawing two diagonals is 28.28 (approx). Surprisingly there is an even shorter way.
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 07:21:30 pm
Fascinating! I'm gonna play with this (on paper using calculus for N points). Maybe someone can demo up the N=4 case before I crack the general problem.
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 07:43:42 pm
Hmmm, I kept on reproducing the centroid case for the answer to this on the back of some legal documents I ignore - but anyway - I'm still working on intuitively seeing it. Like if I start with a solved case and then introduce a new point very far away, how does the answer change? Mathematical intuition aside, I configured your code for N=4 points on a square, and sure enough, it gave me the centroid. What am I not getting? (See attached)
Title: Re: Joining the points of regular polygons
Post by: SMcNeill on February 04, 2020, 07:48:33 pm
What am I not getting? (See attached)

Warp drive?  ;D

(I couldn’t resist. :P)

Actually, I’d guess maybe a 3/4 circle with the polygon inside it.  Take the square and draw a “C” to connect the points....

Maybe..
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 08:10:46 pm
Is there something about the phrasing of the question that might not have transcribed? If not the centroid, this only reminds me of the traveling salesman problem.
Title: Re: Joining the points of regular polygons
Post by: bplus on February 04, 2020, 08:45:18 pm
No, you will find for a square that the shortest distance is not drawing two diagonals.
So if the sides of the square are 10. Around the perimeter is 30, drawing two diagonals is 28.28 (approx). Surprisingly there is an even shorter way.

I get 28.28... also and it would be a surprise if it were less. Are you saying there is a point other than middle that connects to each of the other 4 points and the distance of all lines is less than 28.28...?

BTW perimeter is 40.
Title: Re: Joining the points of regular polygons
Post by: bplus on February 04, 2020, 08:51:32 pm
Oh wait I remember this, there are two points in the middle area and 120 degrees goes from two of corners to one middle point and line from that middle point to the other which connects the other 2 corners:


      \_/
      / \

But that makes more sense with rectangle.

update: I should say the lines from a middle point are all 120 degrees from each other = 360 total angle.
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 08:52:07 pm
Translation of 28.28 = 4 * 10 * sqrt(2) / 2
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 08:53:44 pm
Ah, that's a new angle. I bet that's what the problem is actually about. Even if not, that's interesting as hell.

EDIT: Oh boy, I see a dirty way to do this, and another way that's... crap there might go my week if I'm not careful.

If there's a pattern at all yet, we might have

Code: QB64: [Select]
  1. 2 points                          - requires 0 nodes
  2. 3 points in equilateral triangle  - requires 1 node
  3. 4 points making a square          - requires 2 nodes
  4. 5 points as a pentagon            - 3?
  5.  

And then there's this technique - plot the given points as given, and then let there be a bunch, who cares - 1000 proposed nodes that connect to every single point and every other node, and these can move. This foregoes keeping track of vectors as a useful exercise, but what I *did* notice is that the correct solution minimizes ink on the page, supposing overlapping dots and lines are drawn once. I'm not sure if I can capture this in an equation without just using a program.
Title: Re: Joining the points of regular polygons
Post by: bplus on February 04, 2020, 09:22:30 pm
hyp * cos(30) = 5   then hyp = 5/cos(30) = 5.7736... x4 = 23.0946... for 4 corner lines

line in middle = 10 - 2 * (5.77 * sin(30) = 2.885) = 10 - 5.77 = 4.23

total of 5 lines = 23.0946 + 4.23... = 27. 32... < 28.28!

Using my numbers and scale 1 unit = 40 pixels our 10x10 gets mapped out like this:
Code: QB64: [Select]
  1. SCREEN _NEWIMAGE(500, 500, 32)
  2. LINE (50, 50)-(450, 450), , B '400 side  / 40 = 10
  3.  
  4. drawLine 50, 50, 60, 40 * 5.77
  5. drawLine 450, 50, 120, 40 * 5.77
  6. drawLine 450, 450, 240, 40 * 5.77
  7. drawLine 50, 450, 300, 40 * 5.77
  8. LINE (2.885 * 40 + 50, 5 * 40 + 50)-STEP(4.23 * 40, 0)
  9.  
  10. SUB drawLine (x, y, degreeAngle, dist)
  11.     x1 = x + dist * COS(_D2R(degreeAngle))
  12.     y1 = y + dist * SIN(_D2R(degreeAngle))
  13.     LINE (x, y)-(x1, y1)
  14.  


Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 04, 2020, 09:34:02 pm
Right, that's more like it.

I keep trying to approach this problem in a discrete math kind of way before turning to code. Here's something interesting - david asks about regular polygons, a handful of which can tile the 2D plane. If I cover an XY grid with squares, well, I can also cover it with the solution, making hexagons and diamonds if you draw it. So - is there anything about one tiling that leads to the other without knowing ahead of time that they are connected by the answer to this problem?

EDIT

Maybe minimizing the total length of road tends to maximize a particular area in a tiling scheme.
Title: Re: Joining the points of regular polygons
Post by: bplus on February 05, 2020, 12:18:40 pm
Here is my purposed road system for a Pentagon, can anyone find better = shorter?
Code: QB64: [Select]
  1. _TITLE "Road to Pentagon" 'b+ 2020-02-05 in search of shortest road system to rech all points of Pentagon
  2. SCREEN _NEWIMAGE(500, 500, 32)
  3. TYPE xy
  4.     x AS SINGLE
  5.     y AS SINGLE
  6. DIM p(4) AS xy
  7.  
  8. polygon 250, 250, 200, 5, _PI(-1 / 10), p(), side 'side = 235.1141
  9. 'cos(30) = (235.1141/2) / h
  10. hyp = (235.1141 / 2) / COS(_D2R(30))
  11. drawLine p(1).x, p(1).y, 210, hyp, i1x, i1y
  12. drawLine p(2).x, p(2).y, 330, hyp, i1x, i1y
  13. LINE (p(3).x, p(3).y)-(p(0).x, p(0).y)
  14. LINE (p(4).x, p(4).y)-(i1x, i1y)
  15. D1 = SQR((p(0).x - p(3).x) ^ 2 + (p(0).y - p(3).y) ^ 2)
  16. D2 = SQR((p(4).x - i1x) ^ 2 + (p(4).y - i1y) ^ 2)
  17. LOCATE 29, 1: PRINT "Distance of 5 spokes or 5 * radius = 1000"
  18. LOCATE 30, 1: PRINT "Sum of 4 inner lines here is"; D1 + D2 + 2 * hyp
  19.  
  20. SUB drawLine (x, y, degreeAngle, dist, x1, y1)
  21.     x1 = x + dist * COS(_D2R(degreeAngle))
  22.     y1 = y + dist * SIN(_D2R(degreeAngle))
  23.     LINE (x, y)-(x1, y1)
  24.  
  25. SUB polygon (xOrigin, yOrigin, radius, nVertex, RadianAngleOffset, p() AS xy, side)
  26.     polyAngle = _PI(2) / nVertex
  27.     p(0).x = xOrigin + radius * COS(RadianAngleOffset)
  28.     p(0).y = yOrigin + radius * SIN(RadianAngleOffset)
  29.     FOR i = 1 TO nVertex - 1
  30.         p(i).x = xOrigin + radius * COS(i * polyAngle + RadianAngleOffset)
  31.         p(i).y = yOrigin + radius * SIN(i * polyAngle + RadianAngleOffset)
  32.         LINE (p(i - 1).x, p(i - 1).y)-(p(i).x, p(i).y)
  33.     NEXT
  34.     LINE (p(i - 1).x, p(i - 1).y)-(p(0).x, p(0).y)
  35.     side = SQR((p(i - 1).x - p(0).x) ^ 2 + (p(i - 1).y - p(0).y) ^ 2)
  36.     FOR i = 0 TO 4
  37.         PRINT p(i).x, p(i).y
  38.     NEXT
  39.     PRINT " side:"; side
  40.  
  41.  
Title: Re: Joining the points of regular polygons
Post by: david_uwi on February 05, 2020, 01:29:33 pm
Here's my solution...(it may find a false minimum occasionally so stick with it the length should be 38.91)
There is now a Wikipedia page on "Steiner trees" which rather gives it away.

https://en.wikipedia.org/wiki/Steiner_tree_problem
 
Code: QB64: [Select]
  1. 'DEFDBL A-Z
  2. nn = 5
  3. rsummin = 10000: m = 1: n = 200
  4. WHILE m < 1000
  5.     x1 = (RND * 300)
  6.     y1 = (RND * 300)
  7.     x2 = (RND * 300)
  8.     y2 = (RND * 300)
  9.     x3 = (RND * 300)
  10.     y3 = (RND * 300)
  11.     IF m > 2 THEN
  12.         x1 = xa - n / m + RND * 2 * n / m
  13.         x2 = xb - n / m + RND * 2 * n / m
  14.         y1 = ya - n / m + RND * 2 * n / m
  15.         y2 = yb - n / m + RND * 2 * n / m
  16.         x3 = xc - n / m + RND * 2 * n / m
  17.         y3 = yc - n / m + RND * 2 * n / m
  18.     END IF
  19.     m = m + .05
  20.     RESTORE
  21.     rsum = 0
  22.     rmin1 = 10000: rmin2 = 10000: rmin3 = 10000: rmin4 = 10000: rmin5 = 10000
  23.     pi = 3.141593
  24.     nx = nn / 2
  25.     FOR i = 1 TO nn
  26.         ang = i * pi / nx + pi / nn
  27.         x(i) = 150 - 150 * SIN(ang): y(i) = 150 - 150 * COS(ang)
  28.         r(i) = SQR((x1 - x(i)) ^ 2 + (y1 - y(i)) ^ 2)
  29.         IF r(i) < rmin1 THEN imin1 = i: rmin1 = r(i)
  30.     NEXT i
  31.     FOR i = 1 TO nn
  32.         IF i = imin1 THEN 5
  33.         IF r(i) < rmin2 THEN imin2 = i: rmin2 = r(i)
  34.    5 NEXT i
  35.  
  36.     FOR i = 1 TO nn
  37.         IF imin1 = i THEN 10
  38.         IF imin2 = i THEN 10
  39.         r(i) = SQR((x2 - x(i)) ^ 2 + (y2 - y(i)) ^ 2)
  40.         IF r(i) < rmin3 THEN imin3 = i: rmin3 = r(i)
  41.    10 NEXT i
  42.     FOR i = 1 TO nn
  43.         IF imin1 = i THEN 15
  44.         IF imin2 = i THEN 15
  45.         IF imin3 = i THEN 15
  46.         IF r(i) < rmin4 THEN imin4 = i: rmin4 = r(i)
  47.    15 NEXT i
  48.     rsum = r(imin1) + r(imin2) + r(imin3) + r(imin4)
  49.     FOR i = 1 TO nn
  50.         IF imin1 = i THEN 20
  51.         IF imin2 = i THEN 20
  52.         IF imin3 = i THEN 20
  53.         IF imin4 = i THEN 20
  54.         r(i) = SQR((x3 - x(i)) ^ 2 + (y3 - y(i)) ^ 2)
  55.         IF r(i) < rmin5 THEN imin5 = i: rmin5 = r(i)
  56.    20 NEXT i
  57.  
  58.     rra = SQR((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
  59.     rrb = SQR((x1 - x3) ^ 2 + (y1 - y3) ^ 2)
  60.     rrc = SQR((x2 - x3) ^ 2 + (y2 - y3) ^ 2)
  61.     a12 = 1: a13 = 2: a23 = 3
  62.     IF rrb > rra THEN SWAP rra, rrb: SWAP a12, a13
  63.     IF rrc > rra THEN SWAP rra, rrc: SWAP a12, a23
  64.     IF rrc > rrb THEN SWAP rrc, rrb: SWAP a23, a13
  65.     rsum = rsum + rrb + rrc + r(imin5)
  66.     IF rsum < rsummin THEN
  67.         rsummin = rsum
  68.         xa = x1: xb = x2: ya = y1: yb = y2: xc = x3: yc = y3
  69.         m = m + .5
  70.         CLS
  71.         FOR i = 1 TO nn
  72.             CIRCLE (x(i) + 100, y(i) + 100), 10
  73.         NEXT i
  74.         CIRCLE (x1 + 100, y1 + 100), 5
  75.         CIRCLE (x2 + 100, y2 + 100), 5
  76.         CIRCLE (x3 + 100, y3 + 100), 5
  77.         IF a12 <> 1 THEN LINE (x1 + 100, y1 + 100)-(x2 + 100, y2 + 100)
  78.         IF a13 <> 1 THEN LINE (x1 + 100, y1 + 100)-(x3 + 100, y3 + 100)
  79.         IF a23 <> 1 THEN LINE (x2 + 100, y2 + 100)-(x3 + 100, y3 + 100)
  80.         LINE (x1 + 100, y1 + 100)-(x(imin1) + 100, y(imin1) + 100)
  81.         LINE (x1 + 100, y1 + 100)-(x(imin2) + 100, y(imin2) + 100)
  82.         LINE (x2 + 100, y2 + 100)-(x(imin3) + 100, y(imin3) + 100)
  83.         LINE (x2 + 100, y2 + 100)-(x(imin4) + 100, y(imin4) + 100)
  84.         LINE (x3 + 100, y3 + 100)-(x(imin5) + 100, y(imin5) + 100)
  85.         LOCATE 1, 1
  86.         rrr = SQR((x(1) - x(2)) ^ 2 + (y(1) - y(2)) ^ 2)
  87.         PRINT rsummin * 10 / rrr
  88.         tt = TIMER
  89.         WHILE TIMER - tt < .13: WEND
  90.     END IF
  91. LOCATE 3, 1
  92. PRINT "Finished"
  93. xx$ = INPUT$(1)
  94.  
Title: Re: Joining the points of regular polygons
Post by: bplus on February 05, 2020, 04:12:27 pm
Cool! So they are called Steiner trees.

It looks like all the angles out from the Steiner points are 120 degrees of each other. This reminds me of soap bubbles and didn't Steve say something about going around in a C like figure but I was thinking it couldn't be curved so a C shape in straight line segments.

Would it increase code performance if you know in advance the lines out from Steiner points are going to be 120 degrees from each other?
Title: Re: Joining the points of regular polygons
Post by: STxAxTIC on February 05, 2020, 05:50:46 pm
I almost said this last night but backspaced it, but I think a solution can come about intuitively this way: Consider the set of given points as fixed (of course). Now surround the entire thing in a soap bubble (dont hold your breath bolus, this isnt Steve's idea)... Gve the soap bubble a few properties:

1) It cannot cross itself or intersect, but it can lay flat on itself in 2 layers or more
2) its infinitely flexible
3) you can define an energy in terms of how much surface area (so just line length) of soap there is
4) *important* the solution will minimize the energy

If all that's true, then you surround the points in this membrane and hit "go". When it's done cooking, the problem is solved. A solution will look like all points basically circled, but with two layers of the membrane becoming what we will call lines or roads coming from each point.. nodes will automatically form, the 120 degree rule will hold for symmetric clusters and obviously bend for ugly ones.

If this hasn't been worked on by a real mathematician I maaaaaay do it.

Anyone need a picture? (Driving now, itll have to come later.) Oh and if you know math terms, this soap film is *almost* but not really a Gaussian surface.
Title: Re: Joining the points of regular polygons
Post by: _vince on February 09, 2020, 02:09:06 pm
Code: [Select]
deflng a-z
const sw = 800
const sh = 600
dim shared pi as double
pi = 4*atn(1)
declare sub circlef(x, y, r, c)

n = 8
dim x(n), y(n)

'for i=0 to n-1
' x(i) = 200*cos(2*pi*i/n)
' y(i) = 200*sin(2*pi*i/n)
'next

x(0) = 0: y(0) = -200
x(1) = -30: y(1) = -30
x(2) = -200: y(2) = 0
x(3) = -30: y(3) = 30
x(4) = 0: y(4) = 200
x(5) = 30: y(5) = 30
x(6) = 200: y(6) = 0
x(7) = 30: y(7) = -30
x(n) = x(0)
y(n) = y(0)

'screenres sw, sh, 32
screen _newimage(sw, sh, 32)
redraw = -1
drag = 0
do
'm = getmouse(mx, my, mw, mb)
do
mx = _mousex
my = _mousey
mb = -_mousebutton(1)
loop while _mouseinput

if drag then
if mb = 1 then
x(ii) = mx - sw/2
y(ii) = sh/2 - my
else
drag = 0
end if
else
dmin = 1e10
for i=0 to n - 1
dx = (mx - sw/2) - x(i)
dy = (sh/2 - my) - y(i)
d = (dx*dx + dy*dy)
if d < dmin then
dmin = d
ii = i
end if
next

if mb = 1 then
omx = mx
omy = my
drag = -1
end if
end if

redraw = -1

a = 0
cx = 0
cy = 0
for i=0 to n-1
d = x(i)*y(i + 1) - x(i + 1)*y(i)
cx = cx + (x(i) + y(i + 1))*d
cy = cy + (y(i) + y(i + 1))*d
a = a + d
next
cx = cx/(3*a)
cy = cy/(3*a)

if redraw then
'screenlock

line (0,0)-(sw,sh),_rgb(0,0,0),bf
locate 1,1: ? m, mx, my, mw, mb

x(n) = x(0)
y(n) = y(0)
x0 = sw/2 + x(0)
y0 = sh/2 - y(0)
for i=1 to n
x1 = sw/2 + x(i)
y1 = sh/2 - y(i)
line (x0, y0)-(x1, y1)
line -(sw/2 + cx, sh/2 - cy)
circlef x1, y1, 8, _rgb(255,255,255)
x0 = x1
y0 = y1
next
circlef sw/2 + x(ii), sh/2 - y(ii), 8, _rgb(255,0,0)

'screenunlock
'screensync

redraw = 0

_display
end if
loop until _keyhit = 27
system


sub circlef(x, y, r, c)
x0 = r
y0 = 0
e = -r

do while y0 < x0
if e <=0 then
y0 = y0 + 1
line (x - x0, y + y0)-(x + x0, y + y0), c, bf
line (x - x0, y - y0)-(x + x0, y - y0), c, bf
e = e + 2*y0
else
line (x - y0, y - x0)-(x + y0, y - x0), c, bf
line (x - y0, y + x0)-(x + y0, y + x0), c, bf
x0 = x0 - 1
e = e - 2*x0
end if
loop
line (x - r, y)-(x + r, y), c, bf
end sub
Title: Re: Joining the points of regular polygons
Post by: TempodiBasic on February 10, 2020, 09:18:14 am
Hi Vince

Cool!
Is it a porting from Freebasic?