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 20203 days, 12 hours, 5 minutes ago.