examples/operations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These examples illustrate common operations on polyhedra using [Polyhedra.jl](https://github.com/JuliaPolyhedra/Polyhedra.jl):\n",
    "\n",
    "- [Intersection](#Intersection).\n",
    "- [Convex hull](#Convex-hull)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Polyhedra, CDDLib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Intersection <a name=\"Intersection\"></a> \n",
    "\n",
    "Intersection of polyhedra is obtained with the [`intersect`](https://juliapolyhedra.github.io/Polyhedra.jl/latest/utilities.html#Base.intersect) function.\n",
    "\n",
    "Below we compute the intersection of two randomly generated polygons in V-representation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polyhedron CDDLib.Polyhedron{Float64}:\n",
       "15-element iterator of Array{Float64,1}:\n",
       " [0.653435, -0.187627]\n",
       " [0.17263, -0.864529]\n",
       " [1.03956, -0.661604]\n",
       " [-1.98295, -0.124786]\n",
       " [0.471671, 0.729333]\n",
       " [-0.610414, -0.793724]\n",
       " [0.0466702, -1.16875]\n",
       " [0.485415, 0.0210984]\n",
       " [-1.27902, 0.477847]\n",
       " [1.13851, -0.459599]\n",
       " [-0.610409, 0.00688353]\n",
       " [-0.551732, 0.473709]\n",
       " [-0.383, -0.0635651]\n",
       " [0.997255, -1.34599]\n",
       " [-1.69915, -1.55624]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P1 = polyhedron(vrep(randn(15, 2)), CDDLib.Library())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polyhedron CDDLib.Polyhedron{Float64}:\n",
       "15-element iterator of Array{Float64,1}:\n",
       " [0.974105, -0.196659]\n",
       " [-1.22919, -1.09104]\n",
       " [-0.403396, 0.816207]\n",
       " [0.0894763, -1.81554]\n",
       " [-0.222775, 0.818613]\n",
       " [1.65048, 0.607726]\n",
       " [-1.04961, 0.393015]\n",
       " [0.049869, 0.000966454]\n",
       " [0.910763, -0.153303]\n",
       " [-0.690545, 0.949615]\n",
       " [0.616334, 1.49328]\n",
       " [1.15224, -1.66972]\n",
       " [-2.17915, -1.30318]\n",
       " [0.301808, -1.59306]\n",
       " [0.861699, -0.428743]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P2 = polyhedron(vrep(randn(15, 2)), CDDLib.Library())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polyhedron CDDLib.Polyhedron{Float64}:\n",
       "12-element iterator of HalfSpace{Float64,Array{Float64,1}}:\n",
       " HalfSpace([-1.0, 6.96138], 4.605499227456095)\n",
       " HalfSpace([-1.0, 1.16809], 1.837191250573574)\n",
       " HalfSpace([-5.04377, -1.0], 10.12634301193736)\n",
       " HalfSpace([1.0, -12.8242], 18.25844289054684)\n",
       " HalfSpace([6.2751, -1.0], 7.603863621588988)\n",
       " HalfSpace([1.78294, 1.0], 1.5702956517801525)\n",
       " HalfSpace([1.0, -7.28838], 13.321810319849142)\n",
       " HalfSpace([-1.0, 2.40381], 2.9732426844014452)\n",
       " HalfSpace([-1.0, -4.42778], 7.949329654479555)\n",
       " HalfSpace([-1.51336, 1.0], 1.9946590486397917)\n",
       " HalfSpace([1.0, 1.16779], 2.3601791454548358)\n",
       " HalfSpace([4.57099, -1.0], 6.936608902132285)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pint = intersect(P1, P2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While `P1` and `P2` have been constructed from their V-representation, their H-representation has been computed to build the intersection `Pint`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(true, true)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hrepiscomputed(P1), vrepiscomputed(P1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(true, true)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hrepiscomputed(P2), vrepiscomputed(P2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On the other hand, `Pint` is constructed from its H-representation hence its V-representation has not been computed yet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(true, false)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hrepiscomputed(Pint), vrepiscomputed(Pint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can obtain the number of points in the intersection with `npoints` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "npoints(Pint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that this triggers the computation of the V-representation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(true, true)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hrepiscomputed(Pint), vrepiscomputed(Pint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can plot the polygons and their intersection using the `plot` function. For further plotting options see the [Plots.jl](http://docs.juliaplots.org/latest/) documentation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Plots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"600\" height=\"400\" viewBox=\"0 0 2400 1600\">\n",
       "<defs>\n",
       "  <clipPath id=\"clip5400\">\n",
       "    <rect x=\"0\" y=\"0\" width=\"2000\" height=\"2000\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<defs>\n",
       "  <clipPath id=\"clip5401\">\n",
       "    <rect x=\"0\" y=\"0\" width=\"2400\" height=\"1600\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip5401)\" points=\"\n",
       "0,1600 2400,1600 2400,0 0,0 \n",
       "  \" fill=\"#ffffff\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip5402\">\n",
       "    <rect x=\"480\" y=\"0\" width=\"1681\" height=\"1600\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip5401)\" points=\"\n",
       "189.504,1503.47 2321.26,1503.47 2321.26,47.2441 189.504,47.2441 \n",
       "  \" fill=\"#ffffff\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip5403\">\n",
       "    <rect x=\"189\" y=\"47\" width=\"2133\" height=\"1457\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  343.913,1503.47 343.913,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  869.053,1503.47 869.053,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1394.19,1503.47 1394.19,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1919.33,1503.47 1919.33,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,1331.25 2321.26,1331.25 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,1123.65 2321.26,1123.65 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,916.057 2321.26,916.057 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,708.46 2321.26,708.46 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,500.864 2321.26,500.864 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,293.267 2321.26,293.267 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,85.6697 2321.26,85.6697 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1503.47 2321.26,1503.47 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1503.47 189.504,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  343.913,1503.47 343.913,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  869.053,1503.47 869.053,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1394.19,1503.47 1394.19,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1919.33,1503.47 1919.33,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1331.25 221.48,1331.25 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1123.65 221.48,1123.65 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,916.057 221.48,916.057 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,708.46 221.48,708.46 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,500.864 221.48,500.864 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,293.267 221.48,293.267 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5401)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,85.6697 221.48,85.6697 \n",
       "  \"/>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 343.913, 1557.47)\" x=\"343.913\" y=\"1557.47\">-2</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 869.053, 1557.47)\" x=\"869.053\" y=\"1557.47\">-1</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 1394.19, 1557.47)\" x=\"1394.19\" y=\"1557.47\">0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 1919.33, 1557.47)\" x=\"1919.33\" y=\"1557.47\">1</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 1348.75)\" x=\"165.504\" y=\"1348.75\">-1.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 1141.15)\" x=\"165.504\" y=\"1141.15\">-1.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 933.557)\" x=\"165.504\" y=\"933.557\">-0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 725.96)\" x=\"165.504\" y=\"725.96\">0.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 518.364)\" x=\"165.504\" y=\"518.364\">0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 310.767)\" x=\"165.504\" y=\"310.767\">1.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5401)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 103.17)\" x=\"165.504\" y=\"103.17\">1.5</text>\n",
       "</g>\n",
       "<polygon clip-path=\"url(#clip5403)\" points=\"\n",
       "352.865,760.271 722.528,510.061 1641.89,405.646 1992.07,899.283 1992.07,899.283 1917.89,1267.31 501.904,1354.6 352.865,760.271 352.865,760.271 \n",
       "  \" fill=\"#0000ff\" fill-opacity=\"0.2\"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:0.2; fill:none\" points=\"\n",
       "  352.865,760.271 722.528,510.061 1641.89,405.646 1992.07,899.283 1917.89,1267.31 501.904,1354.6 352.865,760.271 \n",
       "  \"/>\n",
       "<polygon clip-path=\"url(#clip5403)\" points=\"\n",
       "249.837,1249.53 1031.56,314.186 1717.86,88.4582 2260.93,456.136 2260.93,456.136 1999.28,1401.72 1441.18,1462.26 249.837,1249.53 249.837,1249.53 \n",
       "  \" fill=\"#ff0000\" fill-opacity=\"0.2\"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:0.2; fill:none\" points=\"\n",
       "  249.837,1249.53 1031.56,314.186 1717.86,88.4582 2260.93,456.136 1999.28,1401.72 1441.18,1462.26 249.837,1249.53 \n",
       "  \"/>\n",
       "<polygon clip-path=\"url(#clip5403)\" points=\"\n",
       "423.46,1041.79 883.098,491.825 1641.89,405.646 1992.07,899.283 1992.07,899.283 1917.89,1267.31 751.94,1339.19 486.136,1291.73 423.46,1041.79 423.46,1041.79 \n",
       "  \n",
       "  \" fill=\"#ffff00\" fill-opacity=\"0.6\"/>\n",
       "<polyline clip-path=\"url(#clip5403)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:0.6; fill:none\" points=\"\n",
       "  423.46,1041.79 883.098,491.825 1641.89,405.646 1992.07,899.283 1917.89,1267.31 751.94,1339.19 486.136,1291.73 423.46,1041.79 \n",
       "  \n",
       "  \"/>\n",
       "</svg>\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plot(P1, alpha=0.2, color=\"blue\")\n",
    "plot!(P2, color=\"red\", alpha=0.2)\n",
    "plot!(Pint, color=\"yellow\", alpha=0.6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convex hull <a name=\"Convex-hull\"></a> \n",
    "\n",
    "The binary convex hull operation between two polyhedra is obtained with the [`convexhull`](https://juliapolyhedra.github.io/Polyhedra.jl/latest/utilities.html#Polyhedra.convexhull) function.\n",
    "\n",
    "Below we compute the convex hull of the two randomly generated polygons in V-representation from the previous example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polyhedron CDDLib.Polyhedron{Float64}:\n",
       "12-element iterator of Array{Float64,1}:\n",
       " [-1.98295, -0.124786]\n",
       " [0.471671, 0.729333]\n",
       " [-1.27902, 0.477847]\n",
       " [1.13851, -0.459599]\n",
       " [0.997255, -1.34599]\n",
       " [-1.69915, -1.55624]\n",
       " [0.0894763, -1.81554]\n",
       " [1.65048, 0.607726]\n",
       " [-0.690545, 0.949615]\n",
       " [0.616334, 1.49328]\n",
       " [1.15224, -1.66972]\n",
       " [-2.17915, -1.30318]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Pch = convexhull(P1, P2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "npoints(Pch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"600\" height=\"400\" viewBox=\"0 0 2400 1600\">\n",
       "<defs>\n",
       "  <clipPath id=\"clip5600\">\n",
       "    <rect x=\"0\" y=\"0\" width=\"2000\" height=\"2000\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<defs>\n",
       "  <clipPath id=\"clip5601\">\n",
       "    <rect x=\"0\" y=\"0\" width=\"2400\" height=\"1600\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip5601)\" points=\"\n",
       "0,1600 2400,1600 2400,0 0,0 \n",
       "  \" fill=\"#ffffff\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip5602\">\n",
       "    <rect x=\"480\" y=\"0\" width=\"1681\" height=\"1600\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip5601)\" points=\"\n",
       "189.504,1503.47 2321.26,1503.47 2321.26,47.2441 189.504,47.2441 \n",
       "  \" fill=\"#ffffff\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip5603\">\n",
       "    <rect x=\"189\" y=\"47\" width=\"2133\" height=\"1457\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  343.913,1503.47 343.913,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  869.053,1503.47 869.053,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1394.19,1503.47 1394.19,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1919.33,1503.47 1919.33,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,1331.25 2321.26,1331.25 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,1123.65 2321.26,1123.65 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,916.057 2321.26,916.057 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,708.46 2321.26,708.46 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,500.864 2321.26,500.864 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,293.267 2321.26,293.267 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  189.504,85.6697 2321.26,85.6697 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1503.47 2321.26,1503.47 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1503.47 189.504,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  343.913,1503.47 343.913,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  869.053,1503.47 869.053,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1394.19,1503.47 1394.19,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1919.33,1503.47 1919.33,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1331.25 221.48,1331.25 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,1123.65 221.48,1123.65 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,916.057 221.48,916.057 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,708.46 221.48,708.46 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,500.864 221.48,500.864 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,293.267 221.48,293.267 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip5601)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  189.504,85.6697 221.48,85.6697 \n",
       "  \"/>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 343.913, 1557.47)\" x=\"343.913\" y=\"1557.47\">-2</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 869.053, 1557.47)\" x=\"869.053\" y=\"1557.47\">-1</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 1394.19, 1557.47)\" x=\"1394.19\" y=\"1557.47\">0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:middle;\" transform=\"rotate(0, 1919.33, 1557.47)\" x=\"1919.33\" y=\"1557.47\">1</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 1348.75)\" x=\"165.504\" y=\"1348.75\">-1.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 1141.15)\" x=\"165.504\" y=\"1141.15\">-1.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 933.557)\" x=\"165.504\" y=\"933.557\">-0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 725.96)\" x=\"165.504\" y=\"725.96\">0.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 518.364)\" x=\"165.504\" y=\"518.364\">0.5</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 310.767)\" x=\"165.504\" y=\"310.767\">1.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip5601)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48; text-anchor:end;\" transform=\"rotate(0, 165.504, 103.17)\" x=\"165.504\" y=\"103.17\">1.5</text>\n",
       "</g>\n",
       "<polygon clip-path=\"url(#clip5603)\" points=\"\n",
       "352.865,760.271 722.528,510.061 1641.89,405.646 1992.07,899.283 1992.07,899.283 1917.89,1267.31 501.904,1354.6 352.865,760.271 352.865,760.271 \n",
       "  \" fill=\"#0000ff\" fill-opacity=\"0.2\"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:0.2; fill:none\" points=\"\n",
       "  352.865,760.271 722.528,510.061 1641.89,405.646 1992.07,899.283 1917.89,1267.31 501.904,1354.6 352.865,760.271 \n",
       "  \"/>\n",
       "<polygon clip-path=\"url(#clip5603)\" points=\"\n",
       "249.837,1249.53 1031.56,314.186 1717.86,88.4582 2260.93,456.136 2260.93,456.136 1999.28,1401.72 1441.18,1462.26 249.837,1249.53 249.837,1249.53 \n",
       "  \" fill=\"#ff0000\" fill-opacity=\"0.2\"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:0.2; fill:none\" points=\"\n",
       "  249.837,1249.53 1031.56,314.186 1717.86,88.4582 2260.93,456.136 1999.28,1401.72 1441.18,1462.26 249.837,1249.53 \n",
       "  \"/>\n",
       "<polygon clip-path=\"url(#clip5603)\" points=\"\n",
       "249.837,1249.53 352.865,760.271 722.528,510.061 1031.56,314.186 1717.86,88.4582 2260.93,456.136 2260.93,456.136 1999.28,1401.72 1441.18,1462.26 501.904,1354.6 \n",
       "  249.837,1249.53 249.837,1249.53 \n",
       "  \" fill=\"#008000\" fill-opacity=\"0.1\"/>\n",
       "<polyline clip-path=\"url(#clip5603)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  249.837,1249.53 352.865,760.271 722.528,510.061 1031.56,314.186 1717.86,88.4582 2260.93,456.136 1999.28,1401.72 1441.18,1462.26 501.904,1354.6 \n",
       "  249.837,1249.53 \n",
       "  \"/>\n",
       "</svg>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plot(P1, alpha=0.2, color=\"blue\")\n",
    "plot!(P2, color=\"red\", alpha=0.2)\n",
    "plot!(Pch, color=\"green\", alpha=0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the convex hull operation is done in the V-representation so no representation conversion is needed for this operation since `P1` and `P2` where constructed from their V-representation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(true, true, true)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hrepiscomputed(P1), hrepiscomputed(P2), hrepiscomputed(Pint)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us note that the `convexhull` of a V-representation contains points and rays and represents the convex hull\n",
    "of the points together with the conic hull of the rays. So, `convexhull(P1, P2)` does the union of the vertices:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polyhedron CDDLib.Polyhedron{Float64}:\n",
       "15-element iterator of Array{Float64,1}:\n",
       " [0.965939, -0.408821]\n",
       " [0.0423453, -2.35475]\n",
       " [0.445098, 0.496043]\n",
       " [-0.503593, -0.643319]\n",
       " [0.275412, 0.958958]\n",
       " [1.52787, 0.765889]\n",
       " [2.32907, 0.508292]\n",
       " [0.976168, -0.213605]\n",
       " [-1.2088, 0.561409]\n",
       " [0.0899901, -1.99332]\n",
       " [-0.436715, -0.0207767]\n",
       " [-0.915581, -0.307397]\n",
       " [0.162809, -0.899802]\n",
       " [1.89527, 0.417177]\n",
       " [-1.19564, 0.680285]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# each of Q1 and Q2 has 15 vertices\n",
    "Q1 = polyhedron(vrep(randn(15, 2)), CDDLib.Library())\n",
    "Q2 = polyhedron(vrep(randn(15, 2)), CDDLib.Library())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check that their convex hull has 30 vertices\n",
    "Qch = convexhull(Q1, Q2)\n",
    "npoints(Qch)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, if we want to remove the redundant points we can use `removevredundancy!`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "removevredundancy!(Qch)\n",
    "npoints(Qch)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.0.2",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}