{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "%matplotlib inline"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Nearest neighbors\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\nfrom scipy import spatial"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Make a grid of 0:9 in X and 0:20 in Y.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "[X, Y] = np.meshgrid(range(0, 10), range(0, 20))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Make one XY array [10*20 x 2] where each line is the x, y position of one point.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "XY = np.vstack([X.flatten(), Y.flatten()]).transpose()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Make the fast search tree.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "kdtree = spatial.cKDTree(XY, leafsize=4)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Choose some random points in the grid and get the 8 nearest neighbours.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "rand = np.random.randint(0, XY.shape[1], size=(20,))\n\nfor r in rand:\n    # random point:\n    point = XY[r, :]\n    # query the 8 nearest neightbours with an euclidian distance\n    [dists, indices] = kdtree.query(point, k=8, p=2)\n    print(\"Nearest points to point:\", point)\n    print(\"------------------------------------------\")\n    for idx in range(0, len(indices)):\n        print(\"    \", idx, \".:\", XY[indices[idx], :], \" -> dist:\", dists[idx])"
      ]
    }
  ],
  "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.8.10"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}