Results 1 to 5 of 5

Thread: Generating rectangles around a centre point in a spiral starting from the centre

  1. #1

    Thread Starter
    Frenzied Member Icyculyr's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    1,934

    Generating rectangles around a centre point in a spiral starting from the centre

    Ehh, it's been a while since I've been on VBForums. Feels a little nostalgic

    Anyway I have a central point (40x40 pixel rectangle) and I want to generate (40x40 pixel) rectangles around it in a spiral, starting from the centre.
    The quantity is variable. If 0,0 is the centre point, I want to create rectangles like so:

    Code:
    0,1 >>> 1,1 >>> 1,0 >>> 1,-1 >>> 0,-1 >>> -1,-1 >>> -1,0 >>> -1,1 >>> -1, 2 >>> 0,2 >>> 1,2 >>> 2,2 >>> 2,1
    And I want them to continue around that centre point, in that pattern. For reference, 0,1 is up one square and 1,1 is to the right of 0,1.
    I don't need to know this, I'm going to hardcode it as I only need at the very most 40 of these... however it's piqued my curiosity.

    I would give an example of what I'm capable of so far... but that'd get me as far as the for loop and an x and y variable which can't be that helpful

    Anyone have any idea about this?

  2. #2
    Hyperactive Member Lenggries's Avatar
    Join Date
    Sep 2009
    Posts
    353

    Re: Generating rectangles around a centre point in a spiral starting from the centre

    I would say that hardcoding is the worst way to implement this, so your question here is well worth asking.

    There are two general approaches you could take to compute all the coordinates:
    1: Iterative: Basically, start with (0,0), and iterate from 1 to 402. Whenever Abs(x) = Abs(y), take a right turn somehow.
    2: Formulaic: Write functions that solve for x and y based on which step you are on. For example (using VB6 code):

    Code:
    lngRange = 40
    For n = 0 to lngRange * lngRange - 1
       x = GetX(n)
       y = GetY(n)
       Call Plot(x,y)
    Next n
    GetX() and GetY() are fairly simple formulas, but deriving them is no trivial task. For kicks I derived GetY() for you... I'll leave it to you if you want to figure out GetX() for yourself:
    Code:
    Private Function GetY(n as Long) As Long
       Dim a As Long, b As Long, c As Long, d As Long, e As Long, y As Long
    
       a = Floor(Sqr(n)/2)   'In VB6, Sqr() returns the square root of a number, not the square
       b = n - 4 * a * a
       c = 2 * a + 1
       d = Floor(b / c)
       e = (b - 1) Mod c
    
       If d = 0 Then
          y = -a
       ElseIf d = 1 Then
          y = 1 + e - a
       ElseIf d = 2 Then
          y = 1 + a
       Else
          y = c - e - a - 1
       End If
    
       GetY = y
    End Function
    The advantage of the iterative method is that it will solve the whole range of value faster. The advantage of the formulaic method is that you can solve any point directly without having to first solve all previous points, which gives you far more flexibility in how you deal with this problem. Unless speed is of the essence, I'd go with the formulaic method if you have the ability to derive the necessary formulas.

  3. #3

    Thread Starter
    Frenzied Member Icyculyr's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    1,934

    Re: Generating rectangles around a centre point in a spiral starting from the centre

    Ah I see I see. I appreciate the response. This will be handy. Thanks!

  4. #4
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Generating rectangles around a centre point in a spiral starting from the centre

    For what it's worth, here's a brief discussion of what Lenggries called "GetX/GetY".

    Divide the plane into rectangular strips: the 0th is just (0, 0); the 1st is (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, -1); the nth is all (x, y) with max(|x|, |y|) = n. The strips have edges with 1, 3, 5, ..., 2n+1, ... boxes; for n>0, quadruple this and subtract 4 to get the number of boxes in the whole strip, giving 8n boxes per strip (and 1 box for n=0). The number of boxes before the Nth strip (for N>0) is then

    1+8+16+...+8(N-1)
    = 1 + 8(1+2+...+ N-1)
    = 1 + 8(N)(N-1)/2
    = 1 - 4N + 4N^2
    = (2N-1)^2

    (Eg. N=1 gives 1; N=2 gives 9; N=3 gives 25; etc.)

    Suppose we want to find the mth box. It belongs to the Nth strip, where there are (2N-1)^2 < m for N as large as possible, i.e.

    (2N-1)^2 <= m-1
    2N-1 <= sqrt(m-1)
    N <= (sqrt(m-1)+1)/2

    By definition, N = floor((sqrt(m-1)+1)/2). Now index the boxes in the Nth strip starting from 0 in the upper left corner, going clockwise. m - (2N-1)^2 gives the index of our box using this scheme. Note that indexes 0 to 2N; 2N to 4N; 4N to 6N; 6N to 8N are on the top; right; bottom; left edges, respectively. In all, we have the following Python (even if you don't know Python, it should be easy to read):

    Code:
    from math import sqrt
    def GetPos(m):
      N = int((sqrt(m-1)+1)/2)     # int does the same thing as floor, here
      i = m - (2*N-1)**2             # ** means exponentiation
      if i <= 2*N: return (i-N, N)
      if i <= 4*N: return (N, 3*N-i)
      if i <= 6*N: return (5*N-i, -N)
      if i <= 8*N: return (-N, i-7*N)
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  5. #5

    Thread Starter
    Frenzied Member Icyculyr's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    1,934

    Re: Generating rectangles around a centre point in a spiral starting from the centre

    Ah I see. Thanks for the explanation! Much appreciated.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width