Convex hull algorithm in 2D sensitive to numeric precision

[schillic]

The following happens because of the -0.0. Nevertheless, the result is unexpected.

julia> v = [[-0.0, 2], [2.0, 0], [1.0, 0], [0.0, 1], [0.0, 1.5]]
5-element Vector{Vector{Float64}}:
 [-0.0, 2.0]
 [2.0, 0.0]
 [1.0, 0.0]
 [0.0, 1.0]
 [0.0, 1.5]

julia> c = convex_hull(v)
4-element Vector{Vector{Float64}}:
 [-0.0, 2.0]
 [0.0, 1.5]
 [1.0, 0.0]
 [2.0, 0.0]

julia> plot([Singleton(x) for x in v], c=:blue, alpha=1)

julia> plot!([Singleton(x) for x in c], c=:red, alpha=1)

julia> plot!(VPolygon(v))

[schillic]

The problem is that sort! gives the wrong order due to the -0.0. It uses the order relation <, which ultimately calls the following Base function:

function cmp(A::AbstractVector, B::AbstractVector)
    for (a, b) in zip(A, B)
        if !isequal(a, b)
            return isless(a, b) ? -1 : 1
        end
    end
    return cmp(length(A), length(B))
end

Here, isequal distinguishes 0.0 and -0.0 and thus sort! outputs [-0.0, 2] before [2.0, 0]. The remaining algorithm checks right turns, which are not precise enough to see the difference, and thus gives the wrong result.

I see two possible solutions:

1. Sanitize -0.0 values to 0.0.
2. Change the sort! order relation.