SpatialIndex.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 141,
   "id": "6f802cd1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import OSGridConverter #To convert from =SGB36 to WGS84\n",
    "import pandas as pd #To use pandas for elegant data handling\n",
    "import numpy as np\n",
    "import math\n",
    "\n",
    "class SpatialIndex:\n",
    "    \n",
    "    def __init__(self, resolution):\n",
    "        geograph = pd.read_csv('./data/geograph_mini_corpus.csv', encoding='latin-1')\n",
    "        #First we need to reproject the data so that we have them in the correct projection\n",
    "        \n",
    "        sample = geograph.sample(n = 10000) # For testing\n",
    "        \n",
    "        sample.dropna() # Get rid of problematic rows with nas\n",
    "        \n",
    "        for i in sample.index:\n",
    "            try:\n",
    "                g = OSGridConverter.latlong2grid (sample.at[i, 'lat'], sample.at[i, 'lon'], tag = 'WGS84')\n",
    "                sample.at[i, 'x'] = g.E\n",
    "                sample.at[i, 'y'] = g.N\n",
    "            except ValueError:\n",
    "                #print(\"Problem with a document\", sample.at[i,'id'])\n",
    "                sample = sample.drop(i)\n",
    "\n",
    "        # Now we can set up the parameters for our index        \n",
    "        self.resolution = resolution\n",
    "\n",
    "        self.minx = sample['x'].min()\n",
    "        self.maxx = sample['x'].max()\n",
    "        self.miny = sample['y'].min()\n",
    "        self.maxy = sample['y'].max()\n",
    "\n",
    "        w = self.maxx - self.minx\n",
    "        h = self.maxy - self.miny\n",
    "\n",
    "        nc = int(w/self.resolution) + 1\n",
    "        nr = int(h/self.resolution) + 1\n",
    "\n",
    "        #print(maxx, minx, maxy, miny)\n",
    "        #print(nr, nc)\n",
    "\n",
    "        #Build the spatial index now\n",
    "        self.spatialIndex = pd.DataFrame(index=range(nc),columns=range(nr))\n",
    "\n",
    "        #Now we populate the index with document ids\n",
    "        for index, row in sample.iterrows():\n",
    "            i = int((row['x'] - self.minx)/self.resolution)\n",
    "            j = int((row['y'] - self.miny)/self.resolution)\n",
    "            id = row['id']\n",
    "    \n",
    "            #print(row['id'])\n",
    "            #print(row['x'],row['y'],i,j)\n",
    "            if pd.isnull(self.spatialIndex.at[i,j]):\n",
    "                self.spatialIndex.at[i,j] = {id:(row['x'],row['y'])}\n",
    "            else:\n",
    "                names = self.spatialIndex.at[i,j]\n",
    "                names.update({id:(row['x'],row['y'])})\n",
    "                self.spatialIndex.at[i,j] = names\n",
    "\n",
    "        \n",
    "    def rangeQuery(self, dist, point):\n",
    "        x1 = point[0] - dist/2\n",
    "        x2 = point[0] + dist/2\n",
    "        y1 = point[1] - dist/2\n",
    "        y2 = point[1] + dist/2\n",
    "    \n",
    "        i1 = int((x1 - self.minx)/self.resolution)\n",
    "        j1 = int((y1 - self.miny)/self.resolution)\n",
    "        i2 = int((x2 - self.minx)/self.resolution) + 1\n",
    "        j2 = int((y2 - self.miny)/self.resolution) + 1\n",
    "\n",
    "        # Retrieve only the relevant part of the index\n",
    "        result = self.spatialIndex.iloc[j1:j2, i1:i2]\n",
    "        # Turn the data frame into a 1d list\n",
    "        tlist = result.values.flatten()\n",
    "        # Remove all the nans\n",
    "        filtered = filter(lambda i:not(type(i) is float), tlist)\n",
    "        \n",
    "        #Rank by distance\n",
    "        ranked = []\n",
    "        for item in filtered:\n",
    "            for key in item:\n",
    "                d = si.dist(point, item[key])\n",
    "                #print(key, item[key], dist)\n",
    "                ranked.append((key, d/dist))    \n",
    "        ranked.sort(key = lambda x: x[1]) # Sort by rank - values are normalised between 0 and 1\n",
    "        \n",
    "        return ranked\n",
    "    \n",
    "    def dist(self, p1, p2):\n",
    "        #print(p1[0], p1[1], p2[0], p2[1])\n",
    "        dist = (((p1[0] - p2[0]) ** 2) + ((p1[1] - p2[1]) ** 2)) ** 0.5\n",
    "        #print(dist)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "64ff3577",
   "metadata": {},
   "outputs": [],
   "source": [
    "si = SpatialIndex(10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "c7e38f1c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(468943, 0.5778278117224889), (1438140, 0.5959704238466872), (2314638, 0.6066402970459513), (404569, 0.6074849216235741), (865328, 0.635026023088818), (519511, 0.6553544460824234), (1267123, 0.6687383045706295), (1294612, 0.6837296513242642), (1059608, 0.6845898041893408), (2122130, 0.6870489182729277), (606008, 0.688472294286415), (2483509, 0.6938398230139289), (1200265, 0.7018782501972832), (132974, 0.7025510657596357), (2009756, 0.7026800836796216), (1903705, 0.7034965529410929), (1221696, 0.7079896962527068), (2054653, 0.7117238580376521), (2141139, 0.7123270667326913), (1023817, 0.7127463139855582), (665671, 0.7143261160002482), (2768787, 0.7191507937143643), (509484, 0.7198601253021312), (1286440, 0.7260365594100616), (1268706, 0.7328243241050341), (1935407, 0.7373670185192717), (997474, 0.7374032817936194), (2103754, 0.7510833242723473), (1335030, 0.7515087052722677), (1182903, 0.7524662371827722), (2121508, 0.7594703746690847), (468193, 0.7616308082660522), (2222894, 0.7621458916113107), (1011679, 0.768859404637805), (226519, 0.7693438762997987), (628349, 0.7713479111270088), (169090, 0.7725522636042172), (2119084, 0.7773626245195996), (2121526, 0.7828942445183767), (1571271, 0.7871579892245267), (2425308, 0.7872239643201927), (708764, 0.7876898691744105), (661747, 0.7894303325816662), (2115054, 0.7912398334891894), (646952, 0.7965779936704253), (639304, 0.8002792875615362), (639283, 0.8011114279549382), (1152921, 0.8241899053009567), (249267, 0.8250490894486218), (1833006, 0.8322644952777933)]\n"
     ]
    }
   ],
   "source": [
    "test = si.rangeQuery(100000, (164500,374500))\n",
    "print(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "c016bc95",
   "metadata": {},
   "outputs": [],
   "source": [
    "tlist = test.values.flatten()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "cddb6cb7",
   "metadata": {},
   "outputs": [],
   "source": [
    "#for item in tlist:\n",
    "    #print(type(item), item)\n",
    "    \n",
    "filtered = filter(lambda i:not(type(i) is float), tlist)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "ae5591ca",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "164500 374500 220650.0 382150.0\n",
      "56668.730354579144\n",
      "2606571 (220650.0, 382150.0) 56668.730354579144\n",
      "164500 374500 221689.0 381370.0\n",
      "57600.1616403982\n",
      "903327 (221689.0, 381370.0) 57600.1616403982\n",
      "164500 374500 229459.0 328040.0\n",
      "79863.65431784348\n",
      "641312 (229459.0, 328040.0) 79863.65431784348\n",
      "164500 374500 228189.0 327480.0\n",
      "79165.45408825747\n",
      "640120 (228189.0, 327480.0) 79165.45408825747\n",
      "164500 374500 223710.0 329950.0\n",
      "74098.08769462272\n",
      "621806 (223710.0, 329950.0) 74098.08769462272\n",
      "164500 374500 222579.0 331460.0\n",
      "72288.39354280879\n",
      "2204228 (222579.0, 331460.0) 72288.39354280879\n",
      "164500 374500 228660.0 338160.0\n",
      "73736.70185192717\n",
      "1935407 (228660.0, 338160.0) 73736.70185192717\n",
      "164500 374500 231499.0 338800.0\n",
      "75916.77022239553\n",
      "228546 (231499.0, 338800.0) 75916.77022239553\n",
      "164500 374500 222959.0 331270.0\n",
      "72706.86061851385\n",
      "2207982 (222959.0, 331270.0) 72706.86061851385\n",
      "164500 374500 224379.0 334780.0\n",
      "71855.22278164615\n",
      "2009108 (224379.0, 334780.0) 71855.22278164615\n",
      "164500 374500 222860.0 331230.0\n",
      "72651.10116164792\n",
      "2015786 (222860.0, 331230.0) 72651.10116164792\n",
      "164500 374500 232209.0 331890.0\n",
      "80000.7548776885\n",
      "2719941 (232209.0, 331890.0) 80000.7548776885\n",
      "164500 374500 228380.0 340830.0\n",
      "72210.27143003965\n",
      "668991 (228380.0, 340830.0) 72210.27143003965\n",
      "164500 374500 229140.0 340700.0\n",
      "72943.60561420035\n",
      "654566 (229140.0, 340700.0) 72943.60561420035\n",
      "164500 374500 229200.0 375180.0\n",
      "64703.573317089686\n",
      "842593 (229200.0, 375180.0) 64703.573317089686\n",
      "164500 374500 231860.0 373110.0\n",
      "67374.34007097954\n",
      "1045379 (231860.0, 373110.0) 67374.34007097954\n",
      "164500 374500 222400.0 383500.0\n",
      "58595.306979313624\n",
      "53464 (222400.0, 383500.0) 58595.306979313624\n",
      "164500 374500 241420.0 338710.0\n",
      "84838.73231018955\n",
      "1834435 (241420.0, 338710.0) 84838.73231018955\n",
      "164500 374500 234060.0 333600.0\n",
      "80693.26861640939\n",
      "1937154 (234060.0, 333600.0) 80693.26861640939\n",
      "164500 374500 237389.0 335180.0\n",
      "82818.28735852969\n",
      "919014 (237389.0, 335180.0) 82818.28735852969\n",
      "164500 374500 237390.0 335580.0\n",
      "82630.0096817131\n",
      "1921176 (237390.0, 335580.0) 82630.0096817131\n",
      "164500 374500 233560.0 334180.0\n",
      "79968.65635985139\n",
      "619139 (233560.0, 334180.0) 79968.65635985139\n",
      "164500 374500 239799.0 339050.0\n",
      "83226.44952777933\n",
      "1833006 (239799.0, 339050.0) 83226.44952777933\n",
      "164500 374500 241200.0 348200.0\n",
      "81083.78382882733\n",
      "123852 (241200.0, 348200.0) 81083.78382882733\n",
      "164500 374500 233160.0 341310.0\n",
      "76261.20704525991\n",
      "2116926 (233160.0, 341310.0) 76261.20704525991\n",
      "164500 374500 241160.0 340750.0\n",
      "83760.48053825862\n",
      "1777898 (241160.0, 340750.0) 83760.48053825862\n",
      "164500 374500 235030.0 344830.0\n",
      "76516.59819934495\n",
      "468175 (235030.0, 344830.0) 76516.59819934495\n",
      "164500 374500 234579.0 344660.0\n",
      "76167.52484491012\n",
      "717723 (234579.0, 344660.0) 76167.52484491012\n",
      "164500 374500 232960.0 341280.0\n",
      "76094.28362235891\n",
      "2121519 (232960.0, 341280.0) 76094.28362235891\n",
      "164500 374500 239099.0 363500.0\n",
      "75405.64170537905\n",
      "255842 (239099.0, 363500.0) 75405.64170537905\n",
      "164500 374500 238730.0 362710.0\n",
      "75160.47498519417\n",
      "2222940 (238730.0, 362710.0) 75160.47498519417\n",
      "164500 374500 235559.0 368960.0\n",
      "71274.63139855582\n",
      "1023817 (235559.0, 368960.0) 71274.63139855582\n",
      "164500 374500 235289.0 373660.0\n",
      "70793.98364974244\n",
      "1077922 (235289.0, 373660.0) 70793.98364974244\n",
      "164500 374500 241550.0 371560.0\n",
      "77106.07044844134\n",
      "802422 (241550.0, 371560.0) 77106.07044844134\n",
      "164500 374500 241400.0 374400.0\n",
      "76900.06501947837\n",
      "153914 (241400.0, 374400.0) 76900.06501947837\n",
      "164500 374500 236290.0 382130.0\n",
      "72194.32803205526\n",
      "988854 (236290.0, 382130.0) 72194.32803205526\n",
      "164500 374500 235500.0 384700.0\n",
      "71728.93418976752\n",
      "550007 (235500.0, 384700.0) 71728.93418976752\n",
      "164500 374500 234700.0 389900.0\n",
      "71869.32586298553\n",
      "1256229 (234700.0, 389900.0) 71869.32586298553\n",
      "164500 374500 236339.0 393090.0\n",
      "74205.32340068332\n",
      "1193728 (236339.0, 393090.0) 74205.32340068332\n",
      "164500 374500 235660.0 392740.0\n",
      "73460.48733843249\n",
      "2203860 (235660.0, 392740.0) 73460.48733843249\n",
      "[(2606571, 56668.730354579144), (903327, 57600.1616403982), (53464, 58595.306979313624), (842593, 64703.573317089686), (1045379, 67374.34007097954), (1077922, 70793.98364974244), (1023817, 71274.63139855582), (550007, 71728.93418976752), (2009108, 71855.22278164615), (1256229, 71869.32586298553), (988854, 72194.32803205526), (668991, 72210.27143003965), (2204228, 72288.39354280879), (2015786, 72651.10116164792), (2207982, 72706.86061851385), (654566, 72943.60561420035), (2203860, 73460.48733843249), (1935407, 73736.70185192717), (621806, 74098.08769462272), (1193728, 74205.32340068332), (2222940, 75160.47498519417), (255842, 75405.64170537905), (228546, 75916.77022239553), (2121519, 76094.28362235891), (717723, 76167.52484491012), (2116926, 76261.20704525991), (468175, 76516.59819934495), (153914, 76900.06501947837), (802422, 77106.07044844134), (640120, 79165.45408825747), (641312, 79863.65431784348), (619139, 79968.65635985139), (2719941, 80000.7548776885), (1937154, 80693.26861640939), (123852, 81083.78382882733), (1921176, 82630.0096817131), (919014, 82818.28735852969), (1833006, 83226.44952777933), (1777898, 83760.48053825862), (1834435, 84838.73231018955)]\n"
     ]
    }
   ],
   "source": [
    "ranked = []\n",
    "for item in filtered:\n",
    "    for key in item:\n",
    "        dist = si.dist((164500,374500), item[key])\n",
    "        print(key, item[key], dist)\n",
    "        ranked.append((key, dist))    \n",
    "ranked.sort(key = lambda x: x[1])\n",
    "print(ranked)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "624ea937",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc3db5ff",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}