notebooks/stats_tables/extreme_hex_area.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hexagon cell area variation\n",
    "\n",
    "The hexagons vary in size according to their location on the sphere.\n",
    "This distortion comes from the gnomonic projection of cells onto the sphere.\n",
    "\n",
    "This notebook computes the minimum and maximum **hexagon** cell areas on the sphere at each resolution.\n",
    "We're excluding pentagons since they're a special case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Brute force area calculation\n",
    "\n",
    "We can find the minimum and maximum area **hexagons** (excluding pentagons) using brute force search over all hexagons\n",
    "at each resolution. However, this search becomes impractically slow for finer resolutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import h3\n",
    "from tabulate import tabulate\n",
    "\n",
    "def brute_extreme_area_hex(res, min_or_max=min):\n",
    "    \"\"\"\n",
    "    Note: Due to symmetry, the extremal hex is not unique.\n",
    "    \"\"\"\n",
    "    cells = h3.get_res0_indexes()\n",
    "    cells = h3.uncompact(cells, res)\n",
    "    cells = (c for c in cells if not h3.h3_is_pentagon(c))\n",
    "    \n",
    "    h = min_or_max(cells, key=h3.cell_area)\n",
    "    \n",
    "    return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.970457453618385"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res = 4\n",
    "\n",
    "h_max = brute_extreme_area_hex(res, max)\n",
    "h_min = brute_extreme_area_hex(res, min)\n",
    "\n",
    "h3.cell_area(h_max)/h3.cell_area(h_min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using recursive search\n",
    "\n",
    "To find the hexagons at each resolution with the min/max area, we can use a recursive procedure where we find the extremal hex at the coarser resolution, and then look around a neighborhood of that hex (really, its children) at a finer resolution. Due to the continuous nature of the area distortions, this method should give us exact results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def extreme_small_neighborhood(h, min_or_max=min, k=1):\n",
    "    \"\"\" Take the k-ring of cells around (and including) h,\n",
    "    take all their children, and find the one who's\n",
    "    area is min/max of the group.\n",
    "    \"\"\"\n",
    "    cells = h3.k_ring(h, k)\n",
    "    \n",
    "    res =  h3.h3_get_resolution(h) + 1\n",
    "    cells = h3.uncompact(cells, res)\n",
    "    \n",
    "    cells = (c for c in cells if not h3.h3_is_pentagon(c))\n",
    "\n",
    "    h = min_or_max(cells, key=h3.cell_area)\n",
    "        \n",
    "    return h\n",
    "\n",
    "def extreme_area_hex(res, min_or_max=min, k=1):\n",
    "    \"\"\" Get the extreme min/max area hex at given resolution\n",
    "    by recursively searching small neighborhoods of whatever\n",
    "    the coarser resolution's extremal hex was.\n",
    "    \"\"\"\n",
    "    if res == 0:\n",
    "        cells = h3.get_res0_indexes()\n",
    "        cells = (c for c in cells if not h3.h3_is_pentagon(c))\n",
    "        return min_or_max(cells, key=h3.cell_area)\n",
    "    else:\n",
    "        h = extreme_area_hex(res-1, min_or_max)\n",
    "        h = extreme_small_neighborhood(h, min_or_max, k=k)\n",
    "        return h"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compare brute force to the recursive search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.970457453618161"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res = 4\n",
    "\n",
    "h_max = extreme_area_hex(res, max)\n",
    "h_min = extreme_area_hex(res, min)\n",
    "\n",
    "h3.cell_area(h_max)/h3.cell_area(h_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.970457453618385"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "res = 4\n",
    "\n",
    "h_max = brute_extreme_area_hex(res, max)\n",
    "h_min = brute_extreme_area_hex(res, min)\n",
    "\n",
    "h3.cell_area(h_max)/h3.cell_area(h_min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Format results in a nice table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stats():\n",
    "    \"\"\"\n",
    "    For each resolution yield:\n",
    "    - resolution\n",
    "    - maximum *hex* area\n",
    "    - minimum *hex* area\n",
    "    - ratio of max/min\n",
    "    \"\"\"\n",
    "    for res in range(16):\n",
    "        h_max = extreme_area_hex(res, max)\n",
    "        h_min = extreme_area_hex(res, min)\n",
    "        \n",
    "        a_max = h3.cell_area(h_max)\n",
    "        a_min = h3.cell_area(h_min)\n",
    "\n",
    "        yield res, a_min, a_max, a_max/a_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 4106166.334463915, 4977807.027442012, 1.2122760312124314),\n",
       " (1, 447684.2018179402, 729486.8752753442, 1.62946754054101),\n",
       " (2, 56786.62288947397, 104599.80721892511, 1.8419797110053862),\n",
       " (3, 7725.505769639398, 14950.773301378937, 1.935248480446969),\n",
       " (4, 1084.005635362784, 2135.986983964688, 1.970457453618161),\n",
       " (5, 153.7662444479533, 305.1443087785733, 1.984468762140174),\n",
       " (6, 21.91002101263703, 43.59211168500078, 1.9895969821233024),\n",
       " (7, 3.1268360301030746, 6.227445905490173, 1.9916125583613953),\n",
       " (8, 0.44652617408295603, 0.8896351574995928, 1.9923471660461176),\n",
       " (9, 0.06378022693678723, 0.12709073735993393, 1.9926353897406783),\n",
       " (10, 0.009110980969550845, 0.018155819634610822, 1.9927403750801458),\n",
       " (11, 0.0013015418135499314, 0.002593688519461668, 1.992781555275147),\n",
       " (12, 0.00018593314532801717, 0.00037052693136442757, 1.9927965544322723),\n",
       " (13, 2.65617994932581e-05, 5.2932418770310184e-05, 1.9928024373403412),\n",
       " (14, 3.794538702988277e-06, 7.5617741108915425e-06, 1.9928045812094342),\n",
       " (15, 5.420767288789694e-07, 1.0802534449686401e-06, 1.992805422956702)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(stats())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0  4,977,807.027442012  4,106,166.334463915  1.212276\n",
      " 1    729,486.875275344    447,684.201817940  1.629468\n",
      " 2    104,599.807218925     56,786.622889474  1.841980\n",
      " 3     14,950.773301379      7,725.505769639  1.935248\n",
      " 4      2,135.986983965      1,084.005635363  1.970457\n",
      " 5        305.144308779        153.766244448  1.984469\n",
      " 6         43.592111685         21.910021013  1.989597\n",
      " 7          6.227445905          3.126836030  1.991613\n",
      " 8          0.889635157          0.446526174  1.992347\n",
      " 9          0.127090737          0.063780227  1.992635\n",
      "10          0.018155820          0.009110981  1.992740\n",
      "11          0.002593689          0.001301542  1.992782\n",
      "12          0.000370527          0.000185933  1.992797\n",
      "13          0.000052932          0.000026562  1.992802\n",
      "14          0.000007562          0.000003795  1.992805\n",
      "15          0.000001080          0.000000542  1.992805\n"
     ]
    }
   ],
   "source": [
    "res_fmt = '{:2d}'\n",
    "float_fmt = '{:20,.9f}'\n",
    "ratio_fmt = '{:.6f}'\n",
    "\n",
    "fmt = f'{res_fmt} {float_fmt} {float_fmt}  {ratio_fmt}'\n",
    "\n",
    "for res, a_min, a_max, ratio in stats():\n",
    "    print(fmt.format(res, a_max, a_min, ratio))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, ' 4,106,166.334463915', ' 4,977,807.027442012', '1.212276'),\n",
       " (1, '   447,684.201817940', '   729,486.875275344', '1.629468'),\n",
       " (2, '    56,786.622889474', '   104,599.807218925', '1.841980'),\n",
       " (3, '     7,725.505769639', '    14,950.773301379', '1.935248'),\n",
       " (4, '     1,084.005635363', '     2,135.986983965', '1.970457'),\n",
       " (5, '       153.766244448', '       305.144308779', '1.984469'),\n",
       " (6, '        21.910021013', '        43.592111685', '1.989597'),\n",
       " (7, '         3.126836030', '         6.227445905', '1.991613'),\n",
       " (8, '         0.446526174', '         0.889635157', '1.992347'),\n",
       " (9, '         0.063780227', '         0.127090737', '1.992635'),\n",
       " (10, '         0.009110981', '         0.018155820', '1.992740'),\n",
       " (11, '         0.001301542', '         0.002593689', '1.992782'),\n",
       " (12, '         0.000185933', '         0.000370527', '1.992797'),\n",
       " (13, '         0.000026562', '         0.000052932', '1.992802'),\n",
       " (14, '         0.000003795', '         0.000007562', '1.992805'),\n",
       " (15, '         0.000000542', '         0.000001080', '1.992805')]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fmt_float(x):\n",
    "    s = float_fmt\n",
    "    return s.format(x)\n",
    "\n",
    "def fmt_ratio(x):\n",
    "    s = ratio_fmt\n",
    "    return s.format(x)\n",
    "\n",
    "fmt_stats = [\n",
    "    (a, fmt_float(b), fmt_float(c), fmt_ratio(d))\n",
    "    for a,b,c,d in stats()\n",
    "]\n",
    "\n",
    "fmt_stats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|   Res |   Min <ins>Hexagon</ins> Area (km^2) |   Max <ins>Hexagon</ins> Area (km^2) |   Ratio (max/min) |\n",
      "|------:|-------------------------------------:|-------------------------------------:|------------------:|\n",
      "|     0 |                  4,106,166.334463915 |                  4,977,807.027442012 |          1.212276 |\n",
      "|     1 |                    447,684.201817940 |                    729,486.875275344 |          1.629468 |\n",
      "|     2 |                     56,786.622889474 |                    104,599.807218925 |          1.841980 |\n",
      "|     3 |                      7,725.505769639 |                     14,950.773301379 |          1.935248 |\n",
      "|     4 |                      1,084.005635363 |                      2,135.986983965 |          1.970457 |\n",
      "|     5 |                        153.766244448 |                        305.144308779 |          1.984469 |\n",
      "|     6 |                         21.910021013 |                         43.592111685 |          1.989597 |\n",
      "|     7 |                          3.126836030 |                          6.227445905 |          1.991613 |\n",
      "|     8 |                          0.446526174 |                          0.889635157 |          1.992347 |\n",
      "|     9 |                          0.063780227 |                          0.127090737 |          1.992635 |\n",
      "|    10 |                          0.009110981 |                          0.018155820 |          1.992740 |\n",
      "|    11 |                          0.001301542 |                          0.002593689 |          1.992782 |\n",
      "|    12 |                          0.000185933 |                          0.000370527 |          1.992797 |\n",
      "|    13 |                          0.000026562 |                          0.000052932 |          1.992802 |\n",
      "|    14 |                          0.000003795 |                          0.000007562 |          1.992805 |\n",
      "|    15 |                          0.000000542 |                          0.000001080 |          1.992805 |\n"
     ]
    }
   ],
   "source": [
    "headers = [\n",
    "    'Res',\n",
    "    'Min <ins>Hexagon</ins> Area (km^2)',\n",
    "    'Max <ins>Hexagon</ins> Area (km^2)',\n",
    "    'Ratio (max/min)'\n",
    "]\n",
    "out = tabulate(fmt_stats, headers=headers, tablefmt='pipe', stralign='right', disable_numparse=True)\n",
    "\n",
    "print(out)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "|   Res |   Min <ins>Hexagon</ins> Area (km^2) |   Max <ins>Hexagon</ins> Area (km^2) |   Ratio (max/min) |\n",
       "|------:|-------------------------------------:|-------------------------------------:|------------------:|\n",
       "|     0 |                  4,106,166.334463915 |                  4,977,807.027442012 |          1.212276 |\n",
       "|     1 |                    447,684.201817940 |                    729,486.875275344 |          1.629468 |\n",
       "|     2 |                     56,786.622889474 |                    104,599.807218925 |          1.841980 |\n",
       "|     3 |                      7,725.505769639 |                     14,950.773301379 |          1.935248 |\n",
       "|     4 |                      1,084.005635363 |                      2,135.986983965 |          1.970457 |\n",
       "|     5 |                        153.766244448 |                        305.144308779 |          1.984469 |\n",
       "|     6 |                         21.910021013 |                         43.592111685 |          1.989597 |\n",
       "|     7 |                          3.126836030 |                          6.227445905 |          1.991613 |\n",
       "|     8 |                          0.446526174 |                          0.889635157 |          1.992347 |\n",
       "|     9 |                          0.063780227 |                          0.127090737 |          1.992635 |\n",
       "|    10 |                          0.009110981 |                          0.018155820 |          1.992740 |\n",
       "|    11 |                          0.001301542 |                          0.002593689 |          1.992782 |\n",
       "|    12 |                          0.000185933 |                          0.000370527 |          1.992797 |\n",
       "|    13 |                          0.000026562 |                          0.000052932 |          1.992802 |\n",
       "|    14 |                          0.000003795 |                          0.000007562 |          1.992805 |\n",
       "|    15 |                          0.000000542 |                          0.000001080 |          1.992805 |"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import Markdown\n",
    "Markdown(out)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}