{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Creating a polygon from a list of points\n", "\n", "For many of those working with geo data it is a common task being asked to create a polygon from a list of points. More specific, to create a polygon that wraps around those points in a meaningful manner. So, there are several sources in the web explaining how to create the shape (see sources at end of document). This example notebook is the application of those solutions to folium maps." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Helpers" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Imports\n", "import random\n", "\n", "import folium\n", "from scipy.spatial import ConvexHull\n", "\n", "\n", "# Function to create a list of some random points\n", "def randome_points(amount, LON_min, LON_max, LAT_min, LAT_max):\n", "\n", " points = []\n", " for _ in range(amount):\n", " points.append(\n", " (random.uniform(LON_min, LON_max), random.uniform(LAT_min, LAT_max))\n", " )\n", "\n", " return points\n", "\n", "\n", "# Function to draw points in the map\n", "def draw_points(map_object, list_of_points, layer_name, line_color, fill_color, text):\n", "\n", " fg = folium.FeatureGroup(name=layer_name)\n", "\n", " for point in list_of_points:\n", " fg.add_child(\n", " folium.CircleMarker(\n", " point,\n", " radius=1,\n", " color=line_color,\n", " fill_color=fill_color,\n", " popup=(folium.Popup(text)),\n", " )\n", " )\n", "\n", " map_object.add_child(fg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Convex hull\n", "\n", "The convex hull is probably the most common approach - its goal is to create the smallest polygon that contains all points from a given list. The scipy.spatial package provides this algorithm (https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy.spatial.ConvexHull.html, accessed 29.12.2018)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Function that takes a map and a list of points (LON,LAT tupels) and\n", "# returns a map with the convex hull polygon from the points as a new layer\n", "\n", "\n", "def create_convexhull_polygon(\n", " map_object, list_of_points, layer_name, line_color, fill_color, weight, text\n", "):\n", "\n", " # Since it is pointless to draw a convex hull polygon around less than 3 points check len of input\n", " if len(list_of_points) < 3:\n", " return\n", "\n", " # Create the convex hull using scipy.spatial\n", " form = [list_of_points[i] for i in ConvexHull(list_of_points).vertices]\n", "\n", " # Create feature group, add the polygon and add the feature group to the map\n", " fg = folium.FeatureGroup(name=layer_name)\n", " fg.add_child(\n", " folium.vector_layers.Polygon(\n", " locations=form,\n", " color=line_color,\n", " fill_color=fill_color,\n", " weight=weight,\n", " popup=(folium.Popup(text)),\n", " )\n", " )\n", " map_object.add_child(fg)\n", "\n", " return map_object" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Initialize map\n", "my_convexhull_map = folium.Map(location=[48.5, 9.5], zoom_start=8)\n", "\n", "# Create a convex hull polygon that contains some points\n", "list_of_points = randome_points(\n", " amount=10, LON_min=48, LON_max=49, LAT_min=9, LAT_max=10\n", ")\n", "\n", "create_convexhull_polygon(\n", " my_convexhull_map,\n", " list_of_points,\n", " layer_name=\"Example convex hull\",\n", " line_color=\"lightblue\",\n", " fill_color=\"lightskyblue\",\n", " weight=5,\n", " text=\"Example convex hull\",\n", ")\n", "\n", "draw_points(\n", " my_convexhull_map,\n", " list_of_points,\n", " layer_name=\"Example points for convex hull\",\n", " line_color=\"royalblue\",\n", " fill_color=\"royalblue\",\n", " text=\"Example point for convex hull\",\n", ")\n", "\n", "# Add layer control and show map\n", "folium.LayerControl(collapsed=False).add_to(my_convexhull_map)\n", "my_convexhull_map" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Envelope\n", "\n", "The envelope is another interesting approach - its goal is to create a box that contains all points from a given list." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def create_envelope_polygon(\n", " map_object, list_of_points, layer_name, line_color, fill_color, weight, text\n", "):\n", "\n", " # Since it is pointless to draw a box around less than 2 points check len of input\n", " if len(list_of_points) < 2:\n", " return\n", "\n", " # Find the edges of box\n", " from operator import itemgetter\n", "\n", " list_of_points = sorted(list_of_points, key=itemgetter(0))\n", " x_min = list_of_points[0]\n", " x_max = list_of_points[len(list_of_points) - 1]\n", "\n", " list_of_points = sorted(list_of_points, key=itemgetter(1))\n", " y_min = list_of_points[0]\n", " y_max = list_of_points[len(list_of_points) - 1]\n", "\n", " upper_left = (x_min[0], y_max[1])\n", " upper_right = (x_max[0], y_max[1])\n", " lower_right = (x_max[0], y_min[1])\n", " lower_left = (x_min[0], y_min[1])\n", "\n", " edges = [upper_left, upper_right, lower_right, lower_left]\n", "\n", " # Create feature group, add the polygon and add the feature group to the map\n", " fg = folium.FeatureGroup(name=layer_name)\n", " fg.add_child(\n", " folium.vector_layers.Polygon(\n", " locations=edges,\n", " color=line_color,\n", " fill_color=fill_color,\n", " weight=weight,\n", " popup=(folium.Popup(text)),\n", " )\n", " )\n", " map_object.add_child(fg)\n", "\n", " return map_object" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Initialize map\n", "my_envelope_map = folium.Map(location=[49.5, 8.5], zoom_start=8)\n", "\n", "# Create an envelope polygon that contains some points\n", "list_of_points = randome_points(\n", " amount=10, LON_min=49.1, LON_max=50, LAT_min=8, LAT_max=9\n", ")\n", "\n", "create_envelope_polygon(\n", " my_envelope_map,\n", " list_of_points,\n", " layer_name=\"Example envelope\",\n", " line_color=\"indianred\",\n", " fill_color=\"red\",\n", " weight=5,\n", " text=\"Example envelope\",\n", ")\n", "\n", "draw_points(\n", " my_envelope_map,\n", " list_of_points,\n", " layer_name=\"Example points for envelope\",\n", " line_color=\"darkred\",\n", " fill_color=\"darkred\",\n", " text=\"Example point for envelope\",\n", ")\n", "\n", "# Add layer control and show map\n", "folium.LayerControl(collapsed=False).add_to(my_envelope_map)\n", "my_envelope_map" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Concave hull (alpha shape)\n", "In some cases the convex hull does not yield good results - this is when the shape of the polygon should be concave instead of convex. The solution is a concave hull that is also called alpha shape. Yet, there is no ready to go, off the shelve solution for this but there are great resources (see: http://blog.thehumangeo.com/2014/05/12/drawing-boundaries-in-python/, accessed 04.01.2019 or https://towardsdatascience.com/the-concave-hull-c649795c0f0f, accessed 29.12.2018)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Main code\n", "Just putting it all together..." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Initialize map\n", "my_map_global = folium.Map(location=[48.2460683, 9.26764125], zoom_start=7)\n", "\n", "# Create a convex hull polygon that contains some points\n", "list_of_points = randome_points(\n", " amount=10, LON_min=48, LON_max=49, LAT_min=9, LAT_max=10\n", ")\n", "\n", "create_convexhull_polygon(\n", " my_map_global,\n", " list_of_points,\n", " layer_name=\"Example convex hull\",\n", " line_color=\"lightblue\",\n", " fill_color=\"lightskyblue\",\n", " weight=5,\n", " text=\"Example convex hull\",\n", ")\n", "\n", "draw_points(\n", " my_map_global,\n", " list_of_points,\n", " layer_name=\"Example points for convex hull\",\n", " line_color=\"royalblue\",\n", " fill_color=\"royalblue\",\n", " text=\"Example point for convex hull\",\n", ")\n", "\n", "# Create an envelope polygon that contains some points\n", "list_of_points = randome_points(\n", " amount=10, LON_min=49.1, LON_max=50, LAT_min=8, LAT_max=9\n", ")\n", "\n", "create_envelope_polygon(\n", " my_map_global,\n", " list_of_points,\n", " layer_name=\"Example envelope\",\n", " line_color=\"indianred\",\n", " fill_color=\"red\",\n", " weight=5,\n", " text=\"Example envelope\",\n", ")\n", "\n", "draw_points(\n", " my_map_global,\n", " list_of_points,\n", " layer_name=\"Example points for envelope\",\n", " line_color=\"darkred\",\n", " fill_color=\"darkred\",\n", " text=\"Example point for envelope\",\n", ")\n", "\n", "# Add layer control and show map\n", "folium.LayerControl(collapsed=False).add_to(my_map_global)\n", "my_map_global" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sources:\n", "\n", "* http://blog.yhat.com/posts/interactive-geospatial-analysis.html, accessed 28.12.2018\n", "\n", "* https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy.spatial.ConvexHull.html, accessed 29.12.2018\n", "\n", "* https://www.oreilly.com/ideas/an-elegant-solution-to-the-convex-hull-problem, accessed 29.12.2018\n", "\n", "* https://medium.com/@vworri/simple-geospacial-mapping-with-geopandas-and-the-usual-suspects-77f46d40e807, accessed 29.12.2018\n", "\n", "* https://towardsdatascience.com/the-concave-hull-c649795c0f0f, accessed 29.12.2018\n", "\n", "* http://blog.thehumangeo.com/2014/05/12/drawing-boundaries-in-python/, accessed 04.01.2019\n" ] } ], "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.9.0" } }, "nbformat": 4, "nbformat_minor": 2 }