Opened 7 years ago

Closed 4 years ago

#6443 closed Bugs (fixed)

Convex hull does not cover polygon with zero area

Reported by: cooperch@… Owned by: Barend Gehrels
Milestone: To Be Determined Component: geometry
Version: Boost 1.47.0 Severity: Showstopper
Keywords: Cc:

Description

A polygon with points (0,0) and (0,2) should have an area of 0 and a perimeter of 4, I think? (If I'm wrong on the specification please let me know).

The attached code says otherwise - it gives a convex hull with zero perimeter.

Attachments (1)

boost_geom_test_no_multipoint.cpp (1.3 KB) - added by cooperch@… 7 years ago.
c++ code to reproduce problem

Download all attachments as: .zip

Change History (6)

Changed 7 years ago by cooperch@…

c++ code to reproduce problem

comment:1 Changed 6 years ago by viboes

Component: Nonegeometry
Owner: set to Barend Gehrels

Please set the component in the future if you want it to be analyzed.

comment:2 Changed 6 years ago by Barend Gehrels

Thanks for the report - because the component was not set, it did not reach my inbox. However, will now have a look at the problem soon.

comment:3 in reply to:  2 Changed 6 years ago by Sarat Chandra Addepalli <s.addepalli@…>

Hi. This seems to me to be more of a question on convention followed, than a bug. If a point set S has only two elements (p1 and p2, say) Should the Convex_hull(S) have two edges or one? One edge would mean that the Convex_hull is not a 'closed' polygon. Two edges, on the other hand, would mean that the perimeter calculation is correct.

On a side note, I had to include the #include<boost/geometry/geometries/point_xy.hpp> line to avoid compilation errors in the attached file.

comment:4 Changed 5 years ago by Rong Xiao <akelux@…>

I think this IS a bug according to the mathematical definition of a convex hull of a set of points, c.f. http://en.wikipedia.org/wiki/Convex_hull. The convex hull one point is the point itself; the convex hull of two distinct points are the line segment between the two points.

comment:5 Changed 4 years ago by awulkiew

Resolution: fixed
Status: newclosed

This was fixed in 1.57 as a side effect of fixing https://svn.boost.org/trac/boost/ticket/10562. Since 1.57 a Polygon containing the minimal correct number of Points is returned (3 for open and 4 for closed Polygons) so "correct" area and perimeter can be calculated. Note that according to OGC specification Polygons with area = 0 are invalid.

Note: See TracTickets for help on using tickets.