polygon intersection for fun with JSON

polygon intersections with JSON.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## task: find tiles which intersect a query polygon\n",
    "\n",
    "### conditions:\n",
    "- tile boundaries are stored in JSON, as bounding box corners\n",
    "- tile finding method needs to be really simple\n",
    "- there are not massive amounts of tiles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### import stuff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#all the imports we need\n",
    "from shapely import geometry, wkt\n",
    "import json\n",
    "\n",
    "# actually, we didn't need wkt - but it stays to show one way of doing this"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### define some JSON with bounding box corners in it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "tile1json=\"\"\"{\n",
    "\"filename\": \"/path_to_tile1.thing\",\n",
    "\"bbox\": {\n",
    "    \"min_x\": 146.0,\n",
    "    \"max_x\": 149.0,\n",
    "    \"min_y\": -36.0,\n",
    "    \"max_y\": -34.0\n",
    "    }\n",
    "}\n",
    "\"\"\"\n",
    "\n",
    "tile2json=\"\"\"{\n",
    "\"filename\": \"/path_to_tile2.thing\",\n",
    "\"bbox\": {\n",
    "    \"min_x\": 146.0,\n",
    "    \"max_x\": 149.0,\n",
    "    \"min_y\": -38.0,\n",
    "    \"max_y\": -36.0\n",
    "    }\n",
    "}\n",
    "\"\"\"\n",
    "\n",
    "tile3json=\"\"\"{\n",
    "\"filename\": \"/path_to_tile3.thing\",\n",
    "\"bbox\": {\n",
    "    \"min_x\": 145.0,\n",
    "    \"max_x\": 148.0,\n",
    "    \"min_y\": -41.0,\n",
    "    \"max_y\": -38.0\n",
    "    }\n",
    "}\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### loadify tile JSON into python JSON objects"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'bbox': {'max_x': 149.0, 'max_y': -34.0, 'min_x': 146.0, 'min_y': -36.0},\n",
       " 'filename': '/path_to_tile1.thing'}"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tile1 = json.loads(tile1json)\n",
    "tile1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'bbox': {'max_x': 149.0, 'max_y': -36.0, 'min_x': 146.0, 'min_y': -38.0},\n",
       " 'filename': '/path_to_tile2.thing'}"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tile2 = json.loads(tile2json)\n",
    "tile2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'bbox': {'max_x': 148.0, 'max_y': -38.0, 'min_x': 145.0, 'min_y': -41.0},\n",
       " 'filename': '/path_to_tile3.thing'}"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tile3 = json.loads(tile3json)\n",
    "tile3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### a couple ways of creating shapely polygons from the JSONs "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "#bottom left\n",
    "#top left\n",
    "#top right\n",
    "#bottom right\n",
    "#bottom left\n",
    "\n",
    "def polygonify(tile):\n",
    "    poly = geometry.Polygon([\\\n",
    "        (tile[\"bbox\"][\"min_x\"], tile[\"bbox\"][\"min_y\"]),\\\n",
    "        (tile[\"bbox\"][\"min_x\"], tile[\"bbox\"][\"max_y\"]),\\\n",
    "        (tile[\"bbox\"][\"max_x\"], tile[\"bbox\"][\"max_y\"]),\\\n",
    "        (tile[\"bbox\"][\"max_x\"], tile[\"bbox\"][\"min_y\"]),\\\n",
    "        (tile[\"bbox\"][\"min_x\"], tile[\"bbox\"][\"min_y\"])\\\n",
    "        ])\n",
    "    return poly\n",
    "\n",
    "\n",
    "# don't use this way - use polygonify instead\n",
    "def wktify(tile):\n",
    "    poly = wkt.loads(\"POLYGON((\" + \\\n",
    "        str(tile[\"bbox\"][\"min_x\"]) + \" \" + str(tile[\"bbox\"][\"min_y\"]) + \",\" +\\\n",
    "        str(tile[\"bbox\"][\"min_x\"]) + \" \" + str(tile[\"bbox\"][\"max_y\"]) + \",\" +\\\n",
    "        str(tile[\"bbox\"][\"max_x\"]) + \" \" + str(tile[\"bbox\"][\"max_y\"]) + \",\" +\\\n",
    "        str(tile[\"bbox\"][\"max_x\"]) + \" \" + str(tile[\"bbox\"][\"min_y\"]) + \",\" +\\\n",
    "        str(tile[\"bbox\"][\"min_x\"]) + \" \" + str(tile[\"bbox\"][\"min_y\"]) + \"))\")\n",
    "    return poly\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### the wkt way is slower, but it's the first way I thought of so I left it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 443 µs, sys: 330 µs, total: 773 µs\n",
      "Wall time: 456 µs\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"145.88 -36.12 3.240000000000009 2.239999999999995\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-70.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.06480000000000018\" opacity=\"0.6\" d=\"M 146.0,-36.0 L 146.0,-34.0 L 149.0,-34.0 L 149.0,-36.0 L 146.0,-36.0 z\" /></g></svg>"
      ],
      "text/plain": [
       "<shapely.geometry.polygon.Polygon at 0x108cdb6a0>"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#wkt way\n",
    "%time poly1 = wktify(tile1)\n",
    "poly1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 64 µs, sys: 9 µs, total: 73 µs\n",
      "Wall time: 73.9 µs\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"145.88 -36.12 3.240000000000009 2.239999999999995\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-70.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.06480000000000018\" opacity=\"0.6\" d=\"M 146.0,-36.0 L 146.0,-34.0 L 149.0,-34.0 L 149.0,-36.0 L 146.0,-36.0 z\" /></g></svg>"
      ],
      "text/plain": [
       "<shapely.geometry.polygon.Polygon at 0x108cd3b38>"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#direct to polygon is faster!\n",
    "%time poly_1 = polygonify(tile1)\n",
    "poly_1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### make some test polygons... yes this could be more elegant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"145.88 -35.12 3.240000000000009 2.239999999999995\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-68.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.06480000000000018\" opacity=\"0.6\" d=\"M 146.0,-35.0 L 149.0,-35.0 L 149.0,-33.0 L 146.0,-33.0 L 146.0,-35.0 z\" /></g></svg>"
      ],
      "text/plain": [
       "<shapely.geometry.polygon.Polygon at 0x108c38860>"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test1 = wkt.loads(\"POLYGON((146.0 -35.0,149.0 -35.0,149.0 -33.0,146.0 -33.0,146.0 -35.0))\")\n",
    "test1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"145.84 -37.16 3.319999999999993 4.319999999999993\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-70.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.08639999999999987\" opacity=\"0.6\" d=\"M 146.0,-37.0 L 149.0,-37.0 L 149.0,-33.0 L 146.0,-33.0 L 146.0,-37.0 z\" /></g></svg>"
      ],
      "text/plain": [
       "<shapely.geometry.polygon.Polygon at 0x108cd36d8>"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test2 = wkt.loads(\"POLYGON((146.0 -37.0,149.0 -37.0,149.0 -33.0,146.0 -33.0,146.0 -37.0))\")\n",
    "test2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"144.1338134765625 -38.057264489760676 5.671582031250011 2.7457144619221836\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-73.36881451759916)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.11343164062500023\" opacity=\"0.6\" d=\"M 148.6395263671875,-35.52160862158849 L 147.8704833984375,-36.67557848857603 L 145.4315185546875,-37.359788198380755 L 144.3438720703125,-37.23743533287159 L 144.4976806640625,-37.84720589601068 L 144.8382568359375,-37.41216419050447 L 146.7718505859375,-37.50809178041932 L 146.4312744140625,-37.263670557409604 L 147.799072265625,-37.0228393244075 L 148.4857177734375,-36.28690277619996 L 149.5953369140625,-35.87847989454576 L 148.6395263671875,-35.52160862158849 z\" /></g></svg>"
      ],
      "text/plain": [
       "<shapely.geometry.polygon.Polygon at 0x108cd34e0>"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test3 = wkt.loads(\"POLYGON((148.6395263671875 -35.52160862158849,147.8704833984375 -36.67557848857603,145.4315185546875 -37.359788198380755,144.3438720703125 -37.23743533287159,144.4976806640625 -37.84720589601068,144.8382568359375 -37.41216419050447,146.7718505859375 -37.50809178041932,146.4312744140625 -37.263670557409604,147.799072265625 -37.0228393244075,148.4857177734375 -36.28690277619996,149.5953369140625 -35.87847989454576,148.6395263671875 -35.52160862158849))\")\n",
    "test3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"144.416162109375 -43.76216349143403 4.129101562500011 3.3209508468098505\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-84.20337613605821)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.08258203125000023\" opacity=\"0.6\" d=\"M 146.282958984375,-41.14246722711794 L 144.569091796875,-40.59414233212418 L 144.722900390625,-41.472573364876816 L 145.601806640625,-43.06587799626204 L 146.348876953125,-43.60923380393403 L 147.447509765625,-43.60923380393403 L 148.040771484375,-43.017701451969884 L 148.282470703125,-41.91556321720711 L 148.392333984375,-40.86056386254487 L 147.952880859375,-40.74413568925236 L 146.986083984375,-41.026535404976656 L 146.282958984375,-41.14246722711794 z\" /></g></svg>"
      ],
      "text/plain": [
       "<shapely.geometry.polygon.Polygon at 0x108cd32b0>"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test4 = wkt.loads(\"POLYGON((146.282958984375 -41.14246722711794,144.569091796875 -40.59414233212418,144.722900390625 -41.472573364876816,145.601806640625 -43.06587799626204,146.348876953125 -43.60923380393403,147.447509765625 -43.60923380393403,148.040771484375 -43.017701451969884,148.282470703125 -41.91556321720711,148.392333984375 -40.86056386254487,147.952880859375 -40.74413568925236,146.986083984375 -41.026535404976656,146.282958984375 -41.14246722711794))\")\n",
    "test4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### make a test function - we want to return the filename of tiles which intersect the test polygon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findthething(test,list_of_tiles):\n",
    "    list_of_matches = []\n",
    "    for tile in list_of_tiles:\n",
    "        if geometry.Polygon.intersects(test, polygonify(tile)):\n",
    "            list_of_matches.append(tile[\"filename\"])\n",
    "        \n",
    "    return list_of_matches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### test 1. Polygon test1 should only intersect tile1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 423 µs, sys: 211 µs, total: 634 µs\n",
      "Wall time: 490 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['/path_to_tile1.thing']"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time findthething(test1, [tile1,tile2,tile3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### test 2. Polygon test2 should intersect both tile1 and tile2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 502 µs, sys: 295 µs, total: 797 µs\n",
      "Wall time: 578 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['/path_to_tile1.thing', '/path_to_tile2.thing']"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time findthething(test2, [tile1,tile2,tile3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### test 3. Polygon test3 should intersect both tile1 and tile2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 586 µs, sys: 442 µs, total: 1.03 ms\n",
      "Wall time: 639 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['/path_to_tile1.thing', '/path_to_tile2.thing']"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time findthething(test3, [tile1,tile2,tile3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### test 4. Polygon test4 should intersect only tile3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 638 µs, sys: 546 µs, total: 1.18 ms\n",
      "Wall time: 695 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['/path_to_tile3.thing']"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time findthething(test4, [tile1,tile2,tile3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fun! hope that helps..."
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}