Poisson Disc Growth Tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import numpy as np\n",
    "np.seterr(divide='ignore', invalid='ignore')\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "def GetColour(level, max_level):\n",
    "    return [0,0,0]\n",
    "    #cmap = plt.get_cmap()\n",
    "    #return cmap(int((level / max_level) * 255))\n",
    "\n",
    "def GenerateTree(start_point, radius, num_proposals, max_level):\n",
    "    \n",
    "    cellsize    = radius / np.sqrt(2)\n",
    "\n",
    "    grid_width  = int(np.ceil(1 / cellsize))\n",
    "    grid_height = int(np.ceil(1 / cellsize))\n",
    "    grid        = [None] * (grid_width * grid_height)\n",
    "\n",
    "    def distance(a, b):\n",
    "        dx = a[0] - b[0]\n",
    "        dy = a[1] - b[1]\n",
    "        return np.sqrt(dx * dx + dy * dy)\n",
    "    \n",
    "    def grid_coords(p):\n",
    "        return int(np.floor(p[0] / cellsize)), int(np.floor(p[1] / cellsize))\n",
    "\n",
    "    def fits(p, gx, gy):\n",
    "        xrange = range(max(gx - 2, 0), min(gx + 3, grid_width ))\n",
    "        yrange = range(max(gy - 2, 0), min(gy + 3, grid_height))\n",
    "        \n",
    "        for x in xrange:\n",
    "            for y in yrange:\n",
    "                \n",
    "                g = grid[x + y * grid_width]\n",
    "                if g is None:\n",
    "                    continue\n",
    "                if distance(p, g) <= radius:\n",
    "                    return False\n",
    "        return True\n",
    "    \n",
    "    active   = [(None, 0, start_point)]\n",
    "    accepted = [(start_point, [])] \n",
    "    \n",
    "    grid_x, grid_y = grid_coords(start_point)\n",
    "    grid[grid_x + grid_y * grid_width] = start_point\n",
    "    \n",
    "    while (len(active) > 0):\n",
    "        \n",
    "        current = active[0]\n",
    "        active  = active[1:]\n",
    "        \n",
    "        parent_idx, level, point = current\n",
    "            \n",
    "        current_idx = len(accepted)\n",
    "        \n",
    "        new_node = (point, [])\n",
    "        accepted.append(new_node)\n",
    "        \n",
    "        if (parent_idx is not None):\n",
    "            parent_point, _ = accepted[parent_idx]\n",
    "            \n",
    "            plt.plot([point[0], parent_point[0]], [point[1], parent_point[1]], '-', color=GetColour(level, max_level))\n",
    "            \n",
    "            accepted[parent_idx][1].append(new_node)\n",
    "        \n",
    "        if (level >= max_level): continue\n",
    "    \n",
    "        proposals = MakeProposals(point, radius, num_proposals)\n",
    "        \n",
    "        for i in range(num_proposals):\n",
    "            \n",
    "            # Test proposal\n",
    "            if not (0 <= proposals[i][0] < 1 and 0 <= proposals[i][1] < 1): continue\n",
    "            grid_x, grid_y = grid_coords(proposals[i])\n",
    "            if not fits(proposals[i], grid_x, grid_y): continue\n",
    "            grid[grid_x + grid_y * grid_width] = proposals[i]\n",
    "            \n",
    "            # Add to queue\n",
    "            active.append((current_idx, level+1, proposals[i]))\n",
    "            \n",
    "    return accepted[0]\n",
    "\n",
    "def PlotTree(root, level, max_level):\n",
    "    \n",
    "    print('level', level)\n",
    "    \n",
    "    parent_point, children = root    \n",
    "    for node in children:\n",
    "        point, _ = node\n",
    "        plt.plot([point[0], parent_point[0]], [point[1], parent_point[1]], '-', color=GetColour(level, max_level))\n",
    "        PlotTree(node, level+1, max_level)\n",
    "    \n",
    "def MakeProposals(point, radius, num_proposals):\n",
    "    ang      = np.random.uniform(low=0,      high=np.pi*2,     size=(num_proposals,))\n",
    "    rad      = np.random.uniform(low=radius, high=radius*1.25, size=(num_proposals,))\n",
    "    \n",
    "    pos      = np.empty((num_proposals, 2))\n",
    "    pos[:,0] = point[0] + np.cos(ang) * rad\n",
    "    pos[:,1] = point[1] + np.sin(ang) * rad\n",
    "    \n",
    "    return pos\n",
    "\n",
    "def PlotCircle(point, radius):\n",
    "    ang = np.linspace(0,2*np.pi,100)\n",
    "    x   = point[0] + (np.cos(ang) * radius)\n",
    "    y   = point[1] + (np.sin(ang) * radius)\n",
    "    plt.plot(x,y,'-o', color='black')\n",
    "    \n",
    "def CheckPoint(point, radius, accepted):\n",
    "    for i in range(len(accepted)):\n",
    "        if (np.sqrt(np.sum(np.square(point - accepted[i][2]))) <= radius):\n",
    "            return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "figw   = 2**12\n",
    "figh   = 2**12\n",
    "figdpi = 100\n",
    "fig    = plt.figure(facecolor='white', figsize=(figw/figdpi, figh/figdpi), dpi=figdpi)\n",
    "\n",
    "max_level = 100\n",
    "\n",
    "plt.axis('off')\n",
    "\n",
    "tree = GenerateTree([0.5, 0.5], 0.0001, 20, max_level)\n",
    "\n",
    "#PlotTree(tree, 0, max_level)\n",
    "\n",
    "plt.savefig(\"poisson.png\")\n",
    "plt.show()"
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}