Numba QuadTree WIP

nb_qtree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import numba\n",
    "from numba import float64, uint8, deferred_type, types, typed, optional\n",
    "from numba.extending import overload_method, overload\n",
    "from numba.experimental import jitclass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define QuadTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "@jitclass([('x', float64), ('y', float64)])\n",
    "class Point(object):\n",
    "    \"\"\"Point object defined by (x,y)\"\"\"\n",
    "\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        \n",
    "point_type = Point.class_type.instance_type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "@jitclass([('center', Point.class_type.instance_type), ('w', float64)])\n",
    "class BoundingBox(object):\n",
    "    \"\"\"Boundingbox object, defined by a center (Point) and a half-width\"\"\"\n",
    "    \n",
    "    def __init__(self, center, w):\n",
    "        self.center = center\n",
    "        self.w = w\n",
    "        \n",
    "    def contains(self, p):\n",
    "        \n",
    "        ulx = self.center.x - self.w\n",
    "        lrx = self.center.x + self.w\n",
    "        uly = self.center.y - self.w\n",
    "        lry = self.center.y + self.w\n",
    "        \n",
    "        return (ulx < p.x) & (p.x <= lrx) & (uly < p.y) & (p.y <= lry)\n",
    "\n",
    "    def intersects(self, other):\n",
    "        pass\n",
    "    \n",
    "bbox_type = BoundingBox.class_type.instance_type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "quadtree_type = deferred_type()\n",
    "dict_type = types.DictType(types.string, quadtree_type)\n",
    "\n",
    "@jitclass([\n",
    "    ('bbox', bbox_type), \n",
    "    ('max_capacity', uint8),\n",
    "    ('points', types.ListType(point_type)),\n",
    "    ('northwest', optional(quadtree_type)),\n",
    "    ('northeast', optional(quadtree_type)),\n",
    "    ('southwest', optional(quadtree_type)),\n",
    "    ('southeast', optional(quadtree_type)),\n",
    "])\n",
    "class QuadTree(object):\n",
    "\n",
    "    # Based on:\n",
    "    # https://en.wikipedia.org/wiki/Quadtree#Pseudocode\n",
    "    def __init__(self, bbox, max_capacity):\n",
    "        \n",
    "        self.max_capacity = max_capacity\n",
    "        self.bbox = bbox\n",
    "        self.points = typed.List.empty_list(point_type)\n",
    "\n",
    "        self.northwest = None\n",
    "        self.northeast = None\n",
    "        self.southwest = None\n",
    "        self.southeast = None\n",
    "\n",
    "    def subdivide(self):\n",
    "        \n",
    "        w = self.bbox.w / 2        \n",
    "        bbox_nw = BoundingBox(Point(self.bbox.center.x - w, self.bbox.center.y - w), w)\n",
    "        bbox_ne = BoundingBox(Point(self.bbox.center.x + w, self.bbox.center.y - w), w)\n",
    "        bbox_sw = BoundingBox(Point(self.bbox.center.x - w, self.bbox.center.y + w), w)\n",
    "        bbox_se = BoundingBox(Point(self.bbox.center.x + w, self.bbox.center.y + w), w)       \n",
    "        \n",
    "        # need to create new object from overloaded methods (??)\n",
    "        # https://github.com/numba/numba/issues/6032#issuecomment-674840597\n",
    "        self.northwest = self.new_quadtree(bbox_nw, self.max_capacity)\n",
    "        self.northeast = self.new_quadtree(bbox_ne, self.max_capacity)\n",
    "        self.southwest = self.new_quadtree(bbox_sw, self.max_capacity)\n",
    "        self.southeast = self.new_quadtree(bbox_se, self.max_capacity)\n",
    "        \n",
    "    def insert(self, p):\n",
    "        \n",
    "        if not self.bbox.contains(p):\n",
    "            return False\n",
    "        \n",
    "        if len(self.points) < self.max_capacity:\n",
    "            self.points.append(p)\n",
    "            return True\n",
    "        else:\n",
    "            \n",
    "            if self.northeast is None:\n",
    "                self.subdivide()\n",
    "\n",
    "            # check shouldn't add anything after .subdivide()\n",
    "            # it should always be an instance of QuadTree\n",
    "            if self.northeast is not None:\n",
    "                if self.northwest.insert(p):\n",
    "                    return True\n",
    "                \n",
    "#             if self.northeast.insert(p):\n",
    "#                 return True\n",
    "#             if self.southwest.insert(p):\n",
    "#                 return True\n",
    "#             if self.southeast.insert(p):\n",
    "#                 return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "quadtree_type.define(QuadTree.class_type.instance_type)\n",
    "\n",
    "@overload_method(types.misc.ClassInstanceType, 'new_quadtree')\n",
    "def ol_quadtree_new_quadtree(inst, bbox, max_capacity):\n",
    "    if inst is QuadTree.class_type.instance_type:\n",
    "        def impl(inst, bbox, max_capacity):\n",
    "            return QuadTree(bbox, max_capacity)\n",
    "        return impl\n",
    "        \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypingError",
     "evalue": "Failed in nopython mode pipeline (step: nopython frontend)\n\u001b[1m\u001b[1m\u001b[1m\u001b[1m- Resolution failure for literal arguments:\n\u001b[1mFailed in nopython mode pipeline (step: nopython frontend)\n\u001b[1m\u001b[1m\u001b[1m\u001b[1m- Resolution failure for literal arguments:\n\u001b[1mFailed in nopython mode pipeline (step: nopython frontend)\ncompiler re-entrant to the same function signature\u001b[0m\n\u001b[0m\u001b[1m- Resolution failure for non-literal arguments:\n\u001b[1mNone\u001b[0m\n\u001b[0m\u001b[0m\n\u001b[0m\u001b[1mDuring: resolving callee type: BoundFunction((<class 'numba.core.types.misc.ClassInstanceType'>, 'insert') for instance.jitclass.QuadTree#22447fa0ac8<bbox:instance.jitclass.BoundingBox#224460e2a88<center:instance.jitclass.Point#224460e7288<x:float64,y:float64>,w:float64>,max_capacity:uint8,points:ListType[instance.jitclass.Point#224460e7288<x:float64,y:float64>],northwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',northeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None'>)\u001b[0m\n\u001b[0m\u001b[1mDuring: typing of call at <ipython-input-9-ddc08fe14636> (59)\n\u001b[0m\n\u001b[1m\nFile \"<ipython-input-9-ddc08fe14636>\", line 59:\u001b[0m\n\u001b[1m    def insert(self, p):\n        <source elided>\n            if self.northeast is not None:\n\u001b[1m                if self.northwest.insert(p):\n\u001b[0m                \u001b[1m^\u001b[0m\u001b[0m\n\u001b[0m\n\u001b[0m\u001b[1m- Resolution failure for non-literal arguments:\n\u001b[1mNone\u001b[0m\n\u001b[0m\u001b[0m\n\u001b[0m\u001b[1mDuring: resolving callee type: BoundFunction((<class 'numba.core.types.misc.ClassInstanceType'>, 'insert') for instance.jitclass.QuadTree#22447fa0ac8<bbox:instance.jitclass.BoundingBox#224460e2a88<center:instance.jitclass.Point#224460e7288<x:float64,y:float64>,w:float64>,max_capacity:uint8,points:ListType[instance.jitclass.Point#224460e7288<x:float64,y:float64>],northwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',northeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None'>)\u001b[0m\n\u001b[0m\u001b[1mDuring: typing of call at <string> (3)\n\u001b[0m\n\u001b[1m\nFile \"<string>\", line 3:\u001b[0m\n\u001b[1m<source missing, REPL/exec in use?>\u001b[0m\n",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypingError\u001b[0m                               Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-10-d535b1335881>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[0mtree\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mQuadTree\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mbbox_init\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m4\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m \u001b[0mtree\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0minsert\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mPoint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0.1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m0.1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32mC:\\Miniconda3\\envs\\py38\\lib\\site-packages\\numba\\experimental\\jitclass\\boxing.py\u001b[0m in \u001b[0;36mwrapper\u001b[1;34m(*args, **kwargs)\u001b[0m\n\u001b[0;32m     58\u001b[0m     \u001b[1;33m@\u001b[0m\u001b[0mwraps\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfunc\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     59\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mwrapper\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 60\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0mmethod\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m**\u001b[0m\u001b[0mkwargs\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     61\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     62\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mwrapper\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Miniconda3\\envs\\py38\\lib\\site-packages\\numba\\core\\dispatcher.py\u001b[0m in \u001b[0;36m_compile_for_args\u001b[1;34m(self, *args, **kws)\u001b[0m\n\u001b[0;32m    413\u001b[0m                 \u001b[0me\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mpatch_message\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmsg\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    414\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 415\u001b[1;33m             \u001b[0merror_rewrite\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0me\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m'typing'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    416\u001b[0m         \u001b[1;32mexcept\u001b[0m \u001b[0merrors\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mUnsupportedError\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    417\u001b[0m             \u001b[1;31m# Something unsupported is present in the user code, add help info\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Miniconda3\\envs\\py38\\lib\\site-packages\\numba\\core\\dispatcher.py\u001b[0m in \u001b[0;36merror_rewrite\u001b[1;34m(e, issue_type)\u001b[0m\n\u001b[0;32m    356\u001b[0m                 \u001b[1;32mraise\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    357\u001b[0m             \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 358\u001b[1;33m                 \u001b[0mreraise\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtype\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0me\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    359\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    360\u001b[0m         \u001b[0margtypes\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Miniconda3\\envs\\py38\\lib\\site-packages\\numba\\core\\utils.py\u001b[0m in \u001b[0;36mreraise\u001b[1;34m(tp, value, tb)\u001b[0m\n\u001b[0;32m     78\u001b[0m         \u001b[0mvalue\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mtp\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     79\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mvalue\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__traceback__\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mtb\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 80\u001b[1;33m         \u001b[1;32mraise\u001b[0m \u001b[0mvalue\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mwith_traceback\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     81\u001b[0m     \u001b[1;32mraise\u001b[0m \u001b[0mvalue\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     82\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypingError\u001b[0m: Failed in nopython mode pipeline (step: nopython frontend)\n\u001b[1m\u001b[1m\u001b[1m\u001b[1m- Resolution failure for literal arguments:\n\u001b[1mFailed in nopython mode pipeline (step: nopython frontend)\n\u001b[1m\u001b[1m\u001b[1m\u001b[1m- Resolution failure for literal arguments:\n\u001b[1mFailed in nopython mode pipeline (step: nopython frontend)\ncompiler re-entrant to the same function signature\u001b[0m\n\u001b[0m\u001b[1m- Resolution failure for non-literal arguments:\n\u001b[1mNone\u001b[0m\n\u001b[0m\u001b[0m\n\u001b[0m\u001b[1mDuring: resolving callee type: BoundFunction((<class 'numba.core.types.misc.ClassInstanceType'>, 'insert') for instance.jitclass.QuadTree#22447fa0ac8<bbox:instance.jitclass.BoundingBox#224460e2a88<center:instance.jitclass.Point#224460e7288<x:float64,y:float64>,w:float64>,max_capacity:uint8,points:ListType[instance.jitclass.Point#224460e7288<x:float64,y:float64>],northwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',northeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None'>)\u001b[0m\n\u001b[0m\u001b[1mDuring: typing of call at <ipython-input-9-ddc08fe14636> (59)\n\u001b[0m\n\u001b[1m\nFile \"<ipython-input-9-ddc08fe14636>\", line 59:\u001b[0m\n\u001b[1m    def insert(self, p):\n        <source elided>\n            if self.northeast is not None:\n\u001b[1m                if self.northwest.insert(p):\n\u001b[0m                \u001b[1m^\u001b[0m\u001b[0m\n\u001b[0m\n\u001b[0m\u001b[1m- Resolution failure for non-literal arguments:\n\u001b[1mNone\u001b[0m\n\u001b[0m\u001b[0m\n\u001b[0m\u001b[1mDuring: resolving callee type: BoundFunction((<class 'numba.core.types.misc.ClassInstanceType'>, 'insert') for instance.jitclass.QuadTree#22447fa0ac8<bbox:instance.jitclass.BoundingBox#224460e2a88<center:instance.jitclass.Point#224460e7288<x:float64,y:float64>,w:float64>,max_capacity:uint8,points:ListType[instance.jitclass.Point#224460e7288<x:float64,y:float64>],northwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',northeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southwest:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None',southeast:OptionalType(DeferredType#2354848956552) i.e. the type 'DeferredType#2354848956552 or None'>)\u001b[0m\n\u001b[0m\u001b[1mDuring: typing of call at <string> (3)\n\u001b[0m\n\u001b[1m\nFile \"<string>\", line 3:\u001b[0m\n\u001b[1m<source missing, REPL/exec in use?>\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "bbox_init = BoundingBox(Point(0.5, 0.5), 0.5)\n",
    "\n",
    "tree = QuadTree(bbox_init, 4)\n",
    "\n",
    "tree.insert(Point(0.1, 0.1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# manually insert some points, this currently makes points in \"full\" trees \n",
    "# just disapear instead of propagate into subtrees\n",
    "\n",
    "# it does show that creating the nested QuadTrees works\n",
    "\n",
    "for i in range(50):\n",
    "    p = Point(np.random.rand(), np.random.rand())\n",
    "    tree.insert(p)\n",
    "\n",
    "for i in range(50):\n",
    "    p = Point(np.random.rand(), np.random.rand())\n",
    "    tree.northwest.insert(p)\n",
    "    tree.northeast.insert(p)\n",
    "    tree.southwest.insert(p)\n",
    "    tree.southeast.insert(p)\n",
    "\n",
    "for i in range(50):\n",
    "    p = Point(np.random.rand(), np.random.rand())\n",
    "    tree.northwest.northwest.insert(p)\n",
    "    tree.northeast.northeast.insert(p)\n",
    "    tree.southwest.southwest.insert(p)\n",
    "    tree.southeast.southeast.insert(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Display result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root -> northwest -> northwest 4\n",
      "root -> northwest -> northeast 0\n",
      "root -> northwest -> southwest 0\n",
      "root -> northwest -> southeast 0\n",
      "root -> northwest 4\n",
      "root -> northeast -> northwest 0\n",
      "root -> northeast -> northeast -> northwest 0\n",
      "root -> northeast -> northeast -> northeast 0\n",
      "root -> northeast -> northeast -> southwest 0\n",
      "root -> northeast -> northeast -> southeast 0\n",
      "root -> northeast -> northeast 4\n",
      "root -> northeast -> southwest 0\n",
      "root -> northeast -> southeast 0\n",
      "root -> northeast 4\n",
      "root -> southwest -> northwest 0\n",
      "root -> southwest -> northeast 0\n",
      "root -> southwest -> southwest 3\n",
      "root -> southwest -> southeast 0\n",
      "root -> southwest 4\n",
      "root -> southeast -> northwest 0\n",
      "root -> southeast -> northeast 0\n",
      "root -> southeast -> southwest 0\n",
      "root -> southeast -> southeast 3\n",
      "root -> southeast 4\n",
      "root 4\n"
     ]
    }
   ],
   "source": [
    "# after uncommenting the line generating the issue the rest seems to work\n",
    "def traverse_tree(trail, tree):\n",
    "    \n",
    "    for branch in ['northwest', 'northeast', 'southwest', 'southeast']:\n",
    "        \n",
    "        subtree = getattr(tree, branch, None)\n",
    "\n",
    "        if subtree:\n",
    "            yield from traverse_tree(trail + f' -> {branch}', subtree)\n",
    "        \n",
    "    yield trail, tree\n",
    "    \n",
    "    \n",
    "for trail, subtree in traverse_tree('root', tree):\n",
    "    print(trail, len(subtree.points))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}