1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>convex_hull</title> 5<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../index.html" title="Chapter 1. Geometry"> 8<link rel="up" href="../algorithms.html" title="Algorithms"> 9<link rel="prev" href="convert.html" title="convert"> 10<link rel="next" href="correct.html" title="correct"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="convert.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../algorithms.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="correct.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h4 class="title"> 27<a name="geometry.reference.algorithms.convex_hull"></a><a class="link" href="convex_hull.html" title="convex_hull">convex_hull</a> 28</h4></div></div></div> 29<p> 30 <a class="indexterm" name="idm45635704328880"></a> 31Calculates the convex hull of a geometry. 32 </p> 33<h6> 34<a name="geometry.reference.algorithms.convex_hull.h0"></a> 35 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.description"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.description">Description</a> 36 </h6> 37<p> 38 The free function convex_hull calculates the convex hull of a geometry. 39 </p> 40<h6> 41<a name="geometry.reference.algorithms.convex_hull.h1"></a> 42 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.synopsis"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.synopsis">Synopsis</a> 43 </h6> 44<p> 45</p> 46<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Geometry</span><span class="special">,</span> <span class="keyword">typename</span> <span class="identifier">OutputGeometry</span><span class="special">></span> 47<span class="keyword">void</span> <span class="identifier">convex_hull</span><span class="special">(</span><span class="identifier">Geometry</span> <span class="keyword">const</span> <span class="special">&</span> <span class="identifier">geometry</span><span class="special">,</span> <span class="identifier">OutputGeometry</span> <span class="special">&</span> <span class="identifier">hull</span><span class="special">)</span></pre> 48<p> 49 </p> 50<h6> 51<a name="geometry.reference.algorithms.convex_hull.h2"></a> 52 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.parameters"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.parameters">Parameters</a> 53 </h6> 54<div class="informaltable"><table class="table"> 55<colgroup> 56<col> 57<col> 58<col> 59<col> 60</colgroup> 61<thead><tr> 62<th> 63 <p> 64 Type 65 </p> 66 </th> 67<th> 68 <p> 69 Concept 70 </p> 71 </th> 72<th> 73 <p> 74 Name 75 </p> 76 </th> 77<th> 78 <p> 79 Description 80 </p> 81 </th> 82</tr></thead> 83<tbody> 84<tr> 85<td> 86 <p> 87 Geometry const & 88 </p> 89 </td> 90<td> 91 <p> 92 the input geometry type 93 </p> 94 </td> 95<td> 96 <p> 97 geometry 98 </p> 99 </td> 100<td> 101 <p> 102 A model of the specified concept, input geometry 103 </p> 104 </td> 105</tr> 106<tr> 107<td> 108 <p> 109 OutputGeometry & 110 </p> 111 </td> 112<td> 113 <p> 114 the output geometry type 115 </p> 116 </td> 117<td> 118 <p> 119 hull 120 </p> 121 </td> 122<td> 123 <p> 124 A model of the specified concept which is set to the convex hull 125 </p> 126 </td> 127</tr> 128</tbody> 129</table></div> 130<h6> 131<a name="geometry.reference.algorithms.convex_hull.h3"></a> 132 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.header"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.header">Header</a> 133 </h6> 134<p> 135 Either 136 </p> 137<p> 138 <code class="computeroutput"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code> 139 </p> 140<p> 141 Or 142 </p> 143<p> 144 <code class="computeroutput"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">algorithms</span><span class="special">/</span><span class="identifier">convex_hull</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code> 145 </p> 146<h6> 147<a name="geometry.reference.algorithms.convex_hull.h4"></a> 148 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.conformance"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.conformance">Conformance</a> 149 </h6> 150<p> 151 The function convex_hull implements function ConvexHull() from the <a href="http://www.opengeospatial.org/standards/sfa" target="_top">OGC Simple Feature Specification</a>. 152 </p> 153<h6> 154<a name="geometry.reference.algorithms.convex_hull.h5"></a> 155 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.supported_geometries"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.supported_geometries">Supported 156 geometries</a> 157 </h6> 158<div class="informaltable"><table class="table"> 159<colgroup> 160<col> 161<col> 162</colgroup> 163<thead><tr> 164<th> 165 <p> 166 Geometry 167 </p> 168 </th> 169<th> 170 <p> 171 Status 172 </p> 173 </th> 174</tr></thead> 175<tbody> 176<tr> 177<td> 178 <p> 179 Point 180 </p> 181 </td> 182<td> 183 <p> 184 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 185 </p> 186 </td> 187</tr> 188<tr> 189<td> 190 <p> 191 Segment 192 </p> 193 </td> 194<td> 195 <p> 196 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 197 </p> 198 </td> 199</tr> 200<tr> 201<td> 202 <p> 203 Box 204 </p> 205 </td> 206<td> 207 <p> 208 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 209 </p> 210 </td> 211</tr> 212<tr> 213<td> 214 <p> 215 Linestring 216 </p> 217 </td> 218<td> 219 <p> 220 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 221 </p> 222 </td> 223</tr> 224<tr> 225<td> 226 <p> 227 Ring 228 </p> 229 </td> 230<td> 231 <p> 232 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 233 </p> 234 </td> 235</tr> 236<tr> 237<td> 238 <p> 239 Polygon 240 </p> 241 </td> 242<td> 243 <p> 244 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 245 </p> 246 </td> 247</tr> 248<tr> 249<td> 250 <p> 251 MultiPoint 252 </p> 253 </td> 254<td> 255 <p> 256 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 257 </p> 258 </td> 259</tr> 260<tr> 261<td> 262 <p> 263 MultiLinestring 264 </p> 265 </td> 266<td> 267 <p> 268 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 269 </p> 270 </td> 271</tr> 272<tr> 273<td> 274 <p> 275 MultiPolygon 276 </p> 277 </td> 278<td> 279 <p> 280 <span class="inlinemediaobject"><img src="../../../img/ok.png" alt="ok"></span> 281 </p> 282 </td> 283</tr> 284</tbody> 285</table></div> 286<h6> 287<a name="geometry.reference.algorithms.convex_hull.h6"></a> 288 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.complexity"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.complexity">Complexity</a> 289 </h6> 290<p> 291 Linearithmic 292 </p> 293<h6> 294<a name="geometry.reference.algorithms.convex_hull.h7"></a> 295 <span class="phrase"><a name="geometry.reference.algorithms.convex_hull.example"></a></span><a class="link" href="convex_hull.html#geometry.reference.algorithms.convex_hull.example">Example</a> 296 </h6> 297<p> 298 Shows how to generate the convex_hull of a geometry 299 </p> 300<p> 301</p> 302<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iostream</span><span class="special">></span> 303 304<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 305<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">geometries</span><span class="special">/</span><span class="identifier">polygon</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 306<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">geometry</span><span class="special">/</span><span class="identifier">geometries</span><span class="special">/</span><span class="identifier">adapted</span><span class="special">/</span><span class="identifier">boost_tuple</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 307 308<span class="identifier">BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS</span><span class="special">(</span><span class="identifier">cs</span><span class="special">::</span><span class="identifier">cartesian</span><span class="special">)</span> 309 310 311<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 312<span class="special">{</span> 313 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">tuple</span><span class="special"><</span><span class="keyword">double</span><span class="special">,</span> <span class="keyword">double</span><span class="special">></span> <span class="identifier">point</span><span class="special">;</span> 314 <span class="keyword">typedef</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">model</span><span class="special">::</span><span class="identifier">polygon</span><span class="special"><</span><span class="identifier">point</span><span class="special">></span> <span class="identifier">polygon</span><span class="special">;</span> 315 316 <span class="identifier">polygon</span> <span class="identifier">poly</span><span class="special">;</span> 317 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">read_wkt</span><span class="special">(</span><span class="string">"polygon((2.0 1.3, 2.4 1.7, 2.8 1.8, 3.4 1.2, 3.7 1.6,3.4 2.0, 4.1 3.0"</span> 318 <span class="string">", 5.3 2.6, 5.4 1.2, 4.9 0.8, 2.9 0.7,2.0 1.3))"</span><span class="special">,</span> <span class="identifier">poly</span><span class="special">);</span> 319 320 <span class="identifier">polygon</span> <span class="identifier">hull</span><span class="special">;</span> 321 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">convex_hull</span><span class="special">(</span><span class="identifier">poly</span><span class="special">,</span> <span class="identifier">hull</span><span class="special">);</span> 322 323 <span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">geometry</span><span class="special">::</span><span class="identifier">dsv</span><span class="special">;</span> 324 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> 325 <span class="special"><<</span> <span class="string">"polygon: "</span> <span class="special"><<</span> <span class="identifier">dsv</span><span class="special">(</span><span class="identifier">poly</span><span class="special">)</span> <span class="special"><<</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span> 326 <span class="special"><<</span> <span class="string">"hull: "</span> <span class="special"><<</span> <span class="identifier">dsv</span><span class="special">(</span><span class="identifier">hull</span><span class="special">)</span> <span class="special"><<</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span> 327 <span class="special">;</span> 328 329 330 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 331<span class="special">}</span> 332</pre> 333<p> 334 </p> 335<p> 336 Output: 337 </p> 338<pre class="programlisting">polygon: (((2, 1.3), (2.4, 1.7), (2.8, 1.8), (3.4, 1.2), (3.7, 1.6), (3.4, 2), (4.1, 3), (5.3, 2.6), (5.4, 1.2), (4.9, 0.8), (2.9, 0.7), (2, 1.3))) 339hull: (((2, 1.3), (2.4, 1.7), (4.1, 3), (5.3, 2.6), (5.4, 1.2), (4.9, 0.8), (2.9, 0.7), (2, 1.3))) 340 341<img src="../../../img/algorithms/convex_hull.png" alt="convex_hull"> 342</pre> 343</div> 344<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 345<td align="left"></td> 346<td align="right"><div class="copyright-footer">Copyright © 2009-2019 Barend Gehrels, Bruno Lalande, Mateusz Loskot, Adam 347 Wulkiewicz, Oracle and/or its affiliates<p> 348 Distributed under the Boost Software License, Version 1.0. (See accompanying 349 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 350 </p> 351</div></td> 352</tr></table> 353<hr> 354<div class="spirit-nav"> 355<a accesskey="p" href="convert.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../algorithms.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="correct.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 356</div> 357</body> 358</html> 359
