search

JuliaPolyhedra / Polyhedra.jl

Polyhedral Computation Interface
Other
172 stars 27 forks source link

Incorrect planar hull evaluation #271

Closed harshangrjn closed 2 years ago

harshangrjn commented 3 years ago

@blegat 

v = convexhull([0.0, 0.0], [1, 0], [0.5, 0.0], [-0.5, 0.0], [0.5, 0.5])
Polyhedra.planar_hull(v)

Output of the above evaluation is the extreme points (EPs) of the convex hull, which doesn't look right: 

 [0.0, 0.0]
 [0.5, 0.5]
 [1.0, 0.0]

But, if I simply re-order the original list of vertices to : 

v = convexhull([1, 0], [0.0, 0.0], [0.5, 0.0], [-0.5, 0.0], [0.5, 0.5])

I seem to get the correct EPs which is: 

 [1.0, 0.0]
 [-0.5, 0.0]
 [0.5, 0.5]

This is a bug, unless I am missing something in the input format.

harshangrjn commented 3 years ago

In Polyhedra.jl, is there an alternative option to evaluate the hull of a set of points in a plane?

blegat commented 2 years ago

Indeed, it looks incorrect. Here is a list of the alternatives: https://github.com/JuliaPolyhedra/Polyhedra.jl/blob/master/examples/Convex%20hull%20of%20a%20set%20of%20points.jl

harshangrjn commented 2 years ago

The other option using vrep seems to lead to the same issue. Yet to try the CDDLib option.

blegat commented 2 years ago

Yes, convexhull and vrep won't change the behavior. CDDLib or QHull should work though.