Opened 5 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: | 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)
Change History (4)
comment:1 Changed 5 years ago by
Component: | None → geometry |
---|---|
Owner: | set to Barend Gehrels |
comment:2 Changed 2 years ago by
Changed 2 years ago by
Attachment: | example boost fail.cpp added |
---|
Example of points that lead to false convex hull
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.