search_trails.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 5,
     "status": "ok",
     "timestamp": 1697322850769,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "DKE7TzNWTQjj"
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import pickle\n",
    "from tqdm import tqdm\n",
    "from shapely.geometry import Point, LineString\n",
    "from rtree import index\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.colors as mcolors\n",
    "\n",
    "import utils.projections as projections\n",
    "\n",
    "standard_colors = list(mcolors.BASE_COLORS.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 11,
     "status": "ok",
     "timestamp": 1697322812563,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "kKELb7dpTlH5"
   },
   "outputs": [],
   "source": [
    "filename = os.path.join(\"data\", 'all_trail_segments.pickle')\n",
    "\n",
    "with open(filename, 'rb') as f:\n",
    "    hiking_trails = pickle.load(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 215,
     "status": "ok",
     "timestamp": 1697322812767,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "_KT4hni0TmX9"
   },
   "outputs": [],
   "source": [
    "filename = os.path.join(\"data\", 'all_lakes.pickle')\n",
    "\n",
    "with open(filename, 'rb') as f:\n",
    "    lakes = pickle.load(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 333,
     "status": "ok",
     "timestamp": 1697322813089,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "y2S4b8OgT1Rk"
   },
   "outputs": [],
   "source": [
    "# Create an R-tree index\n",
    "trail_idx = index.Index()\n",
    "\n",
    "# Insert lines into the R-tree index with their bounding boxes\n",
    "for i, (line, _) in enumerate(hiking_trails):\n",
    "    bbox = line.bounds\n",
    "    trail_idx.insert(i, bbox)\n",
    "\n",
    "# Function to find the polygon a line is in (O(log(N)) time complexity)\n",
    "def find_neighbors_for_trail(l, line):\n",
    "    connected = []\n",
    "    for i in trail_idx.intersection(line.bounds):\n",
    "        if i != l:\n",
    "            # TODO: Consider if need to loosen the intersection if trails don't exactly meet.\n",
    "            intersection = hiking_trails[i][0].intersection(line)\n",
    "            if not intersection.is_empty:\n",
    "                connected.append(i)\n",
    "    return connected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1542,
     "status": "ok",
     "timestamp": 1697322814561,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "B7O3ZWNtUU3h",
    "outputId": "b47175c7-4946-418f-8bfb-8f15cbe3a3d5"
   },
   "outputs": [],
   "source": [
    "trail_subset = hiking_trails\n",
    "graph = []\n",
    "for l, (line, _) in tqdm(enumerate(trail_subset)):\n",
    "    connections = find_neighbors_for_trail(l, line)\n",
    "    graph.append(connections)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 8,
     "status": "ok",
     "timestamp": 1697322862083,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "Pcz1enF0UITp"
   },
   "outputs": [],
   "source": [
    "def print_trail(trail, neighbors):\n",
    "    fig, ax = plt.subplots(1, 1, figsize=(6, 5))\n",
    "\n",
    "    rendered_trail = projections.project_line_to_meters(trail[0])\n",
    "\n",
    "    rendered_neighbors = []\n",
    "    for n in neighbors:\n",
    "        rendered_neighbor = projections.project_line_to_meters(hiking_trails[n][0])\n",
    "        rendered_neighbors.append(rendered_neighbor)\n",
    "\n",
    "    x, y = rendered_trail.xy\n",
    "    ax.plot(x, y, label='Trail', color=standard_colors[0])\n",
    "\n",
    "    for i, n in enumerate(rendered_neighbors):\n",
    "        x, y = n.xy\n",
    "        ax.plot(x, y, label='Neighbor {}'.format(i), color=standard_colors[(i+1) % len(standard_colors)])\n",
    "\n",
    "     # Set labels and legend\n",
    "    ax.set_xlabel('X')\n",
    "    ax.set_ylabel('Y')\n",
    "    ax.set_title(\"Trail {} w/ neighbors\".format(trail[1]['name']))\n",
    "    ax.legend()\n",
    "\n",
    "    # Set equal aspect ratio\n",
    "    plt.axis('equal')\n",
    "\n",
    "    # Show the plot\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "executionInfo": {
     "elapsed": 6774,
     "status": "ok",
     "timestamp": 1697322889872,
     "user": {
      "displayName": "Sydney Zheng",
      "userId": "10865219995042169349"
     },
     "user_tz": 0
    },
    "id": "DFwgW2GRUGLI",
    "outputId": "bb139b47-16f9-4696-a939-1d333f6eee91"
   },
   "outputs": [],
   "source": [
    "LIMIT = 15\n",
    "count = 0\n",
    "for i in range(len(trail_subset)):\n",
    "    trail = trail_subset[i]\n",
    "\n",
    "    neighbors = graph[i]\n",
    "    print_trail(trail, neighbors)\n",
    "\n",
    "    count += 1\n",
    "    if count == LIMIT:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "OLxiqTclVL8c"
   },
   "outputs": [],
   "source": [
    "# Searchable attributes of generated trail:\n",
    "# - D_min <= Total distance <= D_max\n",
    "# - E_min <= [later] Elevation delta <= E_max\n",
    "# - Near lake? (K, 1 = yes, 0 = no)\n",
    "# - Is loop? (P, 1 = yes, 0 = no)\n",
    "\n",
    "# Graph\n",
    "# where node is point between trails\n",
    "# and edge is trail segment\n",
    "# with following features in attribute vector, A:\n",
    "# - Distance (A1)\n",
    "# - Elevation change (A2)\n",
    "# - Near lake? (A3, 1 = yes, 0 = no)\n",
    "\n",
    "# Perform DFS and only accept paths with segments, S, where:\n",
    "# - D_min <= Sum_S[S(A1)] <= D_max\n",
    "# - E_min <= Sum_S[S(A2)] <= E_max\n",
    "# - Sum_S[S(A3)] == 1 if K == 1\n",
    "# - S[0] == S[-1] if P == 1"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyNPbeoPD7ZYI7587tBtJqZv",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}