quadtree.frink

Download or view quadtree.frink in plain text format



class Quadtree
{
   var left
   var right
   var top
   var bottom

   var data
   
   // An array of children
   var children
   
   // Construct a new Quadtree node.
   new[l, r, b, t] :=
   {
      left = l
      right = r
      top = t
      bottom = b

      children = undef
      data = undef
   }

   // Creates a child to go at the specified row and column.  Returns the
   // new child.
   createChild[row, column, value] :=
   {
      middle = (left + right) / 2
      if column == 0
      {
         l = left
         r = middle
      } else
      {
         l = middle
         r = right
      }

      middle = (top + bottom) / 2
      if row == 0
      {
         t = top
         b = middle
      } else
      {
         t = middle
         b = bottom
      }

      var child = new Quadtree[l,r,b,t]
      child.data = value

      if children == undef
         children = new array[]
      
      children@(row*2+column) = child    // Attach to tree

      return child
   }

   // Gets the value of the given child.
   getChild[index] :=
   {
      if children == undef
         return undef

      if index >= length[children]
         return undef
      else
         return children@index
   }

   // Gets the value of the given child at the row and column
   getChild[row, column] :=
   {
      getChild[row*2 + column]
   }

   // Deletes all children of the specified node.  The value is the value
   // that should be given to this node.
   deleteChildren[value] :=
   {
      children = undef
      data = value
   }

   // Deletes a single child of the node.  If the deleted node is the last
   // child, then this node takes on the value undef.
   deleteChild[index] :=
   {
      if children == undef
      {
         data = undef
         return
      }

      children@index = undef
      noValue = true
      len = length[children]
      for i = 0 to len-1
         if children@i != undef
            noValue = false

      if (noValue == true)   // Clean up the children array
      {
         data = undef
         children = undef
      }
   }

   // Returns true if this is a leaf node.
   isLeaf[] :=
   {
      if children == undef
         return true

      noValue = true
      len = length[children]
      for i = 0 to len-1
         if children@i != undef
            noValue = false

      return noValue
   }

   // Gets the data for the given node.
   getData[] := data

   // Sets the data for the given node.
   setData[newData] := data = newData

   // Make a Quadtree for the given graph, going to the specified depth.
   class makeQuadtree[l, r, b, t, equation, depth] :=
   {
      var child
      q = new Quadtree[l,r,b,t]
      q.setData["X"]
      q.subdivide[parseToExpression[equation], depth]
      return q
   }

   subdivide[expression, depth] :=
   {
      if (depth > 0 && data)
      {
         hMiddle  = (left + right) / 2
         vMiddle =  (top + bottom) / 2
         
         xs = [new interval[left, hMiddle], new interval[hMiddle, right]]
         ys = [new interval[vMiddle, top], new interval[bottom, vMiddle]]
         index = 0
         solutionFound = false
         for row = 0 to 1
         {
            y = ys@row
            for col = 0 to 1
            {
               index = row*2 + col
               x = xs@col
//               println["$x, $y"]
//             res = eval[equation]
               res = eval[expression]
               val = "X"
               if res or res == undef
               {
                  if res != true
                  {
//                     println[res]
                     val = "!"
                  }
                  v = createChild[row, col, val]
                     
                  solutionFound = true
                  //                  children@index = v
                  data = undef  // Force to be a non-leaf
                  v.subdivide[expression, depth-1]
               }
            }
         }

         if ! solutionFound
            deleteChildren[undef]
      }
   }

   // Plot the graph in text.
   textPlot[rows, cols] :=
   {
      vals = new array[]
      for i = 0 to rows         // One row padding
      {
         vals@i = new array[]
         for j = 0 to cols - 1
            vals@i@j = "."
      }

      xscale = cols / (right-left)
      yscale = rows / (top-bottom)
      privateTextPlot[vals, xscale, yscale, left, bottom]
      for i = rows-1 to 0 step -1
      {
         println[join["",vals@i]]
      }
   }

   // Private text plotter
   privateTextPlot[vals, xscale, yscale, gLeft, gBottom] :=
   {
      for row = 0 to 1
         for col = 0 to 1
         {
            c = getChild[row,col]
            if (c != undef)
            {
               if (c.isLeaf[] and c.data)
               {
                  for y = floor[(c.bottom - gBottom) * yscale] to floor[(c.top-gBottom) * yscale]
                  {
                     rr = vals@y
                     for x = floor[(c.left - gLeft) * xscale] to floor[(c.right-gLeft) * xscale]
                     {
                        rr@x = c.data
                     }
                  }
               } else
               {
                  c.privateTextPlot[vals, xscale, yscale, gLeft, gBottom]
               }
            }
         }
   }
}


n = Quadtree.makeQuadtree[-5, 5, -5, 5,"y PEQ 5 cos[x^2] sin[x]", 6]
//println[n]
n.textPlot[21,76]


Download or view quadtree.frink in plain text format

This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 19981 days, 16 hours, 52 minutes ago.