GeometricMotionPlanning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Section III. MOTION PLANNING\n",
    "    \n",
    "# Chapter 9. Motion Planning in Simple Geometric Spaces\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will introduce the key issues involved in motion planning in a\n",
    "simple, illustrative *planar path planning* setting. Here, the robot\n",
    "consists only of a point, moving in 2D in an environment with polygonal\n",
    "obstacles. Later we will extend this to handle robots with geometry that\n",
    "can translate and rotate. Planar path planning is useful for a number of\n",
    "applications involving mobile ground robots, autonomous boats, and\n",
    "defining waypoints for aerial vehicles. It is also useful for providing\n",
    "coarse guidance paths for legged robots and mobile manipulators.\n",
    "\n",
    "In motion planning, it is impossible for an algorithm to consider the\n",
    "continuous infinity of paths in the free space. So, the main question to\n",
    "ask is how can an algorithm get away with considering a finite number of\n",
    "alternatives when the true number of alternatives is infinite? What must\n",
    "be sacrificed?\n",
    "\n",
    "In the 2D context, we have the relative luxury of having a polygonal\n",
    "representation of C-obstacles (but not necessarily the free space),\n",
    "which provides much richer geometric information than in the\n",
    "high-dimensional problems we will consider in the next section. We will\n",
    "consider three classes of algorithm: bug algorithms, roadmap planners,\n",
    "and cell decomposition planners.\n",
    "\n",
    "*Bug algorithms* are interesting because the robot only needs local\n",
    "information about the shape of obstacles, and a small amount of memory,\n",
    "to achieve the goal. They can therefore be executed on simple robots\n",
    "without knowledge of all of the obstacles in the space. However, they\n",
    "can be extremely inefficient. *Roadmap planners* build a network of\n",
    "paths in free space. Once a network is constructed, a graph search\n",
    "algorithm can be invoked to yield a solution path. *Cell decomposition\n",
    "planners* also build a network, but a network of adjacent regions in\n",
    "free space. In both roadmap and cell decomposition planners, the manner\n",
    "in which the graph is constructed dictates the performance,\n",
    "completeness, and solution quality of the algorithm.\n",
    "\n",
    "These planners can largely be extended to robots that contain some\n",
    "geometry and can translate and rotate on the plane. We will describe\n",
    "some extensions of these techniques to generate smooth motions, which\n",
    "are applicable to car-like mobile robots and aerial vehicles that cannot\n",
    "rotate in place.\n",
    "\n",
    "Bug algorithms\n",
    "--------------\n",
    "\n",
    "Bug algorithms are simple, clever planning methods that do not actually need a map of obstacles to work!  The only pieces of information needed on-board the robot are 1) a way to determine the robot's current location $X$ and goal location $G$, 2) a contact sensor, and 3) a bit of memory.  By studying how the robot would behave in certain maps, this give us a sense of how to analyze the performance of planners. \n",
    "\n",
    "The inspiration for bug algorithms comes from the _right-hand rule_ for solving mazes. If you are in a maze, a sure-fire way not to get lost is to find a wall, face a direction so that the wall is on your right, and walk along the wall while keeping it immediately to your right.  By following this process, only two possibilities may result: 1) you exit the maze, or 2) you return to the point at which you first touched the wall.  If you return to the starting point, the wall makes a closed circuit, so the next step should be to find a new portion of wall that you did not touch, and apply the right-hand rule again for that new wall.  Using this approach, you are guaranteed to explore the entire maze.  (There is no significance to right vs left; you can just as easily apply a _left-hand rule_.)\n",
    "\n",
    "The first method we will study is called Bug 1.  Unlike the case of a maze, in planning we know which direction we would need to take to reach the goal.  So, Bug 1 proceeds as follows:\n",
    "\n",
    "*************\n",
    "<a name=\"alg:Bug1\"></a>\n",
    "**Algorithm Bug 1**\n",
    "\n",
    "1. Move in a straight line path toward $G$.\n",
    "\n",
    "2. If the robot reaches $G$, we are done.  \n",
    "\n",
    "3. If the robot hits an obstacle, then follow the right-hand rule and traverse its boundary \n",
    "\n",
    "4. This continues until the wall no longer is pointing against the straight line from $X$ toward $G$.  Once this occurs, continue from Step 1.\n",
    "**************\n",
    "\n",
    "It is important to note that in Step 4, this determination is done only locally.  It does not examine the overall shape of the obstacle to see if the straight line does not overlap the obstacle, only locally whether taking the direction $G-X$ leads the robot into free space. \n",
    "\n",
    "*************\n",
    "\n",
    "![fig:Bug0](figures/planning/bug0.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:Bug0\">Figure 1</a>.\n",
    "    The simple Bug 1 algorithm that simply 1) heads toward the goal, 2) turns\n",
    "left when it hits an obstacle, and proceeds to hug the wall, and 3) continues towards the goal\n",
    "    whenever it can.\n",
    "</div>\n",
    "\n",
    "*************\n",
    "\n",
    "The second method is called Bug 2, and is a little more complex.  Here, we shall add some memory to the robot.\n",
    "\n",
    "*************\n",
    "<a name=\"alg:Bug2\"></a>\n",
    "**Algorithm Bug 2**\n",
    "1. Move in a straight line path toward $G$. \n",
    "\n",
    "2. If the robot reaches $G$, we are done.  \n",
    "\n",
    "3. If the robot hits an obstacle, remember the point $P$ at which it is hit.  Follow the right hand-rule.\n",
    "\n",
    "4. If the robot crosses the line $\\overline{PG}$ as it walks along the wall, determine whether $\\| X-G \\| < \\|P-G\\|$ and the wall is not pointing against the straight line from $X$ toward $G$.  If both conditions are satisfied, continue from step 1.  Otherwise, keep walking.\n",
    "\n",
    "5. If $P$ is reached again, return \"No path\"\n",
    "*************\n",
    "\n",
    "Fig. 2 shows how this algorithm works.\n",
    "\n",
    "*************\n",
    "\n",
    "<a name=\"fig:Bug2\"></a>\n",
    "![fig:Bug2](figures/planning/bug2.svg)\n",
    "\n",
    "<div class=\"figcaption\">Figure 2.\n",
    "    The Bug 2 algorithm remembers the line from the start to the\n",
    "goal, and circumnavigates an obstacle until it meets the line again at a\n",
    "closer point to the goal.\n",
    "</div>\n",
    "\n",
    "\n",
    "*************\n",
    "\n",
    "Bug 1 might seem at first to be a little more efficient than Bug 2, because it will opportunistically move in a straight line toward the goal whenever it can break away from the obstacle.  Bug 2 has to hug the boundary of an obstacle until it reaches the line $\\overline{PG}$ again.  However, the problem in Bug 1 is that it may fall into an _infinite loop_, as shown in Fig. 3.  Here, the obstacle is set up so that the robot breaks away from the obstacle, only to hit it again.\n",
    "\n",
    "*************\n",
    "\n",
    "<a name=\"fig:Bugtrap\"></a>\n",
    "![fig:Bugtrap](figures/planning/bugtraps.svg)\n",
    "\n",
    "<div class=\"figcaption\">Figure 3.\n",
    "    A \"bugtrap\" environment designed so that Bug 1 falls into an infinite\n",
    "loop, while Bug 2\n",
    "succeeds.\n",
    "</div>\n",
    "\n",
    "*************\n",
    "\n",
    "By contrast, Bug 2 delays breaking away from the obstacle, which traverses a longer length of the obstacle boundary. In this example, the breakaway point is chosen more judiciously to avoid the infinite loop.  But this is only an anecdote; can we _prove_ that Bug 2 will always succeed (i.e., is a complete planner)?  It turns out that we can.\n",
    "\n",
    "To prove completeness of Bug 2, we shall need to establish 3 facts:\n",
    "\n",
    "A. For each obstacle, Bug 2 will break away from it at some point if there is a path to the goal.\n",
    "\n",
    "B. The sequence of hit points decreases in distance to the goal.\n",
    "\n",
    "C. If there is no path to the goal, then Bug 2 will terminate correctly with failure.\n",
    "\n",
    "\n",
    "Let $O$ be a connected, bounded, planar obstacle, and $P$ any location at which Bug 2 hits it.  Now consider the  curve $\\partial O$ traversed by the right hand rule.  This curve will be the boundary of $O$ if $O$ contains zero holes, but if $O$ contains holes then it will be some connected component of its boundary.  $\\partial O$ is a closed curve dividing the plane into two connected components, and a fact of plane geometry is that a closed curve $C$ separates two points $A \\notin C$ and $B \\notin C$ iff $\\overline{AB}$ intersects $C$ in an odd number of points.  Let $P^\\prime$ be the point immediately preceeding $P$ on the robot's path.  We know that $P^\\prime \\notin O$, and $\\|P^\\prime - G \\| > \\|P-G\\|$, because Bug 2 only moves toward the goal, never away from it.   So, if there is a path to the goal, then the line $\\overline{P^\\prime G}$ intersects $\\partial O$ an even number of times.   Hence, there is at least one other intersection point other than $P$.  Let $C$ be the closest intersection point.  The line segment between $C$ and $G$ will be pointing away from $O$, hence, we know that $C\\neq P$ since the line from $P$ to $G$ points into $O$.  Hence, the robot must break away at from $\\partial O$ at some closer point.  This establishes fact A.\n",
    "\n",
    "Second, let $L$ be the point at which the robot leaves obstacle $O$.  If the robot hits another obstacle, it will have traveled in a straight line from $L$ to $G$, so its next hit point $P^\\prime$ is closer to $G$ than $L$.  Since $\\|P - G \\| > \\| L - G \\| > \\|P^\\prime - G\\|$, the sequence of hit points are decreasing in distance, establishing fact B.\n",
    "\n",
    "Finally, we need to establish that termination at Step 5 correctly determines that no path exists.  As established in B, the sequence of hit points has decreasing distance, so an infinite loop is not possible: Bug 2 must either find the goal or terminate with \"No path\".  As established in A, \"No path\" will not be returned if there is a path to the goal. By contradiction, returning \"No path\" implies there is no path to the goal.  QED."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Roadmap planners\n",
    "----------------\n",
    "\n",
    "Roadmap planners are able to achieve higher quality paths than bug\n",
    "algorithms, but require advance knowledge of all obstacles. They operate\n",
    "by computing a graph $G$ where vertices indicate free configurations and\n",
    "edges indicate collision-free paths (usually straight lines). Then,\n",
    "graph search is performed on this structure to produce a free path. See\n",
    "[Appendix C.1](GraphSearch.ipynb) for more information about graph search\n",
    "algorithms.\n",
    "\n",
    "### Grid search\n",
    "\n",
    "\n",
    "\n",
    "A straightforward method for planning paths in 2D is grid search. Let us\n",
    "define the graph $G$ such that all vertices lie on a grid, and all edges\n",
    "are vertical or horizontal and connect subsequent vertices. Let us\n",
    "assume that $s$ and $g$ lie directly on grid vertices. If we remove all\n",
    "vertices from the grid that are contained within obstacles, and remove\n",
    "edges that intersect obstacles, then a search on the remaining graph\n",
    "will yield a path from the start to the goal\n",
    "([Fig. 4](#fig:Grid4)).\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:Grid4](figures/planning/grid4.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:Grid4\">Figure 4</a>.\n",
    "    Searching along a grid is a resolution complete\n",
    "method.\n",
    "</div>\n",
    "\n",
    "****************\n",
    "\n",
    "If the grid has $m$ divisions in the $x$ direction and $n$ divisions in the $y$ direction, then there are at most $mn$ vertices in the grid.  As discussed in [Appendix C.1](GraphSearch.ipynb), the running time of Dijkstra's algorithm will be $O(mn \\log mn)$.\n",
    "\n",
    "There are two main issues with grid search. First, if the obstacles are\n",
    "constructed to contain *narrow passages* smaller than the resolution of\n",
    "the grid, then it is unlikely for the graph to contain a feasible path\n",
    "even if one exists in the continuous space (unless we are lucky and the\n",
    "narrow passage lines up with the grid edges). The solution to this\n",
    "problem is to reduce the resolution of the grid until it is\n",
    "sufficiently fine to find a path through the narrow passage, as shown below.\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:NarrowPassageGrid](figures/planning/narrow_passage_grid.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:NarrowPassageGrid\">Figure 5</a>.\n",
    "    (Left) A grid search is very likely to fail if the robot needs to pass\n",
    "through a narrow passage smaller than the grid resolution. (Middle) The\n",
    "clearance of a path is the minimum distance to obstacles of any point on\n",
    "the path. (Right) If there exists a path with clearance at least\n",
    "$d \\geq h/\\sqrt{2}$ away from obstacles, then a grid planner with\n",
    "resolution $h$ will find a\n",
    "path.\n",
    "</div>\n",
    "\n",
    "****************\n",
    "\n",
    "\n",
    "To make this more rigorous, let us denote the *clearance* of a point as\n",
    "the distance to the nearest obstacle, and the clearance of a path to be\n",
    "the minimum clearance of all points along the path. It can be easily\n",
    "shown that if there *exists in the free space* a path with clearance at\n",
    "least $h / \\sqrt 2$, then search on a grid with resolution $h$ will find\n",
    "a feasible path. Hence, grid search is resolution-complete.\n",
    "\n",
    "\n",
    "The second issue is that the grid does not contain shortest paths in the\n",
    "original space. Any diagonal movement can only be approximated by a\n",
    "series of axis-aligned movements, which is suboptimal regardless of the\n",
    "resolution of the grid. To partially mitigate this suboptimality, four\n",
    "$45^\\circ$ diagonal edges between grid cells may be added with cost\n",
    "$h \\sqrt 2$. For an even better result, the 8 diagonal edges passing two\n",
    "cells on each axis (moving in directions (2,1) (1,2), (-1,2), etc.) can\n",
    "be added to the graph. The drawback of adding additional edges is that\n",
    "more edges must be checked for collision when constructing the graph.\n",
    "\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:Grid8](figures/planning/grid8.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:Grid8\">Figure 6</a>.\n",
    "Searching with 8-connected grid points allows the planner to compute\n",
    "slightly shorter paths.\n",
    "    </div>\n",
    "\n",
    "****************\n",
    "\n",
    "Techniques that address these problems include the Any-Angle A\\* and the\n",
    "Fast Marching Method (FMM). Both of these methods perform the\n",
    "propagation of distances to a vertex's neighbor not only using the cost\n",
    "of the path along the edge, but also via off-edge paths. Any-Angle A\\*\n",
    "maintains information at each vertex about the source of straight line\n",
    "cost accumulation, while FMM approximates path costs via interpolation\n",
    "of the costs of any other explored vertices in adjoining grid cells. A\n",
    "complete description of these methods is beyond the scope of this book,\n",
    "but suffice to say the approximation quality of both methods improves\n",
    "with finer grids.\n",
    "\n",
    "\n",
    "\n",
    "### Visibility graph\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:VisibilityGraph](figures/planning/visibilitygraph.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:VisibilityGraph\">Figure 7</a>.\n",
    "Illustrating the visibility graph method. First, edges from each\n",
    "vertex to every other vertex are added if collision free. Next, the\n",
    "visibility graph is completed. Finally, a shortest path is produced via\n",
    "graph search.\n",
    "    </div>\n",
    "    \n",
    "****************\n",
    "\n",
    "The *visibility graph* method was one of the earliest motion planning\n",
    "algorithms and is also notable because it is a *complete, optimal*\n",
    "algorithm for polygonal obstacles. The idea of the visibility graph is\n",
    "to construct a graph whose vertices are the start, goal, and all\n",
    "obstacle vertices, and the edges consist of all possible collision-free\n",
    "line segments and obstacle edges. As a result, the solution paths will\n",
    "pass directly through obstacle corners.  Pseudocode for the basic visibility graph method is given below.\n",
    "\n",
    "*************\n",
    "<a name=\"alg:VisibilityGraph\"></a>\n",
    "**Algorithm Visibility-Graph**\n",
    "\n",
    "1. Let $V \\gets \\{ s, g \\}$ and all obstacle vertices.\n",
    "2. $E \\gets \\{ \\}$.\n",
    "3. **for** all pairs of distinct vertices $u, v \\in V$\n",
    "4. &nbsp;&nbsp;&nbsp;**if** $\\overline{uv}$ is an obstacle edge\n",
    "5. &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;Add $(u,v)$ to $E$.\n",
    "6. &nbsp;&nbsp;&nbsp;**else if** $\\overline{uv}$ is collision free\n",
    "7. &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;Add $(u,v)$ to $E$.\n",
    "8. Search $G = (V,E)$, with Cartesian distance as the edge cost, to connect $s$ and $g$.\n",
    "9. **return** the path if one is found.\n",
    "\n",
    "*************\n",
    "\n",
    "The number of iterations of Line 3 is\n",
    "O($n^2$) where $n$ is the number of obstacle vertices. Line 6 requires\n",
    "collision checking an edge with all other obstacle edges, which is an\n",
    "O($n$) operation. Overall, this brute-force construction visibility\n",
    "graph is constructed in O($n^3$) time. Proving the correctness and\n",
    "optimality of this planner is left as an exercise.\n",
    "\n",
    "Because $n$ may be quite large, e.g., in the hundreds or thousands, it\n",
    "may be fruitful to reduce the computational complexity of this\n",
    "algorithm. First, we can observe that if two convex obstacles have many\n",
    "intermediate vertices, most of the possible edges between them cannot be\n",
    "a part of an optimal path. Only the edges connecting obstacle tangents\n",
    "--- that is, an edge such that the prior and next obstacle vertex are on\n",
    "the same side of the edge --- need be checked for collision. Second, we\n",
    "can check for collisions between related edges in a more efficient way.\n",
    "\n",
    "One method for doing so is known as the rotational sweep. The rotational\n",
    "sweep methods collision checks all outgoing edges from a given vertex\n",
    "$u$ in $O(n \\log n)$ time by tracking the closest obstacle edge as a ray\n",
    "centered at $u$ sweeps around the full circle. The procedure is as\n",
    "follows:\n",
    "\n",
    "1.  Sort all vertices around $u$ in order of increasing rotational\n",
    "    angle. Ties are broken by closest distance. $O(n \\log n)$ time.\n",
    "\n",
    "2.  For the vertex $v$ with minimum angle, perform a collision check\n",
    "    with the infinite ray from $u$ toward $v$. Order all of the edges\n",
    "    $I = (e_1,\\ldots,e_k)$ intersected by the ray by order of increasing\n",
    "    distance. If $v$ is on the closest edge, add the edge $(u,v)$ to\n",
    "    $E$. $O(n + log n)$ time.\n",
    "\n",
    "3.  Proceed to the next vertex $w$ in the sorted list. If $w$ is the end\n",
    "    of edge $e_1$, add $(u,w)$ to $E$ and remove $e_1$ from $I$. If it\n",
    "    ends any other edge $e_k \\in I$, remove it from $I$. If $w$ is the\n",
    "    start of any edge $e \\notin I$, then add it to $I$ in order of\n",
    "    intersection distance. With binary search to identify edges in $I$,\n",
    "    this takes $O(\\log n)$ time.\n",
    "\n",
    "4.  Repeat Step 3 until all vertices are visited.\n",
    "\n",
    "Overall, the rotational sweep method constructs the visibility graph in $O(n^2 \\log n)$ time, since the above procedure must be repeated for each of the $n$ vertices.\n",
    "\n",
    "Cell decomposition\n",
    "------------------\n",
    "\n",
    "The class of *cell decomposition* methods differs from the above\n",
    "techniques in that the graph does not characterize a network of\n",
    "configurations, but rather the connectivity between free-space regions\n",
    "that meet at their boundary. So, once a cell decomposition is created,\n",
    "we can identify the cells containing the start and goal configurations\n",
    "and then search the graph to find a sequence of cells that contains a\n",
    "feasible path.\n",
    "\n",
    "### Trapezoidal decomposition\n",
    "\n",
    "One of the simplest cell-decomposition methods is the *trapezoidal\n",
    "decomposition*. This method divides free-space into trapezoids by\n",
    "imagining vertical upper and lower edges emanating from each obstacle\n",
    "vertex. The remaining cells are trapezoids and triangles, which are\n",
    "degenerate trapezoids with one edge of length zero. Each cell that\n",
    "borders another with a vertical line can be connected together with an\n",
    "edge in the graph. Because each cell is convex, any line connecting the\n",
    "left and right edges of the cell is also in free space.\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:TrapezoidalDecomposition](figures/planning/trapezoidal.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:Trapezoidal\">Figure 8</a>.\n",
    "Illustrating the trapezoidal decomposition method. The division of free space into trapezoids and triangles creates a decomposition of the space into convex regions, connected by their vertical boundaries.  More useful for planning is the boundary graph, where nodes are midpoints of the vertical boundaries of each trapezoid, and edges connect any nodes touching the same trapezoid. The start and goal locations can be connected to the graph by identifying which trapezoid in which they lie, and connecting the vertex to each edge bordering the trapezoid.\n",
    "    </div>\n",
    "    \n",
    "****************\n",
    "\n",
    "To create a trapezoidal decomposition, a *sweep line algorithm* can be used. \n",
    "This method imagines a vertical line passing between vertices from\n",
    "left to right, and cells are output incrementally. First we order all of the\n",
    "obstacle vertices in increasing $x$ coordinate. Ties are broken by $y$ coordinate.  This approach is known as *lexicographical order*, in which $(x,y) \\prec (x^\\prime,y^\\prime)$ iff either $x < x^\\prime$, or ($x=x^\\prime$ and $y<y^\\prime$).  Let us assume this order is $v_1,\\ldots,v_n$, with $v_i=(x_i,y_i)$.\n",
    "\n",
    "The algorithm proceeds by moving the sweep line from $v_1$ to $v_2$, $v_2$ to $v_3$, and so on. At every vertex $(x_i,y_i)$, the algorithm maintains an *invariant* that all free-space segments through the vertical line passing through $x_i$ are maintained in a list $L$.  Each segment is an interval $[a,b]$, and each endpoint of the interval stores the edge to which it belongs (i.e., $e_a$, $e_b$).  Each interval is sorted in terms of increasing y coordinate.  Let's assume that the free space is bounded. In this case, we initialize $L$ with the interval $[y_1,y_1]$ with endpoints associated with the edges emanating from the bottom and top of $v_1$, respectively.  \n",
    "\n",
    "Proceeding to the next vertex, one of three events may happen. 1) the next vertex may end *one* of the edges in $L$, simply *continuing* on to another cell, 2) the next vertex may *split* an\n",
    "existing cell, 3) the next vertex may *birth* a new cell, or 4) the next vertex may end *two* of the edges in $L$, causing two cells to\n",
    "*merge*.  Each operation modifies $L$ and outputs at most one cell.\n",
    "- *Continue*: output one cell either above or below the ended edge, remove that edge from $L$ and\n",
    "then insert the next edge in the same place as the old one. \n",
    "- *Split*: identify the location in $L$ into which the two new edges should be inserted.  A cell is outputted, bounded by the two edges surrounding the insertion position, and the two new edges are inserted there.\n",
    "- *Birth*: the vertex arises from within an obstacle. An singleton interval is added to $L$, with edges emanating above and below the vertex.\n",
    "- *Merge*: output the cell bounded below and above by the ended edges, and remove the edges from $L$. \n",
    "\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:SweepLine](figures/planning/sweep-line.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:SweepLine\">Figure 9</a>.\n",
    "Illustrating the types of events that can occur when a sweep line meets a vertex: (a) continue, (b) split, (c) birth, (d) merge.  The sweep line passes from left to right.  Blue edges are those on the sweep line that are unchanged; red edges are deleted; green edges are added.\n",
    "    </div>\n",
    "    \n",
    "****************\n",
    "\n",
    "This repeats until all vertices are processed. To maintain the\n",
    "connectivity of the cell decomposition, we can remember the rightmost\n",
    "cell added above or below each edge, and when a new cell is created, it is\n",
    "attached to the previous cell associated with that edge, and the\n",
    "rightmost cell is changed to the new cell.  (If the free space is unbounded, we produce an unbounded trapezoid to the left of the first vertex and to the right of the last vertex.)\n",
    "\n",
    "Note that there are a fair bit of bookkeeping and technical details required to implement this properly, e.g., to trace the boundary of the free space, determine the event type, and maintain the connectivity of the decomposition. But we can still establish the key computational bottlenecks.  First, we must sort the points in lexicographic order, which takes time $O(n \\log n)$.  The sweep line algorithm passes through $n$ points, and either a continue, split, or merge operation must be performed for each point. To look up the interval in which the new point is located takes $O(\\log n)$ time using bisection, and the update and cell creation steps take O(1) time.  Overall, the running time is $O(n \\log n)$.\n",
    "\n",
    "To find a path given a trapezoidal decomposition, it suffices to find the cells in which the start and goal are located, then search for a path containing the start and goal.  The continuous path is constructed by connecting the midpoints between each cell. Because each path segment is completely contained within the cell, and because trapezoids are convex, the path is guaranteed to be feasible.  Hence, the trapezoidal decomposition algorithm is complete but not optimal.\n",
    "Simple modifications of the vertical coordinates\n",
    " --- straightening the path when possible --- can be made to find the\n",
    "shortest path passing through the cells produced by the algorithm.  However, the sequence of cells may indeed miss the true shortest path.\n",
    "\n",
    "### Approximate cell decomposition\n",
    "\n",
    "Exact cell decomposition algorithms have been extended to 3D spaces with polyhedral obstacles, but in general require sophisticated geometric reasoning about how the free space is cut into convex polyhedra.  An alternative technique is *approximate cell decomposition*, in which we do not worry about creating a decomposition of the true free space, but rather create cells that are contained in the free space.\n",
    "\n",
    "One possible approach is that of an *octree*, which progressively subdivides the space into progressively smaller cubes until it can be determined that 1) a cube is *free*, i.e., completely within free space, 2) a cube is *closed*, i.e., completely inside an obstacle, or 3) a cube is smaller than a given resolution.  If a cube is neither free nor closed, it is *mixed*, and will be subdivided if it is larger than that resolution. An octree is constructed recursively, starting with a box $B_0$ that is know to contain the free space.  It proceeds by recursion on all boxes at level $i$. If a box is found to be mixed, then it is subdivided along each axis, which gives 8 child cubes (and hence the oct- prefix).\n",
    "\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:SweepLine](figures/planning/octree.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:Octree\">Figure 10</a>.\n",
    "An octree cell decomposition progressively divides an initial bounding cube $B_0$ into smaller cubes $B_{1a}$--$B_{1h}$.  A cube does not need to be subdivided if it is completely within the free space, or if it is completely contained within obstacles.  The right figure shows two levels of subdivision, with free cubes in white, obstacle cubes darkly shaded, and mixed cubes lightly shaded.\n",
    "    </div>\n",
    "    \n",
    "****************\n",
    "\n",
    "Some more details are warranted on the collision checking step.  Suppose that obstacles are represented by triangle meshes. Then, if any triangle in the mesh overlaps the box, then the box is mixed.  Otherwise, the box is either free or closed.  It is somewhat difficult to tell whether the box is contained entirely inside an obstacle, but this case can be more or less safely ignored --- if our decomposition only contains free or closed cells, it cannot be the case that any free cell will be connected to any closed cell.\n",
    "\n",
    "Once the octree is constructed, it is a matter of bookeeping to connect each non-mixed cell to its non-mixed neighbors, because on each of the 6 faces of a cell, the neighboring cell(s) may be at a finer level or a coarser level.  In this decomposition, if two free cells are connected, then there is certainly a free space path between them.  However, if two free cells are not connected, it is not certain whether a free space path exists.  Like grid search, this is a resolution complete method, because if the minimum resolution shrinks below a threshold (based on the clearance), then any free path connecting two points will correspond to a sequence of cells in the decomposition.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extensions to planar robots with geometry\n",
    "-----------------------------------------\n",
    "\n",
    "Now let us consider the robot to have some geometry, and allow the robot\n",
    "to translate and rotate in the plane. We will show that if we were to\n",
    "convert the workspace obstacles into C-space obstacles, then we can\n",
    "*directly* apply the techniques for point robots described above! This\n",
    "forms the basis of most planar robot motion planning techniques. This\n",
    "section will also describe how to handle rotations and more realistic\n",
    "motion constraints.\n",
    "\n",
    "### C-space obstacles\n",
    "\n",
    "For each obstacle $O$ in the workspace, there exists a corresponding set\n",
    "$\\mathcal{C}O$ called the *C-obstacle* that contains all configurations\n",
    "in which the obstacle collides with the robot. In other words,\n",
    "$$\\mathcal{C}O = \\{ q  \\in \\mathcal{C} \\,|\\, R(q)\\cap O \\neq \\emptyset \\}.$$\n",
    "The forbidden region can then be stated as the *union* of all\n",
    "C-obstacles:\n",
    "$$\\mathcal{C} \\setminus \\mathcal{F} = \\bigcup_{O \\in E} \\mathcal{C}O.$$\n",
    "But can each $\\mathcal{C}O$ be computed? Certainly this may be a\n",
    "nontrivial problem, particularly when $dim(\\mathcal{C})$ is large,\n",
    "because it is not even clear how to represent a high dimensional set. We\n",
    "show that in some cases, we can compute C-obstacles, and in others, it\n",
    "is worth leaving a C-obstacle purely as an element of thought.\n",
    "\n",
    "### Planar translating disks\n",
    "\n",
    "For point-robots, determining a C-obstacle is trivial. If\n",
    "$\\mathcal{C} = \\mathbb{R}^2$, and the space occupied by the robot $R(q)$\n",
    "is simply the point $\\{ q \\}$, then the C-space obstacle $\\mathcal{C}O$\n",
    "corresponding to an obstacle $O \\subseteq \\mathbb{R}^2$ is simply\n",
    "$\\mathcal{C}O = O$ itself. Given obstacles $O_1,\\ldots,O_n$, the\n",
    "forbidden region is then simply the union $\\bigcup_{i=1}^n O_i$. If the\n",
    "obstacles overlap, we may calculate a representation of the boundary of\n",
    "the union using constructive solid geometry (CSG) operations.\n",
    "\n",
    "Let us now consider the case in which the robot is a translating disk\n",
    "with radius $r$. The configuration $q$ denotes the translation of the\n",
    "robot with respect to some reference frame, and without loss of\n",
    "generality we choose this to have its origin at the center of the disk.\n",
    "Given some obstacle $O$ in workspace, the C-space obstacle\n",
    "$\\mathcal{C}O$ is the set of points such that *if the center of the disk\n",
    "is placed at that point, then the disk overlaps the obstacle.* This is\n",
    "equivalent to the set of points within radius $r$ of the obstacle:\n",
    "$$\\mathcal{C}O = \\{ q \\,|\\, D(q,r) \\cap O \\neq \\emptyset \\} = \\{ q \\,|\\, dist(q,O) \\leq r \\}$$\n",
    "where $D(q,r) \\subseteq \\mathbb{R}^2$ is the disk centered at $q$ with\n",
    "radius $r$. In other words, it is a uniformly \"fattened\" version of the\n",
    "workspace obstacle.\n",
    "\n",
    "****************\n",
    "\n",
    "![fig:DiskCObstacle](figures/planning/disk_cobstacle.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:DiskCObstacle\">Figure 11</a>.\n",
    "(a) For a disk robot and polygonal workspace obstacles, (b) the\n",
    "corresponding C-obstacles are polygons \"fattened\" by the robot's radius\n",
    "$r$. (Top) If the obstacle is convex, the C-obstacle is determined by\n",
    "tracing arcs at every vertex. (Bottom) If the obstacle is non-convex,\n",
    "the C-obstacle may contain\n",
    "holes.\n",
    "    </div>\n",
    "\n",
    "****************\n",
    "\n",
    "If $O$ is a convex polygon, then the boundary of the C-obstacle consists\n",
    "of a series of circular arcs and straight lines\n",
    "([Fig. 11](#fig:DiskCObstacle)). To construct the boundary, we may start\n",
    "with any vertex $u$ of the polygon, and place a point offset\n",
    "perpendicularly to its outgoing edge $\\overline{uv}$. Tracing a straight\n",
    "line parallel to that edge until it is perpendicular to the next vertex\n",
    "$v$, we construct one edge of the C-obstacle. The next segment is a\n",
    "circular arc of radius $r$, swept about $v$ until it hits the point\n",
    "perpendicular to $v$'s outgoing edge. This continues around the boundary\n",
    "of the polygon until the process returns to $u$.\n",
    "\n",
    "In the non-convex obstacle case, the boundary is not so straightforward\n",
    "to compute, because 1) for concave obstacle vertices, the straight edges\n",
    "meet prematurely creating a concave vertex of the C-obstacle, and 2) the\n",
    "boundary created by walking along the polygon in this manner may\n",
    "self-intersect and even create inner holes. To properly handle the case\n",
    "where holes exist requires some CSG-like techniques.\n",
    "\n",
    "To plan in the presence of C-obstacles with arcs, you could discretize\n",
    "the arcs into small polyhedral segments and use the techniques described\n",
    "above for polygons. Or, you could modify the algorithms described above\n",
    "to handle arcs directly. For example, a visibility graph with arcs would\n",
    "construct graph segments consisting of 1) straight lines along obstacle\n",
    "boundaries, 2) arcs along obstacle boundaries, or 3) straight lines that\n",
    "are tangent to two arcs.\n",
    "\n",
    "### Minkowski sums and differences\n",
    "\n",
    "We can generalize the construction of C-obstacles to general translating\n",
    "robots using the notion of a Minkowski difference. The *Minkowski sum*\n",
    "$\\oplus$ is a generalization of addition to be defined on sets of\n",
    "points. If $A$ and $B$ are sets, then $A \\oplus B$ is defined as the\n",
    "set:\n",
    "$$A \\oplus B \\equiv \\{ x + y \\,|\\, x\\in A \\text{ and }y\\in B\\}.$$\n",
    "Similarly, the Minkowski difference $\\ominus$ is defined as\n",
    "$$A \\ominus B \\equiv \\{ x - y \\,|\\, x\\in A \\text{ and }y\\in B\\}.$$\n",
    "\n",
    "If the reference frame of the robot is a shape $R_0$, then the volume\n",
    "occupied after translation $q$ is the set\n",
    "$$R(q) = \\{ x \\,|\\, x-q \\in R_0 \\}.$$\n",
    "If $P$ is a workspace\n",
    "obstacle, the the condition that $R(q) \\cap O \\neq \\emptyset$ requires\n",
    "that there exists some $x \\in \\mathbb{R}^2$ such that $x \\in R(q)$ and\n",
    "$x \\in O$. This is equivalent to the condition that:\n",
    "$$q \\in O \\ominus R_0.$$\n",
    "To see this, observe that if\n",
    "$q \\in O \\ominus R_0$, then there exists $x \\in O$ and $y \\in R_0$ such\n",
    "that $q = x - y$. In other words, $y = x-q \\in R_0$ implies that\n",
    "$x \\in R(q)$. As a result, constructing the C-obstacle is equivalent to\n",
    "compute the Minkowski difference of the object minus the robot's\n",
    "reference shape.\n",
    "\n",
    "As an example, consider a convex polygonal robot with reference\n",
    "$A=(a_1,\\ldots,a_m)$ and a convex polygonal obstacle\n",
    "$B = (b_1,\\ldots,b_n)$. The Minkowki sums which can be obtained by 1)\n",
    "flipping $A$ about the $x$ and $y$ axes to obtain $-A$, 2) tracing the\n",
    "flipped shape about the edges of $B$, and 3) determining the outer edges\n",
    "of the traced paths.\n",
    "\n",
    "In the convex case, the C-obstacle can be shown to be convex with at\n",
    "most $m+n$ edges. One brute-force way to compute it is to calculate all\n",
    "extrema $a_i + b_j$, $i=1,\\ldots,m$ and $j=1,\\ldots,n$, and then\n",
    "computing the convex hull. With an appropriate convex hull algorithm,\n",
    "this can take $O(mn \\log mn)$ time. There is however an optimal\n",
    "$O(m + n)$ algorithm that constructs the Minkowski sum. Briefly, this\n",
    "technique marches about the edges of each polygon and outputs an\n",
    "extremal vertex for each vertex of either polygon encountered in CCW\n",
    "order. In the general non-convex case, however, the Minkowski sum may\n",
    "have $O((mn)^2)$ complexity, and may have holes.\n",
    "\n",
    "### C-obstacles for rotational motion\n",
    "\n",
    "C-obstacles for rotational motion are much more complex. Consider, for\n",
    "example, a translating and rotating convex polygon with polygonal\n",
    "obstacles. The C-space is SE(2) and consists of configurations\n",
    "$q=(x,y,\\theta)$. Imagine it as a volume with $\\theta \\in [0,2\\pi)$ the\n",
    "vertical axis.\n",
    "\n",
    "Then, for any fixed rotation $\\theta$, if we were to consider only the\n",
    "translation components of the configuration, this would be a horizontal\n",
    "slice through configuration space. The slice of a C-obstacle at height\n",
    "$\\theta$ can be determined by the Minkowski difference of the obstacle\n",
    "and the robot reference polygon rotated by angle $\\theta$:\n",
    "$$\\{ (x,y) \\,|\\, (x,y,\\theta) \\in \\mathcal{C}O \\} = O \\ominus R(0,0,\\theta)$$\n",
    "where $R(0,0,\\theta)$ is the rotated robot reference polygon. If $O$ is convex,\n",
    "then this slice is also a convex polygon.\n",
    "\n",
    "However, as we slide $\\theta$ slightly, the vertices of each slice\n",
    "rotate along a helix. At some points along the range $[0,2\\pi)$, these\n",
    "helical paths will merge or split as different combinations of obstacle\n",
    "and robot vertices enter and leave the boundary of the Minkowski\n",
    "difference. This causes the C-obstacle to become a relatively complex\n",
    "shape. \n",
    "\n",
    "The figure below shows a triangular robot $A$ and a box obstacle $B$. At the\n",
    "current orientation, the C-obstacle is also a convex polygon (left).  But if the\n",
    "robot were to rotate, the orientation can be considered a Z direction in a 3D plot.\n",
    "The C-obstacle is now a 3D region, which is a spiraling, undulating volume, but\n",
    "whose slices in the horizontal axis are\n",
    "convex polygons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       "  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"595.928091pt\" height=\"308.278125pt\" viewBox=\"0 0 595.928091 308.278125\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n",
       " <metadata>\n",
       "  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n",
       "   <cc:Work>\n",
       "    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n",
       "    <dc:date>2023-08-27T23:46:30.311582</dc:date>\n",
       "    <dc:format>image/svg+xml</dc:format>\n",
       "    <dc:creator>\n",
       "     <cc:Agent>\n",
       "      <dc:title>Matplotlib v3.7.1, https://matplotlib.org/</dc:title>\n",
       "     </cc:Agent>\n",
       "    </dc:creator>\n",
       "   </cc:Work>\n",
       "  </rdf:RDF>\n",
       " </metadata>\n",
       " <defs>\n",
       "  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n",
       " </defs>\n",
       " <g id=\"figure_1\">\n",
       "  <g id=\"patch_1\">\n",
       "   <path d=\"M 0 308.278125 \n",
       "L 595.928091 308.278125 \n",
       "L 595.928091 0 \n",
       "L 0 0 \n",
       "z\n",
       "\" style=\"fill: #ffffff\"/>\n",
       "  </g>\n",
       "  <g id=\"axes_1\">\n",
       "   <g id=\"patch_2\">\n",
       "    <path d=\"M 28.942188 284.4 \n",
       "L 282.578551 284.4 \n",
       "L 282.578551 7.2 \n",
       "L 28.942188 7.2 \n",
       "z\n",
       "\" style=\"fill: #ffffff\"/>\n",
       "   </g>\n",
       "   <g id=\"PathCollection_1\">\n",
       "    <defs>\n",
       "     <path id=\"m8152d2cc88\" d=\"M 0 3 \n",
       "C 0.795609 3 1.55874 2.683901 2.12132 2.12132 \n",
       "C 2.683901 1.55874 3 0.795609 3 0 \n",
       "C 3 -0.795609 2.683901 -1.55874 2.12132 -2.12132 \n",
       "C 1.55874 -2.683901 0.795609 -3 0 -3 \n",
       "C -0.795609 -3 -1.55874 -2.683901 -2.12132 -2.12132 \n",
       "C -2.683901 -1.55874 -3 -0.795609 -3 0 \n",
       "C -3 0.795609 -2.683901 1.55874 -2.12132 2.12132 \n",
       "C -1.55874 2.683901 -0.795609 3 0 3 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p0d04d6844a)\">\n",
       "     <use xlink:href=\"#m8152d2cc88\" x=\"69.293427\" y=\"203.444628\" style=\"stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_1\">\n",
       "    <g id=\"xtick_1\">\n",
       "     <g id=\"line2d_1\">\n",
       "      <defs>\n",
       "       <path id=\"m338f2c6537\" d=\"M 0 0 \n",
       "L 0 3.5 \n",
       "\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use xlink:href=\"#m338f2c6537\" x=\"69.293427\" y=\"284.4\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_1\">\n",
       "      <!-- 0 -->\n",
       "      <g transform=\"translate(66.112177 298.998438) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \n",
       "Q 1547 4250 1301 3770 \n",
       "Q 1056 3291 1056 2328 \n",
       "Q 1056 1369 1301 889 \n",
       "Q 1547 409 2034 409 \n",
       "Q 2525 409 2770 889 \n",
       "Q 3016 1369 3016 2328 \n",
       "Q 3016 3291 2770 3770 \n",
       "Q 2525 4250 2034 4250 \n",
       "z\n",
       "M 2034 4750 \n",
       "Q 2819 4750 3233 4129 \n",
       "Q 3647 3509 3647 2328 \n",
       "Q 3647 1150 3233 529 \n",
       "Q 2819 -91 2034 -91 \n",
       "Q 1250 -91 836 529 \n",
       "Q 422 1150 422 2328 \n",
       "Q 422 3509 836 4129 \n",
       "Q 1250 4750 2034 4750 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_2\">\n",
       "     <g id=\"line2d_2\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m338f2c6537\" x=\"126.938055\" y=\"284.4\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_2\">\n",
       "      <!-- 2 -->\n",
       "      <g transform=\"translate(123.756805 298.998438) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \n",
       "L 3431 531 \n",
       "L 3431 0 \n",
       "L 469 0 \n",
       "L 469 531 \n",
       "Q 828 903 1448 1529 \n",
       "Q 2069 2156 2228 2338 \n",
       "Q 2531 2678 2651 2914 \n",
       "Q 2772 3150 2772 3378 \n",
       "Q 2772 3750 2511 3984 \n",
       "Q 2250 4219 1831 4219 \n",
       "Q 1534 4219 1204 4116 \n",
       "Q 875 4013 500 3803 \n",
       "L 500 4441 \n",
       "Q 881 4594 1212 4672 \n",
       "Q 1544 4750 1819 4750 \n",
       "Q 2544 4750 2975 4387 \n",
       "Q 3406 4025 3406 3419 \n",
       "Q 3406 3131 3298 2873 \n",
       "Q 3191 2616 2906 2266 \n",
       "Q 2828 2175 2409 1742 \n",
       "Q 1991 1309 1228 531 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_3\">\n",
       "     <g id=\"line2d_3\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m338f2c6537\" x=\"184.582683\" y=\"284.4\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_3\">\n",
       "      <!-- 4 -->\n",
       "      <g transform=\"translate(181.401433 298.998438) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \n",
       "L 825 1625 \n",
       "L 2419 1625 \n",
       "L 2419 4116 \n",
       "z\n",
       "M 2253 4666 \n",
       "L 3047 4666 \n",
       "L 3047 1625 \n",
       "L 3713 1625 \n",
       "L 3713 1100 \n",
       "L 3047 1100 \n",
       "L 3047 0 \n",
       "L 2419 0 \n",
       "L 2419 1100 \n",
       "L 313 1100 \n",
       "L 313 1709 \n",
       "L 2253 4666 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_4\">\n",
       "     <g id=\"line2d_4\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m338f2c6537\" x=\"242.227311\" y=\"284.4\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_4\">\n",
       "      <!-- 6 -->\n",
       "      <g transform=\"translate(239.046061 298.998438) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \n",
       "Q 1688 2584 1439 2293 \n",
       "Q 1191 2003 1191 1497 \n",
       "Q 1191 994 1439 701 \n",
       "Q 1688 409 2113 409 \n",
       "Q 2538 409 2786 701 \n",
       "Q 3034 994 3034 1497 \n",
       "Q 3034 2003 2786 2293 \n",
       "Q 2538 2584 2113 2584 \n",
       "z\n",
       "M 3366 4563 \n",
       "L 3366 3988 \n",
       "Q 3128 4100 2886 4159 \n",
       "Q 2644 4219 2406 4219 \n",
       "Q 1781 4219 1451 3797 \n",
       "Q 1122 3375 1075 2522 \n",
       "Q 1259 2794 1537 2939 \n",
       "Q 1816 3084 2150 3084 \n",
       "Q 2853 3084 3261 2657 \n",
       "Q 3669 2231 3669 1497 \n",
       "Q 3669 778 3244 343 \n",
       "Q 2819 -91 2113 -91 \n",
       "Q 1303 -91 875 529 \n",
       "Q 447 1150 447 2328 \n",
       "Q 447 3434 972 4092 \n",
       "Q 1497 4750 2381 4750 \n",
       "Q 2619 4750 2861 4703 \n",
       "Q 3103 4656 3366 4563 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-36\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_2\">\n",
       "    <g id=\"ytick_1\">\n",
       "     <g id=\"line2d_5\">\n",
       "      <defs>\n",
       "       <path id=\"m670ef368e1\" d=\"M 0 0 \n",
       "L -3.5 0 \n",
       "\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use xlink:href=\"#m670ef368e1\" x=\"28.942188\" y=\"261.089256\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_5\">\n",
       "      <!-- −2 -->\n",
       "      <g transform=\"translate(7.2 264.888475) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \n",
       "L 4684 2272 \n",
       "L 4684 1741 \n",
       "L 678 1741 \n",
       "L 678 2272 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use xlink:href=\"#DejaVuSans-32\" x=\"83.789062\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_2\">\n",
       "     <g id=\"line2d_6\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m670ef368e1\" x=\"28.942188\" y=\"203.444628\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_6\">\n",
       "      <!-- 0 -->\n",
       "      <g transform=\"translate(15.579688 207.243847) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_3\">\n",
       "     <g id=\"line2d_7\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m670ef368e1\" x=\"28.942188\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_7\">\n",
       "      <!-- 2 -->\n",
       "      <g transform=\"translate(15.579688 149.599219) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_4\">\n",
       "     <g id=\"line2d_8\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m670ef368e1\" x=\"28.942188\" y=\"88.155372\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_8\">\n",
       "      <!-- 4 -->\n",
       "      <g transform=\"translate(15.579688 91.954591) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_5\">\n",
       "     <g id=\"line2d_9\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m670ef368e1\" x=\"28.942188\" y=\"30.510744\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_9\">\n",
       "      <!-- 6 -->\n",
       "      <g transform=\"translate(15.579688 34.309963) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-36\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"line2d_10\">\n",
       "    <path d=\"M 40.471113 203.444628 \n",
       "L 98.115741 203.444628 \n",
       "L 69.293427 160.211157 \n",
       "L 40.471113 203.444628 \n",
       "\" clip-path=\"url(#p0d04d6844a)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_11\">\n",
       "    <path d=\"M 155.760369 145.8 \n",
       "L 242.227311 145.8 \n",
       "L 242.227311 88.155372 \n",
       "L 155.760369 88.155372 \n",
       "L 155.760369 145.8 \n",
       "\" clip-path=\"url(#p0d04d6844a)\" style=\"fill: none; stroke: #ff7f0e; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_12\">\n",
       "    <path d=\"M 155.760369 189.033471 \n",
       "L 242.227311 189.033471 \n",
       "L 271.049626 145.8 \n",
       "L 271.049626 88.155372 \n",
       "L 184.582683 88.155372 \n",
       "L 126.938055 88.155372 \n",
       "L 126.938055 145.8 \n",
       "L 155.760369 189.033471 \n",
       "L 155.760369 189.033471 \n",
       "\" clip-path=\"url(#p0d04d6844a)\" style=\"fill: none; stroke: #2ca02c; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_3\">\n",
       "    <path d=\"M 28.942188 284.4 \n",
       "L 28.942188 7.2 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_4\">\n",
       "    <path d=\"M 282.578551 284.4 \n",
       "L 282.578551 7.2 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_5\">\n",
       "    <path d=\"M 28.942188 284.4 \n",
       "L 282.578551 284.4 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_6\">\n",
       "    <path d=\"M 28.942188 7.2 \n",
       "L 282.578551 7.2 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"legend_1\">\n",
       "    <g id=\"patch_7\">\n",
       "     <path d=\"M 164.544176 73.9125 \n",
       "L 275.578551 73.9125 \n",
       "Q 277.578551 73.9125 277.578551 71.9125 \n",
       "L 277.578551 14.2 \n",
       "Q 277.578551 12.2 275.578551 12.2 \n",
       "L 164.544176 12.2 \n",
       "Q 162.544176 12.2 162.544176 14.2 \n",
       "L 162.544176 71.9125 \n",
       "Q 162.544176 73.9125 164.544176 73.9125 \n",
       "z\n",
       "\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n",
       "    </g>\n",
       "    <g id=\"PathCollection_2\">\n",
       "     <g>\n",
       "      <use xlink:href=\"#m8152d2cc88\" x=\"176.544176\" y=\"21.173438\" style=\"stroke: #000000\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"text_10\">\n",
       "     <!-- Reference point -->\n",
       "     <g transform=\"translate(194.544176 23.798438) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-52\" d=\"M 2841 2188 \n",
       "Q 3044 2119 3236 1894 \n",
       "Q 3428 1669 3622 1275 \n",
       "L 4263 0 \n",
       "L 3584 0 \n",
       "L 2988 1197 \n",
       "Q 2756 1666 2539 1819 \n",
       "Q 2322 1972 1947 1972 \n",
       "L 1259 1972 \n",
       "L 1259 0 \n",
       "L 628 0 \n",
       "L 628 4666 \n",
       "L 2053 4666 \n",
       "Q 2853 4666 3247 4331 \n",
       "Q 3641 3997 3641 3322 \n",
       "Q 3641 2881 3436 2590 \n",
       "Q 3231 2300 2841 2188 \n",
       "z\n",
       "M 1259 4147 \n",
       "L 1259 2491 \n",
       "L 2053 2491 \n",
       "Q 2509 2491 2742 2702 \n",
       "Q 2975 2913 2975 3322 \n",
       "Q 2975 3731 2742 3939 \n",
       "Q 2509 4147 2053 4147 \n",
       "L 1259 4147 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \n",
       "L 3597 1613 \n",
       "L 953 1613 \n",
       "Q 991 1019 1311 708 \n",
       "Q 1631 397 2203 397 \n",
       "Q 2534 397 2845 478 \n",
       "Q 3156 559 3463 722 \n",
       "L 3463 178 \n",
       "Q 3153 47 2828 -22 \n",
       "Q 2503 -91 2169 -91 \n",
       "Q 1331 -91 842 396 \n",
       "Q 353 884 353 1716 \n",
       "Q 353 2575 817 3079 \n",
       "Q 1281 3584 2069 3584 \n",
       "Q 2775 3584 3186 3129 \n",
       "Q 3597 2675 3597 1894 \n",
       "z\n",
       "M 3022 2063 \n",
       "Q 3016 2534 2758 2815 \n",
       "Q 2500 3097 2075 3097 \n",
       "Q 1594 3097 1305 2825 \n",
       "Q 1016 2553 972 2059 \n",
       "L 3022 2063 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \n",
       "L 2375 4384 \n",
       "L 1825 4384 \n",
       "Q 1516 4384 1395 4259 \n",
       "Q 1275 4134 1275 3809 \n",
       "L 1275 3500 \n",
       "L 2222 3500 \n",
       "L 2222 3053 \n",
       "L 1275 3053 \n",
       "L 1275 0 \n",
       "L 697 0 \n",
       "L 697 3053 \n",
       "L 147 3053 \n",
       "L 147 3500 \n",
       "L 697 3500 \n",
       "L 697 3744 \n",
       "Q 697 4328 969 4595 \n",
       "Q 1241 4863 1831 4863 \n",
       "L 2375 4863 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \n",
       "Q 2534 3019 2420 3045 \n",
       "Q 2306 3072 2169 3072 \n",
       "Q 1681 3072 1420 2755 \n",
       "Q 1159 2438 1159 1844 \n",
       "L 1159 0 \n",
       "L 581 0 \n",
       "L 581 3500 \n",
       "L 1159 3500 \n",
       "L 1159 2956 \n",
       "Q 1341 3275 1631 3429 \n",
       "Q 1922 3584 2338 3584 \n",
       "Q 2397 3584 2469 3576 \n",
       "Q 2541 3569 2628 3553 \n",
       "L 2631 2963 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \n",
       "L 3513 0 \n",
       "L 2938 0 \n",
       "L 2938 2094 \n",
       "Q 2938 2591 2744 2837 \n",
       "Q 2550 3084 2163 3084 \n",
       "Q 1697 3084 1428 2787 \n",
       "Q 1159 2491 1159 1978 \n",
       "L 1159 0 \n",
       "L 581 0 \n",
       "L 581 3500 \n",
       "L 1159 3500 \n",
       "L 1159 2956 \n",
       "Q 1366 3272 1645 3428 \n",
       "Q 1925 3584 2291 3584 \n",
       "Q 2894 3584 3203 3211 \n",
       "Q 3513 2838 3513 2113 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \n",
       "L 3122 2828 \n",
       "Q 2878 2963 2633 3030 \n",
       "Q 2388 3097 2138 3097 \n",
       "Q 1578 3097 1268 2742 \n",
       "Q 959 2388 959 1747 \n",
       "Q 959 1106 1268 751 \n",
       "Q 1578 397 2138 397 \n",
       "Q 2388 397 2633 464 \n",
       "Q 2878 531 3122 666 \n",
       "L 3122 134 \n",
       "Q 2881 22 2623 -34 \n",
       "Q 2366 -91 2075 -91 \n",
       "Q 1284 -91 818 406 \n",
       "Q 353 903 353 1747 \n",
       "Q 353 2603 823 3093 \n",
       "Q 1294 3584 2113 3584 \n",
       "Q 2378 3584 2631 3529 \n",
       "Q 2884 3475 3122 3366 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \n",
       "L 1159 -1331 \n",
       "L 581 -1331 \n",
       "L 581 3500 \n",
       "L 1159 3500 \n",
       "L 1159 2969 \n",
       "Q 1341 3281 1617 3432 \n",
       "Q 1894 3584 2278 3584 \n",
       "Q 2916 3584 3314 3078 \n",
       "Q 3713 2572 3713 1747 \n",
       "Q 3713 922 3314 415 \n",
       "Q 2916 -91 2278 -91 \n",
       "Q 1894 -91 1617 61 \n",
       "Q 1341 213 1159 525 \n",
       "z\n",
       "M 3116 1747 \n",
       "Q 3116 2381 2855 2742 \n",
       "Q 2594 3103 2138 3103 \n",
       "Q 1681 3103 1420 2742 \n",
       "Q 1159 2381 1159 1747 \n",
       "Q 1159 1113 1420 752 \n",
       "Q 1681 391 2138 391 \n",
       "Q 2594 391 2855 752 \n",
       "Q 3116 1113 3116 1747 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \n",
       "Q 1497 3097 1228 2736 \n",
       "Q 959 2375 959 1747 \n",
       "Q 959 1119 1226 758 \n",
       "Q 1494 397 1959 397 \n",
       "Q 2419 397 2687 759 \n",
       "Q 2956 1122 2956 1747 \n",
       "Q 2956 2369 2687 2733 \n",
       "Q 2419 3097 1959 3097 \n",
       "z\n",
       "M 1959 3584 \n",
       "Q 2709 3584 3137 3096 \n",
       "Q 3566 2609 3566 1747 \n",
       "Q 3566 888 3137 398 \n",
       "Q 2709 -91 1959 -91 \n",
       "Q 1206 -91 779 398 \n",
       "Q 353 888 353 1747 \n",
       "Q 353 2609 779 3096 \n",
       "Q 1206 3584 1959 3584 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \n",
       "L 1178 3500 \n",
       "L 1178 0 \n",
       "L 603 0 \n",
       "L 603 3500 \n",
       "z\n",
       "M 603 4863 \n",
       "L 1178 4863 \n",
       "L 1178 4134 \n",
       "L 603 4134 \n",
       "L 603 4863 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \n",
       "L 1172 3500 \n",
       "L 2356 3500 \n",
       "L 2356 3053 \n",
       "L 1172 3053 \n",
       "L 1172 1153 \n",
       "Q 1172 725 1289 603 \n",
       "Q 1406 481 1766 481 \n",
       "L 2356 481 \n",
       "L 2356 0 \n",
       "L 1766 0 \n",
       "Q 1100 0 847 248 \n",
       "Q 594 497 594 1153 \n",
       "L 594 3053 \n",
       "L 172 3053 \n",
       "L 172 3500 \n",
       "L 594 3500 \n",
       "L 594 4494 \n",
       "L 1172 4494 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-52\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-65\" x=\"64.982422\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-66\" x=\"126.505859\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-65\" x=\"161.710938\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-72\" x=\"223.234375\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-65\" x=\"262.097656\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-6e\" x=\"323.621094\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-63\" x=\"387\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-65\" x=\"441.980469\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-20\" x=\"503.503906\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-70\" x=\"535.291016\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-6f\" x=\"598.767578\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-69\" x=\"659.949219\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-6e\" x=\"687.732422\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-74\" x=\"751.111328\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_13\">\n",
       "     <path d=\"M 166.544176 34.976563 \n",
       "L 176.544176 34.976563 \n",
       "L 186.544176 34.976563 \n",
       "\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_11\">\n",
       "     <!-- A -->\n",
       "     <g transform=\"translate(194.544176 38.476563) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-41\" d=\"M 2188 4044 \n",
       "L 1331 1722 \n",
       "L 3047 1722 \n",
       "L 2188 4044 \n",
       "z\n",
       "M 1831 4666 \n",
       "L 2547 4666 \n",
       "L 4325 0 \n",
       "L 3669 0 \n",
       "L 3244 1197 \n",
       "L 1141 1197 \n",
       "L 716 0 \n",
       "L 50 0 \n",
       "L 1831 4666 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-41\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_14\">\n",
       "     <path d=\"M 166.544176 49.654688 \n",
       "L 176.544176 49.654688 \n",
       "L 186.544176 49.654688 \n",
       "\" style=\"fill: none; stroke: #ff7f0e; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_12\">\n",
       "     <!-- B -->\n",
       "     <g transform=\"translate(194.544176 53.154688) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-42\" d=\"M 1259 2228 \n",
       "L 1259 519 \n",
       "L 2272 519 \n",
       "Q 2781 519 3026 730 \n",
       "Q 3272 941 3272 1375 \n",
       "Q 3272 1813 3026 2020 \n",
       "Q 2781 2228 2272 2228 \n",
       "L 1259 2228 \n",
       "z\n",
       "M 1259 4147 \n",
       "L 1259 2741 \n",
       "L 2194 2741 \n",
       "Q 2656 2741 2882 2914 \n",
       "Q 3109 3088 3109 3444 \n",
       "Q 3109 3797 2882 3972 \n",
       "Q 2656 4147 2194 4147 \n",
       "L 1259 4147 \n",
       "z\n",
       "M 628 4666 \n",
       "L 2241 4666 \n",
       "Q 2963 4666 3353 4366 \n",
       "Q 3744 4066 3744 3513 \n",
       "Q 3744 3084 3544 2831 \n",
       "Q 3344 2578 2956 2516 \n",
       "Q 3422 2416 3680 2098 \n",
       "Q 3938 1781 3938 1306 \n",
       "Q 3938 681 3513 340 \n",
       "Q 3088 0 2303 0 \n",
       "L 628 0 \n",
       "L 628 4666 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-42\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_15\">\n",
       "     <path d=\"M 166.544176 64.332813 \n",
       "L 176.544176 64.332813 \n",
       "L 186.544176 64.332813 \n",
       "\" style=\"fill: none; stroke: #2ca02c; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_13\">\n",
       "     <!-- A - B -->\n",
       "     <g transform=\"translate(194.544176 67.832813) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-2d\" d=\"M 313 2009 \n",
       "L 1997 2009 \n",
       "L 1997 1497 \n",
       "L 313 1497 \n",
       "L 313 2009 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-41\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-20\" x=\"68.408203\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-2d\" x=\"100.195312\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-20\" x=\"136.279297\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-42\" x=\"168.066406\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"patch_8\">\n",
       "   <path d=\"M 333.305824 272.618182 \n",
       "L 586.942187 272.618182 \n",
       "L 586.942187 18.981818 \n",
       "L 333.305824 18.981818 \n",
       "z\n",
       "\" style=\"fill: #ffffff\"/>\n",
       "  </g>\n",
       "  <g id=\"pane3d_1\">\n",
       "   <g id=\"patch_9\">\n",
       "    <path d=\"M 463.551524 158.858473 \n",
       "L 577.226399 199.022045 \n",
       "L 580.751572 83.966158 \n",
       "L 463.551524 51.204813 \n",
       "\" style=\"fill: #f2f2f2; opacity: 0.5; stroke: #f2f2f2; stroke-linejoin: miter\"/>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"pane3d_2\">\n",
       "   <g id=\"patch_10\">\n",
       "    <path d=\"M 463.551524 158.858473 \n",
       "L 349.876649 199.022045 \n",
       "L 346.351476 83.966158 \n",
       "L 463.551524 51.204813 \n",
       "\" style=\"fill: #e6e6e6; opacity: 0.5; stroke: #e6e6e6; stroke-linejoin: miter\"/>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"pane3d_3\">\n",
       "   <g id=\"patch_11\">\n",
       "    <path d=\"M 463.551524 158.858473 \n",
       "L 349.876649 199.022045 \n",
       "L 463.551524 245.972978 \n",
       "L 577.226399 199.022045 \n",
       "\" style=\"fill: #ececec; opacity: 0.5; stroke: #ececec; stroke-linejoin: miter\"/>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"axis3d_1\">\n",
       "   <g id=\"line2d_16\">\n",
       "    <path d=\"M 577.226399 199.022045 \n",
       "L 463.551524 245.972978 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"text_14\">\n",
       "    <!-- x -->\n",
       "    <g transform=\"translate(542.893469 255.309842) scale(0.1 -0.1)\">\n",
       "     <defs>\n",
       "      <path id=\"DejaVuSans-78\" d=\"M 3513 3500 \n",
       "L 2247 1797 \n",
       "L 3578 0 \n",
       "L 2900 0 \n",
       "L 1881 1375 \n",
       "L 863 0 \n",
       "L 184 0 \n",
       "L 1544 1831 \n",
       "L 300 3500 \n",
       "L 978 3500 \n",
       "L 1906 2253 \n",
       "L 2834 3500 \n",
       "L 3513 3500 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "     </defs>\n",
       "     <use xlink:href=\"#DejaVuSans-78\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Line3DCollection_1\">\n",
       "    <path d=\"M 575.126765 199.889253 \n",
       "L 461.439305 159.604762 \n",
       "L 461.378583 51.812223 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 558.090774 206.925599 \n",
       "L 444.318801 165.653773 \n",
       "L 443.759234 56.737422 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 540.61848 214.142149 \n",
       "L 426.792322 171.846223 \n",
       "L 425.709776 61.782851 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 522.692906 221.545918 \n",
       "L 408.845254 178.187276 \n",
       "L 407.214266 66.952966 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 504.29618 229.144285 \n",
       "L 390.462274 184.682344 \n",
       "L 388.255961 72.252449 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 485.409479 236.945026 \n",
       "L 371.627305 191.33711 \n",
       "L 368.817273 77.686214 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 466.012965 244.956334 \n",
       "L 352.323469 198.157535 \n",
       "L 348.879707 83.259432 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "   </g>\n",
       "   <g id=\"xtick_5\">\n",
       "    <g id=\"line2d_17\">\n",
       "     <path d=\"M 574.146905 199.542045 \n",
       "L 577.090161 200.584971 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_15\">\n",
       "     <!-- 1 -->\n",
       "     <g transform=\"translate(582.365591 221.052514) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-31\" d=\"M 794 531 \n",
       "L 1825 531 \n",
       "L 1825 4091 \n",
       "L 703 3866 \n",
       "L 703 4441 \n",
       "L 1819 4666 \n",
       "L 2450 4666 \n",
       "L 2450 531 \n",
       "L 3481 531 \n",
       "L 3481 0 \n",
       "L 794 0 \n",
       "L 794 531 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-31\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_6\">\n",
       "    <g id=\"line2d_18\">\n",
       "     <path d=\"M 557.109295 206.569558 \n",
       "L 560.057459 207.639031 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_16\">\n",
       "     <!-- 2 -->\n",
       "     <g transform=\"translate(565.389649 228.290936) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_7\">\n",
       "    <g id=\"line2d_19\">\n",
       "     <path d=\"M 539.635621 213.776935 \n",
       "L 542.587979 214.873982 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_17\">\n",
       "     <!-- 3 -->\n",
       "     <g transform=\"translate(547.977074 235.715535) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \n",
       "Q 3050 2419 3304 2112 \n",
       "Q 3559 1806 3559 1356 \n",
       "Q 3559 666 3084 287 \n",
       "Q 2609 -91 1734 -91 \n",
       "Q 1441 -91 1130 -33 \n",
       "Q 819 25 488 141 \n",
       "L 488 750 \n",
       "Q 750 597 1062 519 \n",
       "Q 1375 441 1716 441 \n",
       "Q 2309 441 2620 675 \n",
       "Q 2931 909 2931 1356 \n",
       "Q 2931 1769 2642 2001 \n",
       "Q 2353 2234 1838 2234 \n",
       "L 1294 2234 \n",
       "L 1294 2753 \n",
       "L 1863 2753 \n",
       "Q 2328 2753 2575 2939 \n",
       "Q 2822 3125 2822 3475 \n",
       "Q 2822 3834 2567 4026 \n",
       "Q 2313 4219 1838 4219 \n",
       "Q 1578 4219 1281 4162 \n",
       "Q 984 4106 628 3988 \n",
       "L 628 4550 \n",
       "Q 988 4650 1302 4700 \n",
       "Q 1616 4750 1894 4750 \n",
       "Q 2613 4750 3031 4423 \n",
       "Q 3450 4097 3450 3541 \n",
       "Q 3450 3153 3228 2886 \n",
       "Q 3006 2619 2597 2516 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-33\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_8\">\n",
       "    <g id=\"line2d_20\">\n",
       "     <path d=\"M 521.708925 221.17117 \n",
       "L 524.664703 222.296872 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_18\">\n",
       "     <!-- 4 -->\n",
       "     <g transform=\"translate(530.110802 243.333587) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_9\">\n",
       "    <g id=\"line2d_21\">\n",
       "     <path d=\"M 503.311356 228.759627 \n",
       "L 506.269715 229.915121 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_19\">\n",
       "     <!-- 5 -->\n",
       "     <g transform=\"translate(511.772866 251.152753) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-35\" d=\"M 691 4666 \n",
       "L 3169 4666 \n",
       "L 3169 4134 \n",
       "L 1269 4134 \n",
       "L 1269 2991 \n",
       "Q 1406 3038 1543 3061 \n",
       "Q 1681 3084 1819 3084 \n",
       "Q 2600 3084 3056 2656 \n",
       "Q 3513 2228 3513 1497 \n",
       "Q 3513 744 3044 326 \n",
       "Q 2575 -91 1722 -91 \n",
       "Q 1428 -91 1123 -41 \n",
       "Q 819 9 494 109 \n",
       "L 494 744 \n",
       "Q 775 591 1075 516 \n",
       "Q 1375 441 1709 441 \n",
       "Q 2250 441 2565 725 \n",
       "Q 2881 1009 2881 1497 \n",
       "Q 2881 1984 2565 2268 \n",
       "Q 2250 2553 1709 2553 \n",
       "Q 1456 2553 1204 2497 \n",
       "Q 953 2441 691 2322 \n",
       "L 691 4666 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-35\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_10\">\n",
       "    <g id=\"line2d_22\">\n",
       "     <path d=\"M 484.424116 236.550058 \n",
       "L 487.384146 237.736542 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_20\">\n",
       "     <!-- 6 -->\n",
       "     <g transform=\"translate(492.944338 259.181104) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-36\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_11\">\n",
       "    <g id=\"line2d_23\">\n",
       "     <path d=\"M 465.027392 244.550636 \n",
       "L 467.988105 245.769375 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_21\">\n",
       "     <!-- 7 -->\n",
       "     <g transform=\"translate(473.605266 267.427148) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-37\" d=\"M 525 4666 \n",
       "L 3525 4666 \n",
       "L 3525 4397 \n",
       "L 1831 0 \n",
       "L 1172 0 \n",
       "L 2766 4134 \n",
       "L 525 4134 \n",
       "L 525 4666 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-37\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"axis3d_2\">\n",
       "   <g id=\"line2d_24\">\n",
       "    <path d=\"M 349.876649 199.022045 \n",
       "L 463.551524 245.972978 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"text_22\">\n",
       "    <!-- y -->\n",
       "    <g transform=\"translate(378.290829 255.309842) scale(0.1 -0.1)\">\n",
       "     <defs>\n",
       "      <path id=\"DejaVuSans-79\" d=\"M 2059 -325 \n",
       "Q 1816 -950 1584 -1140 \n",
       "Q 1353 -1331 966 -1331 \n",
       "L 506 -1331 \n",
       "L 506 -850 \n",
       "L 844 -850 \n",
       "Q 1081 -850 1212 -737 \n",
       "Q 1344 -625 1503 -206 \n",
       "L 1606 56 \n",
       "L 191 3500 \n",
       "L 800 3500 \n",
       "L 1894 763 \n",
       "L 2988 3500 \n",
       "L 3597 3500 \n",
       "L 2059 -325 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "     </defs>\n",
       "     <use xlink:href=\"#DejaVuSans-79\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Line3DCollection_2\">\n",
       "    <path d=\"M 465.724465 51.812223 \n",
       "L 465.663743 159.604762 \n",
       "L 351.976283 199.889253 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 483.343815 56.737422 \n",
       "L 482.784247 165.653773 \n",
       "L 369.012274 206.925599 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 501.393272 61.782851 \n",
       "L 500.310726 171.846223 \n",
       "L 386.484568 214.142149 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 519.888783 66.952966 \n",
       "L 518.257794 178.187276 \n",
       "L 404.410142 221.545918 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 538.847087 72.252449 \n",
       "L 536.640774 184.682344 \n",
       "L 422.806868 229.144285 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 558.285775 77.686214 \n",
       "L 555.475743 191.33711 \n",
       "L 441.693569 236.945026 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 578.223341 83.259432 \n",
       "L 574.779579 198.157535 \n",
       "L 461.090084 244.956334 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "   </g>\n",
       "   <g id=\"xtick_12\">\n",
       "    <g id=\"line2d_25\">\n",
       "     <path d=\"M 352.956144 199.542045 \n",
       "L 350.012887 200.584971 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_23\">\n",
       "     <!-- 0 -->\n",
       "     <g transform=\"translate(338.374957 221.052514) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_13\">\n",
       "    <g id=\"line2d_26\">\n",
       "     <path d=\"M 369.993753 206.569558 \n",
       "L 367.04559 207.639031 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_24\">\n",
       "     <!-- 1 -->\n",
       "     <g transform=\"translate(355.350899 228.290936) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-31\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_14\">\n",
       "    <g id=\"line2d_27\">\n",
       "     <path d=\"M 387.467427 213.776935 \n",
       "L 384.515069 214.873982 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_25\">\n",
       "     <!-- 2 -->\n",
       "     <g transform=\"translate(372.763474 235.715535) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_15\">\n",
       "    <g id=\"line2d_28\">\n",
       "     <path d=\"M 405.394124 221.17117 \n",
       "L 402.438346 222.296872 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_26\">\n",
       "     <!-- 3 -->\n",
       "     <g transform=\"translate(390.629747 243.333587) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-33\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_16\">\n",
       "    <g id=\"line2d_29\">\n",
       "     <path d=\"M 423.791692 228.759627 \n",
       "L 420.833333 229.915121 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_27\">\n",
       "     <!-- 4 -->\n",
       "     <g transform=\"translate(408.967683 251.152753) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_17\">\n",
       "    <g id=\"line2d_30\">\n",
       "     <path d=\"M 442.678932 236.550058 \n",
       "L 439.718902 237.736542 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_28\">\n",
       "     <!-- 5 -->\n",
       "     <g transform=\"translate(427.79621 259.181104) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-35\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_18\">\n",
       "    <g id=\"line2d_31\">\n",
       "     <path d=\"M 462.075656 244.550636 \n",
       "L 459.114944 245.769375 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_29\">\n",
       "     <!-- 6 -->\n",
       "     <g transform=\"translate(447.135282 267.427148) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-36\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"axis3d_3\">\n",
       "   <g id=\"line2d_32\">\n",
       "    <path d=\"M 349.876649 199.022045 \n",
       "L 346.351476 83.966158 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"text_30\">\n",
       "    <!-- $\\theta$ -->\n",
       "    <g transform=\"translate(301.605686 139.35844) rotate(-271.754924) scale(0.1 -0.1)\">\n",
       "     <defs>\n",
       "      <path id=\"DejaVuSans-Oblique-3b8\" d=\"M 2913 2219 \n",
       "L 925 2219 \n",
       "Q 791 1284 928 888 \n",
       "Q 1100 400 1566 400 \n",
       "Q 2034 400 2391 891 \n",
       "Q 2703 1322 2913 2219 \n",
       "z\n",
       "M 3009 2750 \n",
       "Q 3094 3638 2984 3950 \n",
       "Q 2813 4444 2353 4444 \n",
       "Q 1875 4444 1525 3956 \n",
       "Q 1250 3563 1034 2750 \n",
       "L 3009 2750 \n",
       "z\n",
       "M 2444 4913 \n",
       "Q 3194 4913 3494 4250 \n",
       "Q 3794 3591 3566 2422 \n",
       "Q 3341 1256 2781 594 \n",
       "Q 2225 -72 1475 -72 \n",
       "Q 722 -72 425 594 \n",
       "Q 128 1256 353 2422 \n",
       "Q 581 3591 1134 4250 \n",
       "Q 1691 4913 2444 4913 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "     </defs>\n",
       "     <use xlink:href=\"#DejaVuSans-Oblique-3b8\" transform=\"translate(0 0.234375)\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Line3DCollection_3\">\n",
       "    <path d=\"M 349.808225 196.788797 \n",
       "L 463.551524 156.764311 \n",
       "L 577.294823 196.788797 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 349.282773 179.638912 \n",
       "L 463.551524 140.68858 \n",
       "L 577.820275 179.638912 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 348.752444 162.329838 \n",
       "L 463.551524 124.474517 \n",
       "L 578.350604 162.329838 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 348.21717 144.85935 \n",
       "L 463.551524 108.120328 \n",
       "L 578.885878 144.85935 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 347.67688 127.22518 \n",
       "L 463.551524 91.624189 \n",
       "L 579.426168 127.22518 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 347.131505 109.425015 \n",
       "L 463.551524 74.984243 \n",
       "L 579.971544 109.425015 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "    <path d=\"M 346.580971 91.456502 \n",
       "L 463.551524 58.198603 \n",
       "L 580.522077 91.456502 \n",
       "\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8\"/>\n",
       "   </g>\n",
       "   <g id=\"xtick_19\">\n",
       "    <g id=\"line2d_33\">\n",
       "     <path d=\"M 350.7885 196.443854 \n",
       "L 347.844003 197.479976 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_31\">\n",
       "     <!-- 0 -->\n",
       "     <g transform=\"translate(326.823411 204.387235) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_20\">\n",
       "    <g id=\"line2d_34\">\n",
       "     <path d=\"M 350.267903 179.303114 \n",
       "L 347.308807 180.31177 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_32\">\n",
       "     <!-- 1 -->\n",
       "     <g transform=\"translate(326.206474 187.237349) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-31\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_21\">\n",
       "    <g id=\"line2d_35\">\n",
       "     <path d=\"M 349.742476 162.003372 \n",
       "L 346.768637 162.984004 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_33\">\n",
       "     <!-- 2 -->\n",
       "     <g transform=\"translate(325.58381 169.928276) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_22\">\n",
       "    <g id=\"line2d_36\">\n",
       "     <path d=\"M 349.212153 144.542405 \n",
       "L 346.223423 145.494446 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_34\">\n",
       "     <!-- 3 -->\n",
       "     <g transform=\"translate(324.955341 152.457788) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-33\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_23\">\n",
       "    <g id=\"line2d_37\">\n",
       "     <path d=\"M 348.676865 126.917947 \n",
       "L 345.673094 127.840817 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_35\">\n",
       "     <!-- 4 -->\n",
       "     <g transform=\"translate(324.320982 134.823617) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_24\">\n",
       "    <g id=\"line2d_38\">\n",
       "     <path d=\"M 348.136541 109.127693 \n",
       "L 345.117578 110.020799 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_36\">\n",
       "     <!-- 5 -->\n",
       "     <g transform=\"translate(323.680653 117.023453) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-35\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"xtick_25\">\n",
       "    <g id=\"line2d_39\">\n",
       "     <path d=\"M 347.59111 91.169292 \n",
       "L 344.556802 92.032028 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_37\">\n",
       "     <!-- 6 -->\n",
       "     <g transform=\"translate(323.034268 99.054939) scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-36\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       "  <g id=\"axes_2\">\n",
       "   <g id=\"Poly3DCollection_1\">\n",
       "    <defs>\n",
       "     <path id=\"m3633629afe\" d=\"M 437.395061 -134.639722 \n",
       "L 382.163947 -114.919518 \n",
       "L 388.893299 -97.329751 \n",
       "L 425.24225 -82.426591 \n",
       "L 481.980325 -104.498965 \n",
       "L 517.475679 -118.307448 \n",
       "L 481.093998 -131.451817 \n",
       "L 437.395061 -134.639722 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m3633629afe\" x=\"0\" y=\"308.278125\" style=\"fill: #808080; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_2\">\n",
       "    <defs>\n",
       "     <path id=\"mc106039d9e\" d=\"M 434.734125 -135.319166 \n",
       "L 379.264043 -115.574392 \n",
       "L 390.818441 -98.438926 \n",
       "L 427.283842 -83.53796 \n",
       "L 484.043245 -105.606593 \n",
       "L 515.459687 -120.741545 \n",
       "L 479.152872 -133.817877 \n",
       "L 434.734125 -135.319166 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mc106039d9e\" x=\"0\" y=\"308.278125\" style=\"fill: #828282; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_3\">\n",
       "    <defs>\n",
       "     <path id=\"me04e0788a4\" d=\"M 432.371198 -135.909003 \n",
       "L 376.661924 -116.132582 \n",
       "L 392.943942 -99.639405 \n",
       "L 429.525692 -84.74541 \n",
       "L 486.290217 -106.803268 \n",
       "L 513.279049 -123.091763 \n",
       "L 477.045707 -136.104052 \n",
       "L 432.371198 -135.909003 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#me04e0788a4\" x=\"0\" y=\"308.278125\" style=\"fill: #848484; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_4\">\n",
       "    <defs>\n",
       "     <path id=\"m43c72dda66\" d=\"M 430.333302 -136.421371 \n",
       "L 374.386865 -116.607091 \n",
       "L 395.246016 -100.937984 \n",
       "L 431.942867 -86.056125 \n",
       "L 488.696494 -108.095606 \n",
       "L 510.957188 -125.35297 \n",
       "L 474.794984 -138.305446 \n",
       "L 430.333302 -136.421371 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m43c72dda66\" x=\"0\" y=\"308.278125\" style=\"fill: #868686; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_5\">\n",
       "    <defs>\n",
       "     <path id=\"m77275a6a34\" d=\"M 428.644549 -136.869294 \n",
       "L 372.465276 -117.011889 \n",
       "L 397.698586 -102.34031 \n",
       "L 434.508144 -87.476076 \n",
       "L 491.23524 -109.489099 \n",
       "L 508.51882 -127.521009 \n",
       "L 472.42451 -140.418096 \n",
       "L 428.644549 -136.869294 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m77275a6a34\" x=\"0\" y=\"308.278125\" style=\"fill: #888888; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_6\">\n",
       "    <defs>\n",
       "     <path id=\"mebf5725055\" d=\"M 427.325827 -137.26659 \n",
       "L 370.920354 -117.361802 \n",
       "L 400.273604 -103.8508 \n",
       "L 437.192338 -89.009939 \n",
       "L 493.877865 -110.988045 \n",
       "L 505.989713 -129.592716 \n",
       "L 469.959187 -142.438983 \n",
       "L 427.325827 -137.26659 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mebf5725055\" x=\"0\" y=\"308.278125\" style=\"fill: #8a8a8a; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_7\">\n",
       "    <defs>\n",
       "     <path id=\"m3cccf5878d\" d=\"M 426.394483 -137.627747 \n",
       "L 369.771747 -117.672396 \n",
       "L 405.108205 -103.507975 \n",
       "L 439.964671 -90.661022 \n",
       "L 496.594379 -112.595477 \n",
       "L 503.396458 -131.565936 \n",
       "L 467.424784 -144.366053 \n",
       "L 426.394483 -137.627747 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m3cccf5878d\" x=\"0\" y=\"308.278125\" style=\"fill: #8c8c8c; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_8\">\n",
       "    <defs>\n",
       "     <path id=\"m2934c5ce56\" d=\"M 425.864028 -137.967797 \n",
       "L 369.035229 -117.959834 \n",
       "L 404.4716 -103.75516 \n",
       "L 442.793168 -92.431225 \n",
       "L 499.353781 -114.313131 \n",
       "L 500.766222 -133.439527 \n",
       "L 464.847703 -146.198219 \n",
       "L 425.864028 -137.967797 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m2934c5ce56\" x=\"0\" y=\"308.278125\" style=\"fill: #8e8e8e; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_9\">\n",
       "    <defs>\n",
       "     <path id=\"m4069547c9b\" d=\"M 425.743866 -138.302169 \n",
       "L 368.722396 -118.240722 \n",
       "L 404.27096 -103.995127 \n",
       "L 445.645078 -94.32101 \n",
       "L 502.124462 -116.141415 \n",
       "L 498.126516 -135.213355 \n",
       "L 462.254744 -147.93536 \n",
       "L 425.743866 -138.302169 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m4069547c9b\" x=\"0\" y=\"308.278125\" style=\"fill: #909090; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_10\">\n",
       "    <defs>\n",
       "     <path id=\"m63aa06fe11\" d=\"M 426.039049 -138.646536 \n",
       "L 368.840389 -118.531942 \n",
       "L 404.512609 -104.245646 \n",
       "L 448.487309 -96.329395 \n",
       "L 504.874628 -118.07941 \n",
       "L 495.504952 -136.888294 \n",
       "L 459.672874 -149.578312 \n",
       "L 426.039049 -138.646536 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m63aa06fe11\" x=\"0\" y=\"308.278125\" style=\"fill: #939393; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_11\">\n",
       "    <defs>\n",
       "     <path id=\"ma81cfdfbe3\" d=\"M 457.128987 -151.128856 \n",
       "L 402.278167 -131.897894 \n",
       "L 369.39166 -118.850473 \n",
       "L 405.198036 -104.524597 \n",
       "L 451.286873 -98.453982 \n",
       "L 507.572718 -120.124888 \n",
       "L 492.929004 -138.466203 \n",
       "L 457.128987 -151.128856 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#ma81cfdfbe3\" x=\"0\" y=\"308.278125\" style=\"fill: #959595; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_12\">\n",
       "    <defs>\n",
       "     <path id=\"mfeecabca29\" d=\"M 454.649672 -152.589698 \n",
       "L 399.648169 -133.393213 \n",
       "L 370.373775 -119.213189 \n",
       "L 406.323706 -104.849767 \n",
       "L 454.011323 -100.690991 \n",
       "L 510.187825 -122.27435 \n",
       "L 490.425771 -139.94991 \n",
       "L 454.649672 -152.589698 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mfeecabca29\" x=\"0\" y=\"308.278125\" style=\"fill: #979797; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_13\">\n",
       "    <defs>\n",
       "     <path id=\"m624648ba06\" d=\"M 452.260979 -153.96444 \n",
       "L 397.101897 -134.795809 \n",
       "L 371.779281 -119.636661 \n",
       "L 407.880924 -105.238634 \n",
       "L 456.629184 -103.035325 \n",
       "L 512.690101 -124.523087 \n",
       "L 488.021736 -141.343185 \n",
       "L 452.260979 -153.96444 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m624648ba06\" x=\"0\" y=\"308.278125\" style=\"fill: #999999; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_14\">\n",
       "    <defs>\n",
       "     <path id=\"ma6c69d0cce\" d=\"M 449.988179 -155.257553 \n",
       "L 394.665918 -136.110469 \n",
       "L 373.595636 -120.13694 \n",
       "L 409.855777 -105.708137 \n",
       "L 459.110366 -105.480656 \n",
       "L 515.051145 -126.865249 \n",
       "L 485.742525 -142.650705 \n",
       "L 449.988179 -155.257553 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#ma6c69d0cce\" x=\"0\" y=\"308.278125\" style=\"fill: #9b9b9b; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_15\">\n",
       "    <defs>\n",
       "     <path id=\"mb6705bcdc5\" d=\"M 447.855531 -156.474335 \n",
       "L 392.365861 -137.342869 \n",
       "L 375.805208 -120.729343 \n",
       "L 412.229143 -106.274454 \n",
       "L 461.426547 -108.019523 \n",
       "L 517.244362 -129.293944 \n",
       "L 483.612677 -143.878015 \n",
       "L 447.855531 -156.474335 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mb6705bcdc5\" x=\"0\" y=\"308.278125\" style=\"fill: #9d9d9d; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_16\">\n",
       "    <defs>\n",
       "     <path id=\"mfe1471dc1d\" d=\"M 445.886052 -157.620866 \n",
       "L 390.226174 -138.499528 \n",
       "L 378.385361 -121.428236 \n",
       "L 414.976784 -106.952766 \n",
       "L 463.551524 -110.643446 \n",
       "L 519.245293 -131.801342 \n",
       "L 481.655398 -145.031485 \n",
       "L 445.886052 -157.620866 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mfe1471dc1d\" x=\"0\" y=\"308.278125\" style=\"fill: #9f9f9f; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_17\">\n",
       "    <defs>\n",
       "     <path id=\"m0c5a7ecb73\" d=\"M 444.101283 -158.703962 \n",
       "L 388.269883 -139.587754 \n",
       "L 381.308615 -122.246824 \n",
       "L 418.069534 -107.757038 \n",
       "L 465.461528 -113.343057 \n",
       "L 521.031899 -134.378791 \n",
       "L 483.43098 -147.533314 \n",
       "L 444.101283 -158.703962 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m0c5a7ecb73\" x=\"0\" y=\"308.278125\" style=\"fill: #a2a2a2; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_18\">\n",
       "    <defs>\n",
       "     <path id=\"m24d159a12d\" d=\"M 442.521061 -159.73111 \n",
       "L 386.518347 -140.615586 \n",
       "L 384.542905 -123.196949 \n",
       "L 421.473566 -108.6998 \n",
       "L 467.135491 -116.108239 \n",
       "L 522.584815 -137.016943 \n",
       "L 484.983223 -150.092898 \n",
       "L 442.521061 -159.73111 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m24d159a12d\" x=\"0\" y=\"308.278125\" style=\"fill: #a4a4a4; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_19\">\n",
       "    <defs>\n",
       "     <path id=\"m1960b726f7\" d=\"M 441.163302 -160.710409 \n",
       "L 384.991034 -141.591718 \n",
       "L 388.051915 -124.288905 \n",
       "L 425.150759 -109.791953 \n",
       "L 468.555271 -118.928267 \n",
       "L 523.887548 -139.705892 \n",
       "L 486.295399 -152.700822 \n",
       "L 441.163302 -160.710409 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m1960b726f7\" x=\"0\" y=\"308.278125\" style=\"fill: #a6a6a6; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_20\">\n",
       "    <defs>\n",
       "     <path id=\"mf58d94f305\" d=\"M 440.043788 -161.650497 \n",
       "L 383.705282 -142.525431 \n",
       "L 391.795513 -125.531269 \n",
       "L 429.059152 -111.042589 \n",
       "L 469.705827 -121.791961 \n",
       "L 524.926634 -142.435303 \n",
       "L 487.353689 -155.347266 \n",
       "L 440.043788 -161.650497 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mf58d94f305\" x=\"0\" y=\"308.278125\" style=\"fill: #a8a8a8; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_21\">\n",
       "    <defs>\n",
       "     <path id=\"m8ad9e83b5b\" d=\"M 439.175962 -162.560469 \n",
       "L 382.676086 -143.426503 \n",
       "L 395.730249 -126.930767 \n",
       "L 433.153473 -112.458839 \n",
       "L 470.575345 -124.687831 \n",
       "L 525.691751 -145.194558 \n",
       "L 488.1473 -158.022136 \n",
       "L 439.175962 -162.560469 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m8ad9e83b5b\" x=\"0\" y=\"308.278125\" style=\"fill: #aaaaaa; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_22\">\n",
       "    <defs>\n",
       "     <path id=\"me2bda0b159\" d=\"M 438.570742 -163.449792 \n",
       "L 381.915895 -144.305123 \n",
       "L 399.809934 -128.492153 \n",
       "L 437.385747 -114.045756 \n",
       "L 495.051907 -135.434888 \n",
       "L 526.175778 -147.972885 \n",
       "L 488.668533 -160.71519 \n",
       "L 438.570742 -163.449792 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#me2bda0b159\" x=\"0\" y=\"308.278125\" style=\"fill: #acacac; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_23\">\n",
       "    <defs>\n",
       "     <path id=\"m0d0abe1299\" d=\"M 438.236353 -164.328217 \n",
       "L 381.434416 -145.171783 \n",
       "L 403.986283 -130.218138 \n",
       "L 441.705967 -115.806227 \n",
       "L 499.250418 -137.144075 \n",
       "L 526.374823 -150.759491 \n",
       "L 488.912819 -163.416165 \n",
       "L 438.236353 -164.328217 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m0d0abe1299\" x=\"0\" y=\"308.278125\" style=\"fill: #aeaeae; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_24\">\n",
       "    <defs>\n",
       "     <path id=\"mf9882f1110\" d=\"M 438.178173 -165.205672 \n",
       "L 381.238453 -146.037182 \n",
       "L 408.209591 -132.10934 \n",
       "L 446.062802 -117.740928 \n",
       "L 503.466654 -139.014233 \n",
       "L 526.288196 -153.543696 \n",
       "L 488.878708 -166.114901 \n",
       "L 438.178173 -165.205672 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mf9882f1110\" x=\"0\" y=\"308.278125\" style=\"fill: #b0b0b0; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_25\">\n",
       "    <defs>\n",
       "     <path id=\"m4d1ffdf070\" d=\"M 438.398612 -166.092162 \n",
       "L 381.331757 -146.912106 \n",
       "L 412.429456 -134.164281 \n",
       "L 450.404349 -119.848314 \n",
       "L 507.65083 -141.043915 \n",
       "L 525.918352 -156.315042 \n",
       "L 488.56782 -168.801448 \n",
       "L 438.398612 -166.092162 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m4d1ffdf070\" x=\"0\" y=\"308.278125\" style=\"fill: #b2b2b2; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_26\">\n",
       "    <defs>\n",
       "     <path id=\"mdb9cd9fa4b\" d=\"M 438.897019 -166.997658 \n",
       "L 381.714914 -147.807309 \n",
       "L 418.033275 -134.170265 \n",
       "L 454.678892 -122.124653 \n",
       "L 511.753557 -143.229666 \n",
       "L 525.270799 -159.063415 \n",
       "L 487.984768 -171.466179 \n",
       "L 438.897019 -166.997658 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mdb9cd9fa4b\" x=\"0\" y=\"308.278125\" style=\"fill: #b5b5b5; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_27\">\n",
       "    <defs>\n",
       "     <path id=\"m7215f7ca55\" d=\"M 439.669614 -167.931982 \n",
       "L 382.385267 -148.733398 \n",
       "L 418.807459 -135.088501 \n",
       "L 458.835651 -124.564095 \n",
       "L 515.726562 -145.566088 \n",
       "L 524.353974 -161.779138 \n",
       "L 487.137042 -174.099883 \n",
       "L 439.669614 -167.931982 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m7215f7ca55\" x=\"0\" y=\"308.278125\" style=\"fill: #b7b7b7; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_28\">\n",
       "    <defs>\n",
       "     <path id=\"m68a119fee4\" d=\"M 440.709467 -168.904694 \n",
       "L 383.336864 -149.700699 \n",
       "L 419.868147 -136.050008 \n",
       "L 462.825519 -127.158785 \n",
       "L 519.52337 -148.045935 \n",
       "L 523.179092 -164.45307 \n",
       "L 486.034876 -176.693853 \n",
       "L 440.709467 -168.904694 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m68a119fee4\" x=\"0\" y=\"308.278125\" style=\"fill: #b9b9b9; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_29\">\n",
       "    <defs>\n",
       "     <path id=\"m37041bfb9a\" d=\"M 442.006513 -169.924971 \n",
       "L 384.560465 -150.719134 \n",
       "L 421.205142 -137.065255 \n",
       "L 466.601756 -129.899001 \n",
       "L 523.099961 -150.660251 \n",
       "L 521.759977 -167.076684 \n",
       "L 484.691086 -179.239969 \n",
       "L 442.006513 -169.924971 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m37041bfb9a\" x=\"0\" y=\"308.278125\" style=\"fill: #bbbbbb; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_30\">\n",
       "    <defs>\n",
       "     <path id=\"m9b42243e14\" d=\"M 443.547607 -171.001497 \n",
       "L 386.043575 -151.798098 \n",
       "L 422.804928 -138.144162 \n",
       "L 470.120627 -132.77333 \n",
       "L 526.415356 -153.398522 \n",
       "L 520.112869 -169.64214 \n",
       "L 483.120894 -181.730761 \n",
       "L 443.547607 -171.001497 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m9b42243e14\" x=\"0\" y=\"308.278125\" style=\"fill: #bdbdbd; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_31\">\n",
       "    <defs>\n",
       "     <path id=\"m08981537a0\" d=\"M 445.316625 -172.142346 \n",
       "L 387.770538 -152.946332 \n",
       "L 424.650768 -139.295959 \n",
       "L 473.341973 -135.768867 \n",
       "L 529.432153 -156.248857 \n",
       "L 518.256221 -172.142346 \n",
       "L 481.34173 -184.15947 \n",
       "L 445.316625 -172.142346 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m08981537a0\" x=\"0\" y=\"308.278125\" style=\"fill: #bfbfbf; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_32\">\n",
       "    <defs>\n",
       "     <path id=\"mb08d3a2044\" d=\"M 479.373029 -186.520099 \n",
       "L 424.618586 -168.369789 \n",
       "L 389.722673 -154.171808 \n",
       "L 426.722852 -140.529074 \n",
       "L 476.229707 -138.871428 \n",
       "L 532.116979 -159.198187 \n",
       "L 516.21048 -174.57101 \n",
       "L 479.373029 -186.520099 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mb08d3a2044\" x=\"0\" y=\"308.278125\" style=\"fill: #c1c1c1; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_33\">\n",
       "    <defs>\n",
       "     <path id=\"m9248a2b645\" d=\"M 477.236017 -188.807451 \n",
       "L 422.434042 -170.754976 \n",
       "L 391.878455 -155.481621 \n",
       "L 428.998495 -141.851006 \n",
       "L 478.752226 -142.065784 \n",
       "L 534.440865 -162.232477 \n",
       "L 513.997867 -176.92268 \n",
       "L 477.236017 -188.807451 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m9248a2b645\" x=\"0\" y=\"308.278125\" style=\"fill: #c3c3c3; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_34\">\n",
       "    <defs>\n",
       "     <path id=\"mf59e898f28\" d=\"M 474.953483 -191.017164 \n",
       "L 420.089515 -173.056512 \n",
       "L 394.213753 -156.881887 \n",
       "L 431.452383 -143.268228 \n",
       "L 480.882729 -145.335901 \n",
       "L 536.379531 -165.33694 \n",
       "L 511.642141 -179.192778 \n",
       "L 474.953483 -191.017164 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mf59e898f28\" x=\"0\" y=\"308.278125\" style=\"fill: #c6c6c6; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_35\">\n",
       "    <defs>\n",
       "     <path id=\"m1e32a730c9\" d=\"M 472.549559 -193.14573 \n",
       "L 417.609477 -175.27063 \n",
       "L 396.702103 -158.37766 \n",
       "L 434.056869 -144.786089 \n",
       "L 482.599447 -148.665177 \n",
       "L 537.91359 -168.496262 \n",
       "L 509.168366 -181.377627 \n",
       "L 472.549559 -193.14573 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m1e32a730c9\" x=\"0\" y=\"308.278125\" style=\"fill: #c8c8c8; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_36\">\n",
       "    <defs>\n",
       "     <path id=\"mcf2d92529e\" d=\"M 470.049484 -195.190516 \n",
       "L 415.019636 -177.394496 \n",
       "L 399.315029 -159.972857 \n",
       "L 436.782306 -146.408739 \n",
       "L 483.885789 -152.036681 \n",
       "L 539.028669 -171.694814 \n",
       "L 506.602673 -183.474462 \n",
       "L 470.049484 -195.190516 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mcf2d92529e\" x=\"0\" y=\"308.278125\" style=\"fill: #cacaca; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_37\">\n",
       "    <defs>\n",
       "     <path id=\"mbd4f88b993\" d=\"M 467.479372 -197.14977 \n",
       "L 412.346701 -179.426228 \n",
       "L 402.022401 -161.670201 \n",
       "L 439.597422 -148.139069 \n",
       "L 484.730394 -155.433384 \n",
       "L 539.715443 -174.916869 \n",
       "L 501.550034 -187.098565 \n",
       "L 467.479372 -197.14977 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mbd4f88b993\" x=\"0\" y=\"308.278125\" style=\"fill: #cccccc; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_38\">\n",
       "    <defs>\n",
       "     <path id=\"mfcee5c3602\" d=\"M 464.865976 -199.022627 \n",
       "L 409.618142 -181.364889 \n",
       "L 404.792819 -163.47119 \n",
       "L 442.469723 -149.978673 \n",
       "L 485.127112 -158.838375 \n",
       "L 539.969599 -178.146796 \n",
       "L 501.884139 -190.220844 \n",
       "L 464.865976 -199.022627 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mfcee5c3602\" x=\"0\" y=\"308.278125\" style=\"fill: #cecece; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_39\">\n",
       "    <defs>\n",
       "     <path id=\"m9edb77265c\" d=\"M 462.236455 -200.809103 \n",
       "L 406.861952 -183.210491 \n",
       "L 407.594029 -165.376069 \n",
       "L 445.365925 -151.927823 \n",
       "L 485.074908 -162.235063 \n",
       "L 539.791736 -181.36925 \n",
       "L 501.797128 -193.33614 \n",
       "L 462.236455 -200.809103 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m9edb77265c\" x=\"0\" y=\"308.278125\" style=\"fill: #d0d0d0; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_40\">\n",
       "    <defs>\n",
       "     <path id=\"m08624a863b\" d=\"M 459.618133 -202.510087 \n",
       "L 404.1064 -184.963982 \n",
       "L 410.393347 -167.383836 \n",
       "L 448.252392 -153.985471 \n",
       "L 484.577708 -165.607362 \n",
       "L 539.187201 -184.569342 \n",
       "L 501.293 -196.430291 \n",
       "L 459.618133 -202.510087 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m08624a863b\" x=\"0\" y=\"308.278125\" style=\"fill: #d2d2d2; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_41\">\n",
       "    <defs>\n",
       "     <path id=\"me1c043f35b\" d=\"M 457.038267 -204.127324 \n",
       "L 401.379794 -186.627229 \n",
       "L 413.158095 -169.492263 \n",
       "L 451.095593 -156.149271 \n",
       "L 508.232615 -175.904702 \n",
       "L 538.165878 -187.732793 \n",
       "L 500.38021 -199.489705 \n",
       "L 457.038267 -204.127324 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#me1c043f35b\" x=\"0\" y=\"308.278125\" style=\"fill: #d4d4d4; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_42\">\n",
       "    <defs>\n",
       "     <path id=\"madd07859fc\" d=\"M 454.523802 -205.6634 \n",
       "L 398.710234 -188.202998 \n",
       "L 415.85604 -171.697929 \n",
       "L 453.862548 -158.415618 \n",
       "L 510.886858 -178.08123 \n",
       "L 536.741937 -190.846068 \n",
       "L 499.071436 -202.501495 \n",
       "L 454.523802 -205.6634 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#madd07859fc\" x=\"0\" y=\"308.278125\" style=\"fill: #d7d7d7; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_43\">\n",
       "    <defs>\n",
       "     <path id=\"mdd02f8c028\" d=\"M 452.10114 -207.12171 \n",
       "L 396.125366 -189.69493 \n",
       "L 418.455817 -173.996285 \n",
       "L 456.521265 -160.779714 \n",
       "L 513.426435 -180.348064 \n",
       "L 534.933545 -193.896495 \n",
       "L 497.38332 -205.45359 \n",
       "L 452.10114 -207.12171 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mdd02f8c028\" x=\"0\" y=\"308.278125\" style=\"fill: #d9d9d9; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_44\">\n",
       "    <defs>\n",
       "     <path id=\"mc5cc899d57\" d=\"M 449.795899 -208.506434 \n",
       "L 393.65214 -191.107502 \n",
       "L 420.927342 -176.381723 \n",
       "L 459.041161 -163.235639 \n",
       "L 515.822505 -182.699742 \n",
       "L 532.762566 -196.872363 \n",
       "L 495.336178 -208.334828 \n",
       "L 449.795899 -208.506434 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mc5cc899d57\" x=\"0\" y=\"308.278125\" style=\"fill: #dbdbdb; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_45\">\n",
       "    <defs>\n",
       "     <path id=\"me2ec68f2ee\" d=\"M 447.632676 -209.822492 \n",
       "L 391.316559 -192.445995 \n",
       "L 423.242191 -178.847666 \n",
       "L 461.393456 -165.776453 \n",
       "L 518.048069 -185.129862 \n",
       "L 530.254231 -199.763004 \n",
       "L 492.953689 -211.135037 \n",
       "L 447.632676 -209.822492 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#me2ec68f2ee\" x=\"0\" y=\"308.278125\" style=\"fill: #dddddd; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_46\">\n",
       "    <defs>\n",
       "     <path id=\"m13051b0fd1\" d=\"M 445.63481 -211.075511 \n",
       "L 389.143436 -193.716444 \n",
       "L 425.373961 -181.386674 \n",
       "L 463.551524 -168.394299 \n",
       "L 520.0783 -187.631176 \n",
       "L 527.436807 -202.558857 \n",
       "L 490.262587 -213.845098 \n",
       "L 445.63481 -211.075511 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m13051b0fd1\" x=\"0\" y=\"308.278125\" style=\"fill: #dfdfdf; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_47\">\n",
       "    <defs>\n",
       "     <path id=\"mb323fddc61\" d=\"M 443.824151 -212.271771 \n",
       "L 387.156146 -194.925593 \n",
       "L 423.405151 -182.603504 \n",
       "L 465.491219 -171.080529 \n",
       "L 521.890837 -190.195705 \n",
       "L 524.341258 -205.251524 \n",
       "L 487.292329 -216.456995 \n",
       "L 443.824151 -212.271771 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mb323fddc61\" x=\"0\" y=\"308.278125\" style=\"fill: #e1e1e1; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_48\">\n",
       "    <defs>\n",
       "     <path id=\"mdbdaeed86d\" d=\"M 442.220829 -213.418151 \n",
       "L 385.376388 -196.080833 \n",
       "L 421.654043 -183.763462 \n",
       "L 467.191143 -173.825827 \n",
       "L 523.466036 -192.814854 \n",
       "L 521.000906 -207.833799 \n",
       "L 484.074775 -218.963852 \n",
       "L 442.220829 -213.418151 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mdbdaeed86d\" x=\"0\" y=\"308.278125\" style=\"fill: #e3e3e3; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_49\">\n",
       "    <defs>\n",
       "     <path id=\"mde1f2e399d\" d=\"M 440.843028 -214.522073 \n",
       "L 383.823942 -197.190141 \n",
       "L 420.140385 -184.87493 \n",
       "L 468.632876 -176.620344 \n",
       "L 524.787176 -195.479537 \n",
       "L 517.451099 -210.299704 \n",
       "L 480.64386 -221.359959 \n",
       "L 440.843028 -214.522073 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mde1f2e399d\" x=\"0\" y=\"308.278125\" style=\"fill: #e6e6e6; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_50\">\n",
       "    <defs>\n",
       "     <path id=\"m8b3cbe0051\" d=\"M 439.706775 -215.591432 \n",
       "L 382.516437 -198.262009 \n",
       "L 418.881677 -185.946837 \n",
       "L 469.801153 -179.453839 \n",
       "L 525.840619 -198.180299 \n",
       "L 513.728876 -212.644494 \n",
       "L 477.035275 -223.640786 \n",
       "L 439.706775 -215.591432 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m8b3cbe0051\" x=\"0\" y=\"308.278125\" style=\"fill: #e8e8e8; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_51\">\n",
       "    <defs>\n",
       "     <path id=\"m518b7a78c7\" d=\"M 438.82573 -216.634525 \n",
       "L 381.469135 -199.305367 \n",
       "L 417.892954 -186.988574 \n",
       "L 470.68399 -182.315813 \n",
       "L 526.615915 -200.907446 \n",
       "L 509.872646 -214.864673 \n",
       "L 473.286153 -225.802993 \n",
       "L 438.82573 -216.634525 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m518b7a78c7\" x=\"0\" y=\"308.278125\" style=\"fill: #eaeaea; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_52\">\n",
       "    <defs>\n",
       "     <path id=\"m3044e7cf6d\" d=\"M 469.434752 -227.844427 \n",
       "L 414.459026 -211.30883 \n",
       "L 380.694713 -200.329497 \n",
       "L 417.186566 -188.009912 \n",
       "L 471.272765 -185.195645 \n",
       "L 527.105873 -203.651169 \n",
       "L 505.921871 -216.957985 \n",
       "L 469.434752 -227.844427 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m3044e7cf6d\" x=\"0\" y=\"308.278125\" style=\"fill: #ececec; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_53\">\n",
       "    <defs>\n",
       "     <path id=\"ma0c2a2d123\" d=\"M 465.520157 -229.764118 \n",
       "L 410.385625 -213.297951 \n",
       "L 380.203077 -201.343943 \n",
       "L 416.77199 -189.020897 \n",
       "L 471.562248 -188.082724 \n",
       "L 527.306576 -206.401662 \n",
       "L 501.916749 -218.923412 \n",
       "L 465.520157 -229.764118 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#ma0c2a2d123\" x=\"0\" y=\"308.278125\" style=\"fill: #eeeeee; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_54\">\n",
       "    <defs>\n",
       "     <path id=\"m69d7806c1f\" d=\"M 461.581967 -231.562264 \n",
       "L 406.27148 -215.156151 \n",
       "L 380.001185 -202.358413 \n",
       "L 416.655658 -190.031757 \n",
       "L 471.550591 -190.966574 \n",
       "L 527.217362 -209.14924 \n",
       "L 497.897912 -220.761161 \n",
       "L 461.581967 -231.562264 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m69d7806c1f\" x=\"0\" y=\"308.278125\" style=\"fill: #f0f0f0; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_55\">\n",
       "    <defs>\n",
       "     <path id=\"mc2f1b318ec\" d=\"M 457.660005 -233.240218 \n",
       "L 402.15774 -216.884872 \n",
       "L 380.092903 -203.38268 \n",
       "L 416.840809 -191.052791 \n",
       "L 471.239273 -193.836971 \n",
       "L 526.840759 -211.884448 \n",
       "L 493.906118 -222.472643 \n",
       "L 457.660005 -233.240218 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mc2f1b318ec\" x=\"0\" y=\"308.278125\" style=\"fill: #f2f2f2; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_56\">\n",
       "    <defs>\n",
       "     <path id=\"m41ac8064a8\" d=\"M 453.794007 -234.800463 \n",
       "L 398.085624 -218.486768 \n",
       "L 380.478885 -204.426467 \n",
       "L 417.327373 -192.094252 \n",
       "L 470.633009 -196.684051 \n",
       "L 526.182392 -214.59816 \n",
       "L 488.336671 -225.798303 \n",
       "L 453.794007 -234.800463 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m41ac8064a8\" x=\"0\" y=\"308.278125\" style=\"fill: #f4f4f4; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_57\">\n",
       "    <defs>\n",
       "     <path id=\"m5d034af387\" d=\"M 450.02333 -236.246591 \n",
       "L 394.096115 -219.965675 \n",
       "L 381.156487 -205.499344 \n",
       "L 418.111893 -193.166236 \n",
       "L 469.73963 -199.498409 \n",
       "L 525.250857 -217.281669 \n",
       "L 487.476304 -228.400939 \n",
       "L 450.02333 -236.246591 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m5d034af387\" x=\"0\" y=\"308.278125\" style=\"fill: #f6f6f6; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_58\">\n",
       "    <defs>\n",
       "     <path id=\"m639229fe8f\" d=\"M 446.386641 -237.583266 \n",
       "L 390.229648 -221.326585 \n",
       "L 382.119726 -206.610607 \n",
       "L 419.187481 -194.278556 \n",
       "L 468.56993 -202.271189 \n",
       "L 524.057564 -219.926773 \n",
       "L 486.357897 -230.967089 \n",
       "L 446.386641 -237.583266 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m639229fe8f\" x=\"0\" y=\"308.278125\" style=\"fill: #f9f9f9; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_59\">\n",
       "    <defs>\n",
       "     <path id=\"mf28a5a778b\" d=\"M 442.921611 -238.816196 \n",
       "L 386.525794 -222.575604 \n",
       "L 383.359267 -207.76917 \n",
       "L 420.543825 -195.440627 \n",
       "L 467.137495 -204.994157 \n",
       "L 522.616566 -222.525846 \n",
       "L 484.994464 -233.489491 \n",
       "L 442.921611 -238.816196 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#mf28a5a778b\" x=\"0\" y=\"308.278125\" style=\"fill: #fbfbfb; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"Poly3DCollection_60\">\n",
       "    <defs>\n",
       "     <path id=\"m264160e827\" d=\"M 439.664599 -239.952088 \n",
       "L 383.022939 -223.719913 \n",
       "L 384.862475 -208.983449 \n",
       "L 422.167233 -196.661341 \n",
       "L 465.458504 -207.659775 \n",
       "L 520.944362 -225.071898 \n",
       "L 483.401455 -235.961494 \n",
       "L 439.664599 -239.952088 \n",
       "z\n",
       "\" style=\"stroke: #000000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p287c95b996)\">\n",
       "     <use xlink:href=\"#m264160e827\" x=\"0\" y=\"308.278125\" style=\"fill: #fdfdfd; stroke: #000000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       " </g>\n",
       " <defs>\n",
       "  <clipPath id=\"p0d04d6844a\">\n",
       "   <rect x=\"28.942188\" y=\"7.2\" width=\"253.636364\" height=\"277.2\"/>\n",
       "  </clipPath>\n",
       "  <clipPath id=\"p287c95b996\">\n",
       "   <rect x=\"333.305824\" y=\"18.981818\" width=\"253.636364\" height=\"253.636364\"/>\n",
       "  </clipPath>\n",
       " </defs>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<Figure size 1000x500 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#this code shows the C-obstacle slices for a translating and rotating triangle\n",
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format = 'svg'\n",
    "import numpy as np\n",
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.colors as colors\n",
    "from mpl_toolkits.mplot3d import Axes3D\n",
    "from matplotlib.collections import PolyCollection\n",
    "\n",
    "def convex_polygon_sort(A):\n",
    "    \"\"\"If A is a convex polygon, given by a list of points in CCW order\n",
    "    but not necessarily sorted by increasing angle from the x axis,\n",
    "    this will return a sorted version for use in convex_minkowski_sum.\n",
    "    \"\"\"\n",
    "    i = np.argmin([v[1] for v in A])\n",
    "    return A[i:] + A[:i]\n",
    "\n",
    "def convex_minkowski_sum(A,B):\n",
    "    \"\"\"A and B are convex polygons, given by lists of points sorted\n",
    "    by their angle about the minimum.  The output is a convex polygon\n",
    "    in the same format.\n",
    "    \"\"\"\n",
    "    aprogress = 0\n",
    "    bprogress = 0\n",
    "    res = []\n",
    "    d = np.array([0,-1])\n",
    "    res.append(A[aprogress] + B[bprogress])\n",
    "    while aprogress < len(A) or bprogress < len(B):\n",
    "        aindex = aprogress%len(A)\n",
    "        bindex = bprogress%len(B)\n",
    "        anext = (aprogress + 1)%len(A)\n",
    "        bnext = (bprogress + 1)%len(B)\n",
    "        #find minimum angle\n",
    "        if np.dot(d, A[anext] + B[bindex] - res[-1]) > np.dot(d, A[aindex] + B[bnext] - res[-1]):\n",
    "            res.append(A[anext] + B[bindex])\n",
    "            d = res[-1] - res[-2]\n",
    "            aprogress += 1\n",
    "        else:\n",
    "            res.append(A[aindex] + B[bnext])\n",
    "            d = res[-1] - res[-2]\n",
    "            bprogress += 1\n",
    "    return res\n",
    "\n",
    "#triangle\n",
    "A = [np.array([-1,0]),np.array([1,0]),np.array([0,1.5])]\n",
    "#rectangle\n",
    "B = [np.array([3,2]),np.array([6,2]),np.array([6,4]),np.array([3,4])]\n",
    "#minkowski sum\n",
    "C = convex_minkowski_sum(convex_polygon_sort([-v for v in A]),convex_polygon_sort(B))\n",
    "\n",
    "# set up a figure twice as wide as it is tall\n",
    "fig = plt.figure(figsize=(10,5))\n",
    "ax1 = fig.add_subplot(1, 2, 1)\n",
    "ax2 = fig.add_subplot(1, 2, 2, projection='3d')\n",
    "ax1.axis('equal')\n",
    "ax1.scatter([0],[0],color='k',label='Reference point')\n",
    "ax1.plot(np.array(A+[A[0]])[:,0],np.array(A+[A[0]])[:,1],label='A')\n",
    "ax1.plot(np.array(B+[B[0]])[:,0],np.array(B+[B[0]])[:,1],label='B')\n",
    "ax1.plot(np.array(C+[C[0]])[:,0],np.array(C+[C[0]])[:,1],label='A - B')\n",
    "ax1.legend()\n",
    "\n",
    "ax2.set_xlim(1,7)\n",
    "ax2.set_ylim(0,6)\n",
    "ax2.set_zlim(0,math.pi*2)\n",
    "ax2.set_xlabel('x')\n",
    "ax2.set_ylabel('y')\n",
    "ax2.set_zlabel(r'$\\theta$')\n",
    "ax2.view_init(elev=20, azim=45)\n",
    "Nslices = 60\n",
    "for i in range(Nslices):\n",
    "    u = float(i)/Nslices\n",
    "    theta = u*math.pi*2\n",
    "    R = np.array([[math.cos(theta),-math.sin(theta)],[math.sin(theta),math.cos(theta)]])\n",
    "    RnA = [-np.dot(R,v) for v in A]\n",
    "    C = convex_minkowski_sum(convex_polygon_sort(RnA),B)\n",
    "    #output C at height theta\n",
    "    tri = PolyCollection([np.array(C)])\n",
    "    tri.set_color(colors.rgb2hex([0.5+0.5*u,0.5+0.5*u,0.5+0.5*u]))\n",
    "    tri.set_edgecolor('k')\n",
    "    ax2.add_collection3d(tri,zs=theta)\n",
    "    \n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Motion planning in SE(2)\n",
    "\n",
    "Although some exact geometric techniques have been developed for planning in\n",
    "SE(2), it is more common to adopt resolution-complete techniques to\n",
    "handle the rotational DOF. As an example, grid search can be applied\n",
    "fairly easily.\n",
    "\n",
    "To apply grid search, the $\\theta$ dimension is split into several\n",
    "divisions on a grid over $[0,2\\pi)$, in addition to the $x$ and $y$\n",
    "dimensions. This gives a 3D grid graph that can be handled via search.\n",
    "To properly handle the topology of SO(2), vertices just below\n",
    "$\\theta=2\\pi$ are connected to the ones at $\\theta=0$. Specifically,\n",
    "suppose we have constructed a grid $(x_i,y_j,\\theta_k)$ with indices\n",
    "$i=1,\\ldots,m$, $j=1,\\ldots,n$, and $k=1,\\ldots,p$. We have\n",
    "$x_i = (i-1)\\Delta x$, $y_j=(j-1)\\Delta y$, and\n",
    "$\\theta_k= (k-1)\\Delta \\theta$, with $k=2\\pi/p$. Then, for each\n",
    "$i=1,\\ldots,m$, $j=1,\\ldots,n$ and $k=1,\\ldots,p$, the graph has an edge\n",
    "from each $(x_i,y_j,\\theta_k)$ to $(x_{i+1},y_j,\\theta_k)$ and\n",
    "$(x_i,y_{j+1},\\theta_k)$ (as long as that incremented index does not\n",
    "exceed the limit), and $(x_i,y_j,\\theta_{k+1\\mod p})$. This leads to at\n",
    "most 6 connections per vertex. Diagonal motions can also be added, which\n",
    "results in 26-connected vertices (each vertex can be thought of being in\n",
    "the center of a $3\\times 3\\times 3$ box).\n",
    "\n",
    "Note that when applying search, a cost function needs to be assigned to\n",
    "each edge. Because translation is measured in different units (say,\n",
    "meters) than orientation (degrees or radians), it may not make much\n",
    "sense to use Euclidean distance as the cost! As an extreme example, let\n",
    "us assume that orientation is measured in degrees and translation in\n",
    "meters, and suppose the robot would need to turn $90^\\circ$ to pass\n",
    "through a narrow gap, then rotate back $90^\\circ$ to reach a goal 1 m\n",
    "away. A planner using Euclidean distance would prefer to take a\n",
    "roundabout path (up to 180 m longer!) to get to the goal without\n",
    "reorientation. At a different extreme, let us assume that orientation is\n",
    "measured in radians and translation in millimeters. Then, the robot\n",
    "would prefer to pass through the gap even when there exists a slightly\n",
    "longer path that does not require reorientation.\n",
    "\n",
    "As a result it is usually prudent to adopt a *weighted metric* as cost,\n",
    "such as the following:\n",
    "$$c((x,y,\\theta),(x^\\prime,y^\\prime,\\theta^\\prime)) = \\sqrt{(x-x^\\prime)^2+(y-y^\\prime)^2+w_\\theta diff(\\theta,\\theta^\\prime)^2}.$$\n",
    "Here, $diff$ is the geodesic angular distance in SO(2), and the weight\n",
    "term $w_\\theta$ should be chosen to balance the tradeoff between\n",
    "translation and rotation. One reasonable choice is to set\n",
    "$w_\\theta = R^2$ where $R$ is the radius of the robot. For axis-aligned\n",
    "motions, this weighted cost bounds the maximum distance that a point on\n",
    "the robot could move during a straight line motion\n",
    "$(x,y,\\theta)\\rightarrow (x^\\prime,y^\\prime,\\theta^\\prime)$.\n",
    "\n",
    "Cell decomposition can also be extended in a resolution-complete fashion\n",
    "to SE(2) by splitting $\\theta$ into discrete values, and thinking of the\n",
    "$(x,y)$ plane as a \"layer\" in 3D space. The C-obstacle for that layer\n",
    "can be computed using Minkowski sums, and then its cell decomposition\n",
    "computed. Then, an edge is added to connect cells on adjacent layers\n",
    "whose $(x,y)$ projections overlap. This layered cell graph can then be\n",
    "searched to connect any two points in SE(2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Summary\n",
    "-------\n",
    "\n",
    "### Key takeaways\n",
    "\n",
    "* Geometric motion planning methods can achieve completeness or resolution completeness in low-dimensional configuration spaces.\n",
    "* The major classes of geometric planners are bug methods, grid search, visibility graph methods, and cell decomposition.\n",
    "* Bug algorithms only use local information about obstacles and a small amount of memory to make decisions on-line.  They are sufficiently simple that their completeness and suboptimality can be analyzed using geometric reasoning.\n",
    "* Grid search methods are quite general, can be applied to robots with arbitrary geometry, and can be extended to solve curvature-constrained problems using the state lattice approach.  They are resolution-complete, and their performance depends heavily on the grid resolution, and somewhat on the grid search heuristic.\n",
    "* Visibility graph methods build a network of free paths between obstacle vertices. They are complete and optimal in 2D configuration spaces, but take at least $O(n^2)$ time and $O(n^2)$ space to build.\n",
    "* Cell decomposition methods build a representation of the free space volume as a collection of simple geometric shapes. They can be complete, optimal, and constructed efficiently ($O(n \\log n)$ for the trapezoidal decomposition).\n",
    "* Translating robots with geometry can be converted into point robot problems by constructing C-obstacles. This can be done using the Minkowski difference operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Glossary\n",
    "\n",
    "* Planar path planning\n",
    "* Bug algorithms\n",
    "* Grid search\n",
    "* Visibility graph\n",
    "* Cell decomposition\n",
    "* Trapezoidal decomposition\n",
    "* C-obstacle\n",
    "* Minkowski difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Exercises\n",
    "---------\n",
    "\n",
    "1.  If all obstacles are convex and non-overlapping, is the Bug 1\n",
    "    complete? If so, prove it. If not, produce a counterexample.\n",
    "\n",
    "2.  Suppose that the bug had a $360^\\circ$ distance sensor with some\n",
    "    maximum range $R$ to detect the shape of obstacles around it.\n",
    "    Specifically, suppose that it knows the shape of all obstacles in a\n",
    "    circle of radius $R$. Could you modify Bug 1 so that the bug can\n",
    "    reach the goal with a shorter path (when it terminates)? Bug 1\n",
    "    should be equivalent to your new algorithm when $R=0$. Prove that\n",
    "    your method produces paths of length no longer than paths produced\n",
    "    by Bug 1.\n",
    "\n",
    "3.  Prove that the minimum length path in a polygonal environment is\n",
    "    either a straight line or passes through obstacle vertices. Then\n",
    "    prove that the visibility graph method yields a path with minimum\n",
    "    length. _Hint: consider whether a locally suboptimal path can be\n",
    "    improved by \"shortcutting\" one of the corners of the path._\n",
    "\n",
    "4.  Is grid search with 4-connected neighbors in a plane approximately\n",
    "    optimal, provided that clearance is sufficiently large, and the\n",
    "    length of an optimal path is greater than the grid resolution? If\n",
    "    so, derive an approximation factor. If not, show a class of\n",
    "    environments in which an arbitrarily poor approximation factor can\n",
    "    be constructed.\n",
    "\n",
    "5.  Create a modified `grid_search` algorithm in `rsbook_code.planning.grid_search`\n",
    "    that accepts a `max_time` parameter that gives a maximum time budget\n",
    "    for search.  After this amount of time has elapsed, no more nodes\n",
    "    should be evaluated, and instead the algorithm should return the path\n",
    "    leading to the explored node that got closest to the goal. \n",
    "    _Hint: you can raise an exception to break out of the search loop._\n",
    "\n",
    "6.  The *medial axis* of the free space is the set of free points that are equidistant between exactly \n",
    "    two or more points on the obstacle boundary.  Draw the medial axis of the simple environment in Fig. 1.\n",
    "    Could the medial axis be considered a form of roadmap?  Describe a path planning algorithm that could\n",
    "    accept a medial axis as input and produce a path.\n",
    "\n",
    "7.  Prove that the medial axis of a free space with polygonal obstacles consists of straight lines and\n",
    "    parabolic arcs.  (Hint: recall the focus and directrix that define a parabola.)\n",
    "\n",
    "8.  Give pseudocode for computing the Minkowski sum of two convex\n",
    "    polygons in O($m+n$) time.\n",
    "\n",
    "9.  What is the configuration space of two disk-shaped mobile robots\n",
    "    that can translate in the plane? What C-space obstacles exist in\n",
    "    this space, assuming they are not allowed to collide with the\n",
    "    environment or each other? Extend your description of the C-space\n",
    "    and C-space obstacles to $n$ robots.\n",
    "\n",
    "10. Suppose $R$ is the maximum radius of the robot with respect to its\n",
    "    reference point. Produce a cost metric for SE(2) that bounds the\n",
    "    distance traveled by any point on the robot as it moves from\n",
    "    $(x,y,\\theta)\\rightarrow (x^\\prime,y^\\prime,\\theta^\\prime)$ in a\n",
    "    straight-line configuration-space motion.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "remove_cell_html"
    ]
   },
   "source": [
    "## Interactive quiz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "code_folding": [
     0
    ],
    "tags": [
     "remove_cell_html"
    ]
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link rel=\"stylesheet\" href=\"//stackpath.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css\"/>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "eacbe827cc6a463f8a51ec9caa82c964",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(HTML(value='<style>\\n            .correct { background:#8f8;padding:10px 25px 10px 25px;width:4…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#This code must be run from the RoboticSystemsBook folder\n",
    "\n",
    "# If you are running on Google Colab, uncomment the following code:\n",
    "#\n",
    "# %cd ~\n",
    "# !git clone --depth 1 https://github.com/krishauser/RoboticSystemsBook\n",
    "# %cd RoboticSystemsBook\n",
    "\n",
    "from rsbook_code.assessment import quiz\n",
    "quiz.show(\"geometric_motion_planning\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interactive examples\n",
    "\n",
    "The following examples require [Numpy](https://numpy.org/) and [Matplotlib](https://matplotlib.org/) to be installed on your system, and for your Jupyter notebook to be run in the same folder containing this iPython notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [],
   "source": [
    "#If you are using Google Colab, first uncomment and run the following code\n",
    "\n",
    "# %cd ~\n",
    "# !git clone --depth 1 https://github.com/krishauser/RoboticSystemsBook\n",
    "# %cd RoboticSystemsBook\n",
    "# import rsbook_code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Grid search\n",
    "\n",
    "The following example shows a 2D grid search amongst obstacles.  The cost-to-come from the start is shown as a heatmap for all reached nodes in the grid.\n",
    "\n",
    "Try changing the resolution to examine its effect on running time and solution quality. (0.5, 0.1, or 0.025 are good to try)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "code_folding": [
     0
    ]
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "grid_search: search computed path with 28 nodes, cost 7.609087296526012 taking time: 0.06352496147155762\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       "  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"479.662187pt\" height=\"474.598125pt\" viewBox=\"0 0 479.662187 474.598125\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n",
       " <metadata>\n",
       "  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n",
       "   <cc:Work>\n",
       "    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n",
       "    <dc:date>2023-08-27T23:47:16.087696</dc:date>\n",
       "    <dc:format>image/svg+xml</dc:format>\n",
       "    <dc:creator>\n",
       "     <cc:Agent>\n",
       "      <dc:title>Matplotlib v3.7.1, https://matplotlib.org/</dc:title>\n",
       "     </cc:Agent>\n",
       "    </dc:creator>\n",
       "   </cc:Work>\n",
       "  </rdf:RDF>\n",
       " </metadata>\n",
       " <defs>\n",
       "  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n",
       " </defs>\n",
       " <g id=\"figure_1\">\n",
       "  <g id=\"patch_1\">\n",
       "   <path d=\"M 0 474.598125 \n",
       "L 479.662187 474.598125 \n",
       "L 479.662187 0 \n",
       "L 0 0 \n",
       "z\n",
       "\" style=\"fill: #ffffff\"/>\n",
       "  </g>\n",
       "  <g id=\"axes_1\">\n",
       "   <g id=\"patch_2\">\n",
       "    <path d=\"M 28.942188 450.72 \n",
       "L 472.462188 450.72 \n",
       "L 472.462188 7.2 \n",
       "L 28.942188 7.2 \n",
       "z\n",
       "\" style=\"fill: #ffffff\"/>\n",
       "   </g>\n",
       "   <g clip-path=\"url(#p869a668d44)\">\n",
       "    <image xlink:href=\"data:image/png;base64,\n",
       "iVBORw0KGgoAAAANSUhEUgAAACgAAAAoCAYAAACM/rhtAAAC2klEQVR4nO2WPa8cNRSGH4/tuTdipZQ0FEhINOEfIKGU9AhBA23KFHRRREVLFyHxD0iZhoqCVJFS0FBBAQ0NSIhEd3Zm1z7Hh8Kzm6zubvaGTXYp5pUsy/OlZ97XPjZMmjRp0qRJk04pt+8BefCNEVvICSQTPrq9951XqfCim/Ljd4YPoFIBNR+La62tgPLwvhEihBZCBMkQq4PH1iVAefTA8BEXAsQWfKzO5YSJnB7QXZux4d4q4phxkk4LKI+/r9Fem+FChMbXVhRii0l7WkAXAoS2wsXzEbCBUqAobv+if72AxDHWlXPx7JmDkmrUR1azMfLjnFs513hcez5eq+PTAmquLhVdx2qSwAoUq/2RtRlxThBzjbporXtrWLlSxI/ffMu8b1AtZDP6UhhKodfChRaeSOGpFr7KT680oTcATQQnCZMW55oKt5qDRbGiOz/0y7vvWAwNWQqqBZUGFkJ0DnGO4BxtM7biuMXMvqXbC7npoObq2nLAVOqK9h7TcZHs2En+ef89y1JQKURpEC0Mg+B9w80//7gEcTdet+gc2D68LRFbM4AKztedxJ7fSXZE7GdnuKSYKEUKfV/hvN8+Z59Ijf8q2gAMH3zsVgcECxGkxfmIjYC7HPSzc1wSLCvMl4TgiKFBYrP1+Xt2ceWCeukL4eanjqGDoYO+w4YL6Mfx0G0HfOOsQkaPCx4fGnxweH94Yd9+3Oq7WrBjCyGAyF4H6RZYG7BWiKkhe0fw2x18Ge38Rbn/tbE60eRUIVUgpepsP4e+X7cyH9BuiXYLtFuy7BPDQnn7518PsnHnL4ZPvnD08+rmqp/X2JFcgZ9rlusiWTWRguTDC/sLMwif3XH8/dcI2WGjc9b3G3AlCSVr7ZOSpSBqiB4O+FL25y8/t/WcFIGcoe/R+eJZvPMliz4zDMqwEG789vtBEf/nl9OtD80Fj4lWuBHy+g8/Hf9MNmnSpP+x/gW83b+uaiUN9gAAAABJRU5ErkJggg==\" id=\"imageee4da64a33\" transform=\"matrix(11.1 0 0 -11.1 28.942188 450.72)\" style=\"image-rendering:crisp-edges;image-rendering:pixelated\" width=\"40\" height=\"40\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_1\">\n",
       "    <path d=\"M 117.646188 227.62944 \n",
       "L 117.646188 217.872 \n",
       "L 117.646188 206.784 \n",
       "L 128.734188 195.696 \n",
       "L 139.822188 184.608 \n",
       "L 150.910188 173.52 \n",
       "L 150.910188 162.432 \n",
       "L 150.910188 151.344 \n",
       "L 150.910188 140.256 \n",
       "L 161.998188 129.168 \n",
       "L 173.086188 129.168 \n",
       "L 184.174188 129.168 \n",
       "L 195.262188 129.168 \n",
       "L 206.350188 129.168 \n",
       "L 217.438188 129.168 \n",
       "L 228.526188 129.168 \n",
       "L 239.614188 140.256 \n",
       "L 250.702188 151.344 \n",
       "L 261.790188 162.432 \n",
       "L 272.878188 173.52 \n",
       "L 283.966188 184.608 \n",
       "L 295.054188 195.696 \n",
       "L 306.142188 195.696 \n",
       "L 317.230188 195.696 \n",
       "L 328.318188 195.696 \n",
       "L 339.406188 195.696 \n",
       "L 350.494188 184.608 \n",
       "L 354.485868 175.7376 \n",
       "\" clip-path=\"url(#p869a668d44)\" style=\"fill: none; stroke: #0000ff; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_3\">\n",
       "    <path d=\"M 161.998188 317.664 \n",
       "L 206.350188 317.664 \n",
       "L 206.350188 140.256 \n",
       "L 161.998188 140.256 \n",
       "z\n",
       "\" clip-path=\"url(#p869a668d44)\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_4\">\n",
       "    <path d=\"M 295.054188 184.608 \n",
       "L 339.406187 184.608 \n",
       "L 339.406187 95.904 \n",
       "L 295.054188 95.904 \n",
       "z\n",
       "\" clip-path=\"url(#p869a668d44)\"/>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_1\">\n",
       "    <g id=\"xtick_1\">\n",
       "     <g id=\"line2d_2\">\n",
       "      <defs>\n",
       "       <path id=\"m3c3c5a2175\" d=\"M 0 0 \n",
       "L 0 3.5 \n",
       "\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use xlink:href=\"#m3c3c5a2175\" x=\"73.294188\" y=\"450.72\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_1\">\n",
       "      <!-- −4 -->\n",
       "      <g transform=\"translate(65.923094 465.318437) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \n",
       "L 4684 2272 \n",
       "L 4684 1741 \n",
       "L 678 1741 \n",
       "L 678 2272 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \n",
       "L 825 1625 \n",
       "L 2419 1625 \n",
       "L 2419 4116 \n",
       "z\n",
       "M 2253 4666 \n",
       "L 3047 4666 \n",
       "L 3047 1625 \n",
       "L 3713 1625 \n",
       "L 3713 1100 \n",
       "L 3047 1100 \n",
       "L 3047 0 \n",
       "L 2419 0 \n",
       "L 2419 1100 \n",
       "L 313 1100 \n",
       "L 313 1709 \n",
       "L 2253 4666 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use xlink:href=\"#DejaVuSans-34\" x=\"83.789062\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_2\">\n",
       "     <g id=\"line2d_3\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m3c3c5a2175\" x=\"161.998188\" y=\"450.72\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_2\">\n",
       "      <!-- −2 -->\n",
       "      <g transform=\"translate(154.627094 465.318437) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \n",
       "L 3431 531 \n",
       "L 3431 0 \n",
       "L 469 0 \n",
       "L 469 531 \n",
       "Q 828 903 1448 1529 \n",
       "Q 2069 2156 2228 2338 \n",
       "Q 2531 2678 2651 2914 \n",
       "Q 2772 3150 2772 3378 \n",
       "Q 2772 3750 2511 3984 \n",
       "Q 2250 4219 1831 4219 \n",
       "Q 1534 4219 1204 4116 \n",
       "Q 875 4013 500 3803 \n",
       "L 500 4441 \n",
       "Q 881 4594 1212 4672 \n",
       "Q 1544 4750 1819 4750 \n",
       "Q 2544 4750 2975 4387 \n",
       "Q 3406 4025 3406 3419 \n",
       "Q 3406 3131 3298 2873 \n",
       "Q 3191 2616 2906 2266 \n",
       "Q 2828 2175 2409 1742 \n",
       "Q 1991 1309 1228 531 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use xlink:href=\"#DejaVuSans-32\" x=\"83.789062\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_3\">\n",
       "     <g id=\"line2d_4\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m3c3c5a2175\" x=\"250.702188\" y=\"450.72\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_3\">\n",
       "      <!-- 0 -->\n",
       "      <g transform=\"translate(247.520938 465.318437) scale(0.1 -0.1)\">\n",
       "       <defs>\n",
       "        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \n",
       "Q 1547 4250 1301 3770 \n",
       "Q 1056 3291 1056 2328 \n",
       "Q 1056 1369 1301 889 \n",
       "Q 1547 409 2034 409 \n",
       "Q 2525 409 2770 889 \n",
       "Q 3016 1369 3016 2328 \n",
       "Q 3016 3291 2770 3770 \n",
       "Q 2525 4250 2034 4250 \n",
       "z\n",
       "M 2034 4750 \n",
       "Q 2819 4750 3233 4129 \n",
       "Q 3647 3509 3647 2328 \n",
       "Q 3647 1150 3233 529 \n",
       "Q 2819 -91 2034 -91 \n",
       "Q 1250 -91 836 529 \n",
       "Q 422 1150 422 2328 \n",
       "Q 422 3509 836 4129 \n",
       "Q 1250 4750 2034 4750 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       </defs>\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_4\">\n",
       "     <g id=\"line2d_5\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m3c3c5a2175\" x=\"339.406188\" y=\"450.72\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_4\">\n",
       "      <!-- 2 -->\n",
       "      <g transform=\"translate(336.224938 465.318437) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_5\">\n",
       "     <g id=\"line2d_6\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#m3c3c5a2175\" x=\"428.110188\" y=\"450.72\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_5\">\n",
       "      <!-- 4 -->\n",
       "      <g transform=\"translate(424.928938 465.318437) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_2\">\n",
       "    <g id=\"ytick_1\">\n",
       "     <g id=\"line2d_7\">\n",
       "      <defs>\n",
       "       <path id=\"mf723f77151\" d=\"M 0 0 \n",
       "L -3.5 0 \n",
       "\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use xlink:href=\"#mf723f77151\" x=\"28.942188\" y=\"406.368\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_6\">\n",
       "      <!-- −4 -->\n",
       "      <g transform=\"translate(7.2 410.167219) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use xlink:href=\"#DejaVuSans-34\" x=\"83.789062\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_2\">\n",
       "     <g id=\"line2d_8\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#mf723f77151\" x=\"28.942188\" y=\"317.664\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_7\">\n",
       "      <!-- −2 -->\n",
       "      <g transform=\"translate(7.2 321.463219) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-2212\"/>\n",
       "       <use xlink:href=\"#DejaVuSans-32\" x=\"83.789062\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_3\">\n",
       "     <g id=\"line2d_9\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#mf723f77151\" x=\"28.942188\" y=\"228.96\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_8\">\n",
       "      <!-- 0 -->\n",
       "      <g transform=\"translate(15.579688 232.759219) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-30\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_4\">\n",
       "     <g id=\"line2d_10\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#mf723f77151\" x=\"28.942188\" y=\"140.256\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_9\">\n",
       "      <!-- 2 -->\n",
       "      <g transform=\"translate(15.579688 144.055219) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-32\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_5\">\n",
       "     <g id=\"line2d_11\">\n",
       "      <g>\n",
       "       <use xlink:href=\"#mf723f77151\" x=\"28.942188\" y=\"51.552\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_10\">\n",
       "      <!-- 4 -->\n",
       "      <g transform=\"translate(15.579688 55.351219) scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-34\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"PathCollection_1\">\n",
       "    <defs>\n",
       "     <path id=\"me6cff42bad\" d=\"M 0 3 \n",
       "C 0.795609 3 1.55874 2.683901 2.12132 2.12132 \n",
       "C 2.683901 1.55874 3 0.795609 3 0 \n",
       "C 3 -0.795609 2.683901 -1.55874 2.12132 -2.12132 \n",
       "C 1.55874 -2.683901 0.795609 -3 0 -3 \n",
       "C -0.795609 -3 -1.55874 -2.683901 -2.12132 -2.12132 \n",
       "C -2.683901 -1.55874 -3 -0.795609 -3 0 \n",
       "C -3 0.795609 -2.683901 1.55874 -2.12132 2.12132 \n",
       "C -1.55874 2.683901 -0.795609 3 0 3 \n",
       "z\n",
       "\" style=\"stroke: #008000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p869a668d44)\">\n",
       "     <use xlink:href=\"#me6cff42bad\" x=\"117.646188\" y=\"227.62944\" style=\"fill: #008000; stroke: #008000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"PathCollection_2\">\n",
       "    <defs>\n",
       "     <path id=\"mc96165dd56\" d=\"M 0 3 \n",
       "C 0.795609 3 1.55874 2.683901 2.12132 2.12132 \n",
       "C 2.683901 1.55874 3 0.795609 3 0 \n",
       "C 3 -0.795609 2.683901 -1.55874 2.12132 -2.12132 \n",
       "C 1.55874 -2.683901 0.795609 -3 0 -3 \n",
       "C -0.795609 -3 -1.55874 -2.683901 -2.12132 -2.12132 \n",
       "C -2.683901 -1.55874 -3 -0.795609 -3 0 \n",
       "C -3 0.795609 -2.683901 1.55874 -2.12132 2.12132 \n",
       "C -1.55874 2.683901 -0.795609 3 0 3 \n",
       "z\n",
       "\" style=\"stroke: #ff0000\"/>\n",
       "    </defs>\n",
       "    <g clip-path=\"url(#p869a668d44)\">\n",
       "     <use xlink:href=\"#mc96165dd56\" x=\"354.485868\" y=\"175.7376\" style=\"fill: #ff0000; stroke: #ff0000\"/>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"patch_5\">\n",
       "    <path d=\"M 28.942188 450.72 \n",
       "L 28.942188 7.2 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_6\">\n",
       "    <path d=\"M 472.462188 450.72 \n",
       "L 472.462188 7.2 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_7\">\n",
       "    <path d=\"M 28.942188 450.72 \n",
       "L 472.462188 450.72 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_8\">\n",
       "    <path d=\"M 28.942188 7.2 \n",
       "L 472.462188 7.2 \n",
       "\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n",
       "   </g>\n",
       "   <g id=\"legend_1\">\n",
       "    <g id=\"patch_9\">\n",
       "     <path d=\"M 410.173125 59.234375 \n",
       "L 465.462188 59.234375 \n",
       "Q 467.462188 59.234375 467.462188 57.234375 \n",
       "L 467.462188 14.2 \n",
       "Q 467.462188 12.2 465.462188 12.2 \n",
       "L 410.173125 12.2 \n",
       "Q 408.173125 12.2 408.173125 14.2 \n",
       "L 408.173125 57.234375 \n",
       "Q 408.173125 59.234375 410.173125 59.234375 \n",
       "z\n",
       "\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n",
       "    </g>\n",
       "    <g id=\"PathCollection_3\">\n",
       "     <g>\n",
       "      <use xlink:href=\"#me6cff42bad\" x=\"422.173125\" y=\"21.173437\" style=\"fill: #008000; stroke: #008000\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"text_11\">\n",
       "     <!-- start -->\n",
       "     <g transform=\"translate(440.173125 23.798437) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \n",
       "L 2834 2853 \n",
       "Q 2591 2978 2328 3040 \n",
       "Q 2066 3103 1784 3103 \n",
       "Q 1356 3103 1142 2972 \n",
       "Q 928 2841 928 2578 \n",
       "Q 928 2378 1081 2264 \n",
       "Q 1234 2150 1697 2047 \n",
       "L 1894 2003 \n",
       "Q 2506 1872 2764 1633 \n",
       "Q 3022 1394 3022 966 \n",
       "Q 3022 478 2636 193 \n",
       "Q 2250 -91 1575 -91 \n",
       "Q 1294 -91 989 -36 \n",
       "Q 684 19 347 128 \n",
       "L 347 722 \n",
       "Q 666 556 975 473 \n",
       "Q 1284 391 1588 391 \n",
       "Q 1994 391 2212 530 \n",
       "Q 2431 669 2431 922 \n",
       "Q 2431 1156 2273 1281 \n",
       "Q 2116 1406 1581 1522 \n",
       "L 1381 1569 \n",
       "Q 847 1681 609 1914 \n",
       "Q 372 2147 372 2553 \n",
       "Q 372 3047 722 3315 \n",
       "Q 1072 3584 1716 3584 \n",
       "Q 2034 3584 2315 3537 \n",
       "Q 2597 3491 2834 3397 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \n",
       "L 1172 3500 \n",
       "L 2356 3500 \n",
       "L 2356 3053 \n",
       "L 1172 3053 \n",
       "L 1172 1153 \n",
       "Q 1172 725 1289 603 \n",
       "Q 1406 481 1766 481 \n",
       "L 2356 481 \n",
       "L 2356 0 \n",
       "L 1766 0 \n",
       "Q 1100 0 847 248 \n",
       "Q 594 497 594 1153 \n",
       "L 594 3053 \n",
       "L 172 3053 \n",
       "L 172 3500 \n",
       "L 594 3500 \n",
       "L 594 4494 \n",
       "L 1172 4494 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \n",
       "Q 1497 1759 1228 1600 \n",
       "Q 959 1441 959 1056 \n",
       "Q 959 750 1161 570 \n",
       "Q 1363 391 1709 391 \n",
       "Q 2188 391 2477 730 \n",
       "Q 2766 1069 2766 1631 \n",
       "L 2766 1759 \n",
       "L 2194 1759 \n",
       "z\n",
       "M 3341 1997 \n",
       "L 3341 0 \n",
       "L 2766 0 \n",
       "L 2766 531 \n",
       "Q 2569 213 2275 61 \n",
       "Q 1981 -91 1556 -91 \n",
       "Q 1019 -91 701 211 \n",
       "Q 384 513 384 1019 \n",
       "Q 384 1609 779 1909 \n",
       "Q 1175 2209 1959 2209 \n",
       "L 2766 2209 \n",
       "L 2766 2266 \n",
       "Q 2766 2663 2505 2880 \n",
       "Q 2244 3097 1772 3097 \n",
       "Q 1472 3097 1187 3025 \n",
       "Q 903 2953 641 2809 \n",
       "L 641 3341 \n",
       "Q 956 3463 1253 3523 \n",
       "Q 1550 3584 1831 3584 \n",
       "Q 2591 3584 2966 3190 \n",
       "Q 3341 2797 3341 1997 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \n",
       "Q 2534 3019 2420 3045 \n",
       "Q 2306 3072 2169 3072 \n",
       "Q 1681 3072 1420 2755 \n",
       "Q 1159 2438 1159 1844 \n",
       "L 1159 0 \n",
       "L 581 0 \n",
       "L 581 3500 \n",
       "L 1159 3500 \n",
       "L 1159 2956 \n",
       "Q 1341 3275 1631 3429 \n",
       "Q 1922 3584 2338 3584 \n",
       "Q 2397 3584 2469 3576 \n",
       "Q 2541 3569 2628 3553 \n",
       "L 2631 2963 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-73\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-74\" x=\"52.099609\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-61\" x=\"91.308594\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-72\" x=\"152.587891\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-74\" x=\"193.701172\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"PathCollection_4\">\n",
       "     <g>\n",
       "      <use xlink:href=\"#mc96165dd56\" x=\"422.173125\" y=\"35.851562\" style=\"fill: #ff0000; stroke: #ff0000\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"text_12\">\n",
       "     <!-- goal -->\n",
       "     <g transform=\"translate(440.173125 38.476562) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \n",
       "Q 2906 2416 2648 2759 \n",
       "Q 2391 3103 1925 3103 \n",
       "Q 1463 3103 1205 2759 \n",
       "Q 947 2416 947 1791 \n",
       "Q 947 1169 1205 825 \n",
       "Q 1463 481 1925 481 \n",
       "Q 2391 481 2648 825 \n",
       "Q 2906 1169 2906 1791 \n",
       "z\n",
       "M 3481 434 \n",
       "Q 3481 -459 3084 -895 \n",
       "Q 2688 -1331 1869 -1331 \n",
       "Q 1566 -1331 1297 -1286 \n",
       "Q 1028 -1241 775 -1147 \n",
       "L 775 -588 \n",
       "Q 1028 -725 1275 -790 \n",
       "Q 1522 -856 1778 -856 \n",
       "Q 2344 -856 2625 -561 \n",
       "Q 2906 -266 2906 331 \n",
       "L 2906 616 \n",
       "Q 2728 306 2450 153 \n",
       "Q 2172 0 1784 0 \n",
       "Q 1141 0 747 490 \n",
       "Q 353 981 353 1791 \n",
       "Q 353 2603 747 3093 \n",
       "Q 1141 3584 1784 3584 \n",
       "Q 2172 3584 2450 3431 \n",
       "Q 2728 3278 2906 2969 \n",
       "L 2906 3500 \n",
       "L 3481 3500 \n",
       "L 3481 434 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \n",
       "Q 1497 3097 1228 2736 \n",
       "Q 959 2375 959 1747 \n",
       "Q 959 1119 1226 758 \n",
       "Q 1494 397 1959 397 \n",
       "Q 2419 397 2687 759 \n",
       "Q 2956 1122 2956 1747 \n",
       "Q 2956 2369 2687 2733 \n",
       "Q 2419 3097 1959 3097 \n",
       "z\n",
       "M 1959 3584 \n",
       "Q 2709 3584 3137 3096 \n",
       "Q 3566 2609 3566 1747 \n",
       "Q 3566 888 3137 398 \n",
       "Q 2709 -91 1959 -91 \n",
       "Q 1206 -91 779 398 \n",
       "Q 353 888 353 1747 \n",
       "Q 353 2609 779 3096 \n",
       "Q 1206 3584 1959 3584 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \n",
       "L 1178 4863 \n",
       "L 1178 0 \n",
       "L 603 0 \n",
       "L 603 4863 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-67\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-6f\" x=\"63.476562\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-61\" x=\"124.658203\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-6c\" x=\"185.9375\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_12\">\n",
       "     <path d=\"M 412.173125 49.654687 \n",
       "L 422.173125 49.654687 \n",
       "L 432.173125 49.654687 \n",
       "\" style=\"fill: none; stroke: #0000ff; stroke-width: 1.5; stroke-linecap: square\"/>\n",
       "    </g>\n",
       "    <g id=\"text_13\">\n",
       "     <!-- path -->\n",
       "     <g transform=\"translate(440.173125 53.154687) scale(0.1 -0.1)\">\n",
       "      <defs>\n",
       "       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \n",
       "L 1159 -1331 \n",
       "L 581 -1331 \n",
       "L 581 3500 \n",
       "L 1159 3500 \n",
       "L 1159 2969 \n",
       "Q 1341 3281 1617 3432 \n",
       "Q 1894 3584 2278 3584 \n",
       "Q 2916 3584 3314 3078 \n",
       "Q 3713 2572 3713 1747 \n",
       "Q 3713 922 3314 415 \n",
       "Q 2916 -91 2278 -91 \n",
       "Q 1894 -91 1617 61 \n",
       "Q 1341 213 1159 525 \n",
       "z\n",
       "M 3116 1747 \n",
       "Q 3116 2381 2855 2742 \n",
       "Q 2594 3103 2138 3103 \n",
       "Q 1681 3103 1420 2742 \n",
       "Q 1159 2381 1159 1747 \n",
       "Q 1159 1113 1420 752 \n",
       "Q 1681 391 2138 391 \n",
       "Q 2594 391 2855 752 \n",
       "Q 3116 1113 3116 1747 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "       <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \n",
       "L 3513 0 \n",
       "L 2938 0 \n",
       "L 2938 2094 \n",
       "Q 2938 2591 2744 2837 \n",
       "Q 2550 3084 2163 3084 \n",
       "Q 1697 3084 1428 2787 \n",
       "Q 1159 2491 1159 1978 \n",
       "L 1159 0 \n",
       "L 581 0 \n",
       "L 581 4863 \n",
       "L 1159 4863 \n",
       "L 1159 2956 \n",
       "Q 1366 3272 1645 3428 \n",
       "Q 1925 3584 2291 3584 \n",
       "Q 2894 3584 3203 3211 \n",
       "Q 3513 2838 3513 2113 \n",
       "z\n",
       "\" transform=\"scale(0.015625)\"/>\n",
       "      </defs>\n",
       "      <use xlink:href=\"#DejaVuSans-70\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-61\" x=\"63.476562\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-74\" x=\"124.755859\"/>\n",
       "      <use xlink:href=\"#DejaVuSans-68\" x=\"163.964844\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       " </g>\n",
       " <defs>\n",
       "  <clipPath id=\"p869a668d44\">\n",
       "   <rect x=\"28.942188\" y=\"7.2\" width=\"443.52\" height=\"443.52\"/>\n",
       "  </clipPath>\n",
       " </defs>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<Figure size 800x800 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#Jupyter notebook must be run from this directory for this code to work.\n",
    "%matplotlib inline\n",
    "\n",
    "from rsbook_code.utilities import graph,example_graphs\n",
    "from rsbook_code.planning import grid_search\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.patches as patches\n",
    "import numpy as np\n",
    "import math\n",
    "\n",
    "#define search problem and obstacle boxes\n",
    "xstart = (-3,0.03)\n",
    "xgoal = (2.34,1.2)\n",
    "xmin = [-5,-5]\n",
    "xmax = [5,5]\n",
    "resolution = 0.25\n",
    "obstacles = [([-2,-2],[-1,2]),([1,1],[2,3])]\n",
    "def in_obstacles(x):\n",
    "    global obstacles\n",
    "    for a,b in obstacles:\n",
    "        if a[0] <= x[0] <= b[0] and a[1] <= x[1] <= b[1]:\n",
    "            return True\n",
    "    return False\n",
    "path,d,p = grid_search.grid_search(xstart,xgoal,xmin,xmax,resolution=resolution,\n",
    "                              obstacle_test = in_obstacles,\n",
    "                              diagonals=True,implicit=True,\n",
    "                              verbose=1)\n",
    "\n",
    "#plot start, goal, and path\n",
    "plt.figure(figsize=(8,8))\n",
    "plt.xlim(xmin[0],xmax[0])\n",
    "plt.ylim(xmin[1],xmax[1])\n",
    "plt.scatter([xstart[0]],[xstart[1]],c='g',zorder=2,label='start')\n",
    "plt.scatter([xgoal[0]],[xgoal[1]],c='r',zorder=2,label='goal')\n",
    "if path is not None:\n",
    "    plt.plot([v[0] for v in path],[v[1] for v in path],c='b',zorder=1,label='path')\n",
    "#plot obstacles\n",
    "for a,b in obstacles:\n",
    "    patch = patches.Rectangle(a,b[0]-a[0],b[1]-a[1],facecolor='k')\n",
    "    plt.gca().add_patch(patch)\n",
    "#plot costs-to-come from start\n",
    "distances = np.ones([int(math.floor((b-a)/resolution)) for (a,b) in zip(xmin,xmax)])*float('inf')\n",
    "for (k,v) in d.items():\n",
    "    if isinstance(k,str): continue\n",
    "    distances[k] = v\n",
    "plt.imshow(distances.T,cmap=plt.cm.Reds, interpolation='none', extent=[xmin[1],xmax[1],xmax[0],xmin[0]])\n",
    "plt.legend()\n",
    "plt.gca().set_aspect('equal', 'box')\n",
    "plt.show()"
   ]
  },
  {
   "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.11.3"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": true,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "298.233px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}