extra/quadtrees/quadtrees-docs.factor

   1 USING: arrays help.markup help.syntax math.rectangles quadtrees quotations sequences ;
   2 IN: quadtrees
   3
   4 ARTICLE: "quadtrees" "Quadtrees"
   5 "The " { $snippet "quadtrees" } " vocabulary implements the quadtree data structure in Factor."
   6 { $subsections <quadtree> }
   7 "Quadtrees follow the " { $link "assocs-protocol" } " for insertion, deletion, and querying of exact points, using two-dimensional vectors as keys. Additional words are provided for spatial queries and pruning the tree structure:"
   8 { $subsections
   9     in-rect
  10     prune-quadtree
  11 }
  12 "The following words are provided to help write quadtree algorithms:"
  13 { $subsections
  14     descend
  15     each-quadrant
  16     map-quadrant
  17 }
  18 "Quadtrees can be used to \"swizzle\" a sequence to improve the locality of spatial data in memory:"
  19 { $subsections swizzle } ;
  20
  21 ABOUT: "quadtrees"
  22
  23 HELP: <quadtree>
  24 { $values { "bounds" rect } { "quadtree" quadtree } }
  25 { $description "Constructs an empty quadtree covering the axis-aligned rectangle indicated by " { $snippet "bounds" } ". All the keys of " { $snippet "quadtree" } " must be two-dimensional vectors lying inside " { $snippet "bounds" } "." } ;
  26
  27 HELP: prune-quadtree
  28 { $values { "tree" quadtree } }
  29 { $description "Removes empty nodes from " { $snippet "tree" } "." } ;
  30
  31 HELP: in-rect
  32 { $values { "tree" quadtree } { "rect" rect } { "values" sequence } }
  33 { $description "Returns a " { $link sequence } " of values from " { $snippet "tree" } " whose keys lie inside " { $snippet "rect" } "." } ;
  34
  35 HELP: descend
  36 { $values { "pt" sequence } { "node" quadtree } { "subnode" quadtree } }
  37 { $description "Descends into the subnode of quadtree node " { $snippet "node" } " that contains " { $snippet "pt" } ", leaving " { $snippet "pt" } " on the stack." } ;
  38
  39 HELP: each-quadrant
  40 { $values { "node" quadtree } { "quot" quotation } }
  41 { $description "Calls " { $snippet "quot" } " with each subnode of " { $snippet "node" } " on the top of the stack in turn." } ;
  42
  43 HELP: map-quadrant
  44 { $values { "node" quadtree } { "quot" quotation } { "array" array } }
  45 { $description "Calls " { $snippet "quot" } " with each subnode of " { $snippet "node" } " on the top of the stack in turn, collecting the four results into " { $snippet "array" } "." } ;
  46
  47 HELP: swizzle
  48 { $values { "sequence" sequence } { "quot" quotation } { "sequence'" sequence } }
  49 { $description "Swizzles " { $snippet "sequence" } " based on the two-dimensional vector values returned by calling " { $snippet "quot" } " on each element of " { $snippet "sequence" } "." } ;