[Boost-bugs] [Boost C++ Libraries] #9873: Boost.Geometry: boost::geometry::convex_hull makes a convex polygon look concave for certain values

Subject: [Boost-bugs] [Boost C++ Libraries] #9873: Boost.Geometry: boost::geometry::convex_hull makes a convex polygon look concave for certain values
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-04-11 12:12:13

#9873: Boost.Geometry: boost::geometry::convex_hull makes a convex polygon look
concave for certain values
-------------------------+-------------------------------------------------
 Reporter:  richel@…     |       Type:  Bugs
   Status:  new          |  Milestone:  To Be Determined
Component:  None         |    Version:  Boost 1.55.0
 Severity:  Problem      |   Keywords:
                         |  Boost.Geometry,boost::geometry::convex_hull,convex_hull
-------------------------+-------------------------------------------------
 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.

 However, convex_hull does make a convex polygon look concave for certain
 values.

 I found that for these values, convex_hull work as expected:
  * (15.0,631.0)
  * ( 8.0,628.0)
  * ( 8.0,679.0)
  * (15.0,682.0)
 I found that for these values, convex_hull work does not work as expected:
  * (15.9835,631.923),
  * (8.24075,628.579),
  * (8.24075,679.58 ),
  * (15.9835,682.926)

 Below is the main portion of the code, including comments and assert
 statements.

 I am using:
  * OS: Lubuntu (with all updates) and Windows 7 (with all updates)
  * GCC: 4.8.0
  * Boost 1.55.0
  * Qt Creator 2.8.1 with Qt 5.1.

 Full code can be viewed at GitHub -> project ProjectRichelBilderbeek ->
 folder Test -> folder CppBoostGeometryExample7 -> code there.

 {{{
 #include <cassert>
 #include <iostream>

 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Weffc++"
 #pragma GCC diagnostic ignored "-Wunused-local-typedefs"
 #pragma GCC diagnostic ignored "-Wunused-variable"
 #include <boost/geometry.hpp>
 #include <boost/geometry/geometries/point_xy.hpp>
 #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<double> Point;
   typedef model::polygon<Point> Polygon;

   //Example A: works as expected
   {
     /* Polygon used:

       -
       |
       -  2---3
       |  |
       -  1---0
       |
       +--|---|---|

     (point values are those simplified from example B)

     */
     const std::vector<Point> 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
       && "OK: boost::geometry::correct adds a point");

     Polygon hull;
     boost::geometry::convex_hull(polygon, hull);

     assert(boost::geometry::num_points(hull) == 5
       && "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<Point> 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
       && "OK: boost::geometry::correct adds a point");

     Polygon hull;
     boost::geometry::convex_hull(polygon, hull);

     assert(boost::geometry::num_points(hull) == 6
       && "Should not add an extra point, as the original polygon was
 convex");

     assert(!boost::geometry::equals(polygon,hull)
       && "Should be equal, but does not");
   }
 }
 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9873>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.