25
我在Mathematica中实现了一个quadtree。我是用Mathematica等函数式编程语言进行编码的新手，我想知道是否可以通过更好地使用模式来改进它或使其更加紧凑。在Mathematica中实现四叉树
（据我所知，我也许可以通过修剪未使用的节点优化树，并有可能会像对空间分解KD树更好的数据结构。）
而且，我仍然不舒服复制的想法每次添加新点时，整个树/表达式。但我的理解是，对整个表达式进行操作而不修改这些部分是功能性编程方式。我很感谢在这方面的任何澄清。
MV
守则
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]] <= bb[[2, 1]]) && (pt[[1]] >= bb[[1, 1]]) &&
(pt[[2]] <= bb[[2, 2]]) && (pt[[2]] >= 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 @@((# == {})& /@ 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 @@ ((# == {})& /@ cNodes),
(* compute child node bounds *)
(* create child nodes with above bounds*)
cNodes = qtMakeNode[#]& /@ splitBox[List @@ qtree[[5]]];
];
(* move curr node pt (if not empty) into child *)
currPt = List @@ qtree[[6]];
If[currPt != {},
cNodes = qtInsert[#, currPt]& /@ cNodes;
];
(* insert new pt into child *)
cNodes = qtInsert[#, pt]& /@ 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 :> List;
bboxes = Cases[qt, _qtbb, Infinity] /. qtbb :> List;
Graphics[{
EdgeForm[Black],Hue[0.2], Map[Disk[#, 0.01]&, pts],
Hue[0.7],EdgeForm[Red], FaceForm[],(Rectangle @@ #) & /@ bboxes
},
Frame->True
]
]
使用
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]
输出
我没有时间与你的代码的发挥，但在应对，” ......我仍然不满意每次添加新点时复制整个树/表达式的想法...'---您是否正在寻找一种方法为您的函数添加内存？如果是这样，搜索'记住他们的价值的功能'。如果不是你要找的东西，无视，今天晚些时候我会玩。看起来不错。 :) – telefunkenvf14
不，我的意思是，当我添加一个点时，而不是将节点插入到退出的树中，实际上，我们正在生成一个新的树，丢弃旧的树。我只是想知道这种内存管理的含义，当这些表达式真的很大。很难摆脱C++的心态！ ;-） 谢谢。 –
如果我正确理解你，你想通过引用传递，因为你不喜欢'qtInsert'中的'Return'行来创建一个新的嵌套列表（可能）巨大的旧树和少量新节点。Mathematica中有一种方法可以用'Attributes [qtInsert] = HoldAll;'来做这样的事情，其缺点是'qtInsert'的所有参数必须是变量，而不是文字值。 – bbtrb