Boost C++ Libraries: Ticket #9873: Boost.Geometry: boost::geometry::convex_hull makes a convex polygon look concave for certain values https://svn.boost.org/trac10/ticket/9873 <p> The goal is to determine if a polygon is convex. boost::geometry::convex_hull can be used to so: if the polygon equals that points, it is convex. </p> <p> However, convex_hull does make a convex polygon look concave for certain values. </p> <p> I found that for these values, convex_hull work as expected: </p> <ul><li>(15.0,631.0) </li><li>( 8.0,628.0) </li><li>( 8.0,679.0) </li><li>(15.0,682.0) </li></ul><p> I found that for these values, convex_hull work does not work as expected: </p> <ul><li>(15.9835,631.923), </li><li>(8.24075,628.579), </li><li>(8.24075,679.58 ), </li><li>(15.9835,682.926) </li></ul><p> Below is the main portion of the code, including comments and assert statements. </p> <p> I am using: </p> <ul><li>OS: Lubuntu (with all updates) and Windows 7 (with all updates) </li><li>GCC: 4.8.0 </li><li>Boost 1.55.0 </li><li>Qt Creator 2.8.1 with Qt 5.1. </li></ul><p> Full code can be viewed at <a class="missing wiki">GitHub</a> -&gt; project <a class="missing wiki">ProjectRichelBilderbeek</a> -&gt; folder Test -&gt; folder CppBoostGeometryExample7 -&gt; code there. </p> <pre class="wiki">#include &lt;cassert&gt; #include &lt;iostream&gt; #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Weffc++" #pragma GCC diagnostic ignored "-Wunused-local-typedefs" #pragma GCC diagnostic ignored "-Wunused-variable" #include &lt;boost/geometry.hpp&gt; #include &lt;boost/geometry/geometries/point_xy.hpp&gt; #pragma GCC diagnostic pop //Goal: determine if a polygon, derived from points, is convex //Method: if the convex_hull equals that points, it is convex // //Bug: convex_hull does make a convex polygon look concave for certain values int main() { using namespace boost::geometry; typedef model::d2::point_xy&lt;double&gt; Point; typedef model::polygon&lt;Point&gt; Polygon; //Example A: works as expected { /* Polygon used: - | - 2---3 | | - 1---0 | +--|---|---| (point values are those simplified from example B) */ const std::vector&lt;Point&gt; points { {15.0,631.0}, { 8.0,628.0}, { 8.0,679.0}, {15.0,682.0} }; Polygon polygon; append(polygon, points); assert(boost::geometry::num_points(polygon) == 4); boost::geometry::correct(polygon); assert(boost::geometry::num_points(polygon) == 5 &amp;&amp; "OK: boost::geometry::correct adds a point"); Polygon hull; boost::geometry::convex_hull(polygon, hull); assert(boost::geometry::num_points(hull) == 5 &amp;&amp; "OK: the hull of a convex polygon has the same number of points as that polygon"); assert(boost::geometry::equals(polygon,hull)); } //Example B: does not work as expected { /* Polygon used: - | - 2---3 | | - 1---0 | +--|---|---| */ const std::vector&lt;Point&gt; points { {15.9835,631.923}, {8.24075,628.579}, {8.24075,679.58 }, {15.9835,682.926} }; Polygon polygon; append(polygon, points); assert(boost::geometry::num_points(polygon) == 4); boost::geometry::correct(polygon); assert(boost::geometry::num_points(polygon) == 5 &amp;&amp; "OK: boost::geometry::correct adds a point"); Polygon hull; boost::geometry::convex_hull(polygon, hull); assert(boost::geometry::num_points(hull) == 6 &amp;&amp; "Should not add an extra point, as the original polygon was convex"); assert(!boost::geometry::equals(polygon,hull) &amp;&amp; "Should be equal, but does not"); } } </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/9873 Trac 1.4.3 viboes Wed, 23 Apr 2014 11:02:26 GMT component changed; owner set https://svn.boost.org/trac10/ticket/9873#comment:1 https://svn.boost.org/trac10/ticket/9873#comment:1 <ul> <li><strong>owner</strong> set to <span class="trac-author">Barend Gehrels</span> </li> <li><strong>component</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">geometry</span> </li> </ul> Ticket Jan-Henrik Kluth <j.kluth@…> Wed, 24 Aug 2016 12:32:31 GMT <link>https://svn.boost.org/trac10/ticket/9873#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/9873#comment:2</guid> <description> <p> I have a similar problem, so I add my case to this ticket: </p> <p> I projected a large 3D model (~200000 points) into a plane and wanted to compute a convex hull of those 2D points. Unfortunately boost::geometry::convex_hull sometimes returns a non-convex polygon. </p> <p> I dumped one example output to file and used those numbers for a second run of boost::geometry::convex_hull. The result stays the same. You can find this in the attached file, as well as a screenshot of the resulting wrong polygon. </p> <p> I am using Windows 7 with Visual Studio 2012 compiler and Boost 1.61. </p> </description> <category>Ticket</category> </item> <item> <author>Jan-Henrik Kluth <j.kluth@…></author> <pubDate>Wed, 24 Aug 2016 12:33:48 GMT</pubDate> <title>attachment set https://svn.boost.org/trac10/ticket/9873 https://svn.boost.org/trac10/ticket/9873 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">convex-hull-result.png</span> </li> </ul> <p> Image of convex hull result </p> Ticket Jan-Henrik Kluth <j.kluth@…> Wed, 24 Aug 2016 12:34:22 GMT attachment set https://svn.boost.org/trac10/ticket/9873 https://svn.boost.org/trac10/ticket/9873 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">example boost fail.cpp</span> </li> </ul> <p> Example of points that lead to false convex hull </p> Ticket