Fix HPolygon vs HPolygon intersection in floating point

[mforets]

Let

p = VPolygon([[0.161915, 0.780202], 
              [0.264545, 0.293386],  
              [0.54406, 0.0902449],  
              [0.801169, 0.00964868],
              [0.954425, 0.155487],
              [0.8336, 0.636783],
              [0.656131, 0.737161]])

q = VPolygon([[0.0800543, 0.318534],
              [0.122886, 0.0980148],
              [0.655319, 0.143195],
              [0.627578, 0.699661],
              [0.245012, 0.953383]])

plot([p, q], alpha=0.1)

Compute the intersection with CDD:

using Polyhedra

pv = convert(VPolytope, p)
qv = convert(VPolytope, q)
plot!(intersection(pv, qv), alpha=0.6, color="orange")

Compute the intersection using intersection(::HPolygon, ::HPolygon):

ph = convert(HPolygon, p)
qh = convert(HPolygon, q)
plot!(intersection(ph, qh), alpha=0.3, color="black")

[mforets]

FWIW note that

function intersection2(P1, P2)
    P = HPolygon()
    addconstraint!.(P, constraints_list(P1))
    addconstraint!.(P, constraints_list(P2))
    return P
end

plot(intersection2(tohrep(p), tohrep(q)), alpha=0.3, color="black")

[schillic]

😟

[schillic]

This could be a problem with redundant constraints, see #381.

[mforets]

Just checked this again, and it has been fixed by now 🎉

ph = convert(HPolygon, p)
qh = convert(HPolygon, q)
plot!(intersection(ph, qh))

---

Regarding computation time, 

• intersection(::HPolygon, ::HPolygon) ... 140us
• intersection(::HPolytope, ::HPolytope) ... 284us
• intersection(::HPolytope, ::HPolytope, backend=CDDLib.Library()) ... 645us

[mforets]

On the other hand intersection of original VPolygon is slow:

@btime intersection($p, $q) # as VPolygon
2.594 ms (32355 allocations: 1.84 MiB)

(this passes through Polyhedra through this function, i'm thinking if we should rather use a 2D implementation, or at least convert to HPolygon and then use the intersection of HPolygon should be cheaper.