{
"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 \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": [
"\n",
"\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 \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": [
"\n",
"\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
}