Modify

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain Barend Gehrels.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.