Opened 4 years ago

Last modified 2 years ago

#9873 new Bugs

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

Reported by: richel@… Owned by: Barend Gehrels
Milestone: To Be Determined Component: geometry
Version: Boost 1.55.0 Severity: Problem
Keywords: Boost.Geometry, boost::geometry::convex_hull, convex_hull Cc:

Description

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

Attachments (2)

convex-hull-result.png (49.4 KB) - added by Jan-Henrik Kluth <j.kluth@…> 2 years ago.
Image of convex hull result
example boost fail.cpp (10.6 KB) - added by Jan-Henrik Kluth <j.kluth@…> 2 years ago.
Example of points that lead to false convex hull

Download all attachments as: .zip

Change History (4)

comment:1 Changed 4 years ago by viboes

Component: Nonegeometry
Owner: set to Barend Gehrels

comment:2 Changed 2 years ago by 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.

Changed 2 years ago by Jan-Henrik Kluth <j.kluth@…>

Attachment: convex-hull-result.png added

Image of convex hull result

Changed 2 years ago by Jan-Henrik Kluth <j.kluth@…>

Attachment: example boost fail.cpp added

Example of points that lead to false convex hull

Note: See TracTickets for help on using tickets.