Databases
StackOverflow2013
Postsdbo
POImplementing a Quadtree in Mathematica
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POImplementing a Quadtree in Mathematica
    text
    copied!<p>I have implemented a <a href="http://en.wikipedia.org/wiki/Quadtree">quadtree</a> in Mathematica. I am new to coding in a functional programming language like Mathematica, and I was wondering if I could improve this or make it more compact by better use of patterns. </p> <p>(I understand that I could perhaps optimize the tree by pruning unused nodes, and there might be better data structures like k-d trees for spatial decomposition.)</p> <p>Also, I am still not comfortable with the idea of copying the entire tree/expression every time a new point is added. But my understanding is that operating on the expression as a whole and not modifying the parts is the functional programming way. I'd appreciate any clarification on this aspect. </p> <p>MV</p> <p>The Code</p> <pre><code>ClearAll[qtMakeNode, qtInsert, insideBox, qtDraw, splitBox, isLeaf, qtbb, qtpt]; (* create a quadtree node *) qtMakeNode[{{xmin_,ymin_}, {xmax_, ymax_}}] := {{}, {}, {}, {}, qtbb[{xmin, ymin}, {xmax, ymax}], {}} (* is pt inside box? *) insideBox[pt_, bb_] := If[(pt[[1]] &lt;= bb[[2, 1]]) &amp;&amp; (pt[[1]] &gt;= bb[[1, 1]]) &amp;&amp; (pt[[2]] &lt;= bb[[2, 2]]) &amp;&amp; (pt[[2]] &gt;= bb[[1, 2]]), True, False] (* split bounding box into 4 children *) splitBox[{{xmin_,ymin_}, {xmax_, ymax_}}] := { {{xmin, (ymin+ymax)/2}, {(xmin+xmax)/2, ymax}}, {{xmin, ymin},{(xmin+xmax)/2,(ymin+ymax)/2}}, {{(xmin+xmax)/2, ymin},{xmax, (ymin+ymax)/2}}, {{(xmin+xmax)/2, (ymin+ymax)/2},{xmax, ymax}} } (* is node a leaf? *) isLeaf[qt_] := If[ And @@((# == {})&amp; /@ Join[qt[[1;;4]], {List @@ qt[[6]]}]),True, False] (*--- insert methods ---*) (* qtInsert #1 - return input if pt is out of bounds *) qtInsert[qtree_, pt_] /; !insideBox[pt, List @@ qtree[[5]]]:= qtree (* qtInsert #2 - if leaf, just add pt to node *) qtInsert[qtree_, pt_] /; isLeaf[qtree] := {qtree[[1]],qtree[[2]],qtree[[3]],qtree[[4]],qtree[[5]], qtpt @@ pt} (* qtInsert #3 - recursively insert pt *) qtInsert[qtree_, pt_] := Module[{cNodes, currPt}, cNodes = qtree[[1;;4]]; (* child nodes not created? *) If[And @@ ((# == {})&amp; /@ cNodes), (* compute child node bounds *) (* create child nodes with above bounds*) cNodes = qtMakeNode[#]&amp; /@ splitBox[List @@ qtree[[5]]]; ]; (* move curr node pt (if not empty) into child *) currPt = List @@ qtree[[6]]; If[currPt != {}, cNodes = qtInsert[#, currPt]&amp; /@ cNodes; ]; (* insert new pt into child *) cNodes = qtInsert[#, pt]&amp; /@ cNodes; (* return new quadtree *) {cNodes[[1]],cNodes[[2]], cNodes[[3]], cNodes[[4]], qtree[[5]], {}} ] (* draw quadtree *) qtDraw[qt_] := Module[{pts, bboxes}, pts = Cases[qt, _qtpt, Infinity] /. qtpt :&gt; List; bboxes = Cases[qt, _qtbb, Infinity] /. qtbb :&gt; List; Graphics[{ EdgeForm[Black],Hue[0.2], Map[Disk[#, 0.01]&amp;, pts], Hue[0.7],EdgeForm[Red], FaceForm[],(Rectangle @@ #) &amp; /@ bboxes }, Frame-&gt;True ] ] </code></pre> <p>Usage </p> <pre><code>Clear[qt]; len = 50; pts = RandomReal[{0, 2}, {len, 2}]; qt = qtMakeNode[{{0.0, 0.0}, {2.0, 2.0}}]; Do[qt = qtInsert[qt, pts[[i]]], {i, 1, len}] qtDraw[qt] </code></pre> <p>Output</p> <p><img src="https://i.stack.imgur.com/J0QB0.png" alt="enter image description here"></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload