Boost.Geometry: boost::geometry::convex_hull makes a convex polygon look concave for certain values

[richel@…]

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");
  }
}

[Jan-Henrik Kluth <j.kluth@…>]

I have a similar problem, so I add my case to this ticket:

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.

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.

I am using Windows 7 with Visual Studio 2012 compiler and Boost 1.61.

[Jan-Henrik Kluth <j.kluth@…>]

Image of convex hull result

[Jan-Henrik Kluth <j.kluth@…>]

Example of points that lead to false convex hull