id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
9873,Boost.Geometry: boost::geometry::convex_hull makes a convex polygon look concave for certain values,richel@…,Barend Gehrels,"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"");
  }
}
}}}",Bugs,new,To Be Determined,geometry,Boost 1.55.0,Problem,,"Boost.Geometry,boost::geometry::convex_hull,convex_hull",