Intersection of two sets

[schillic]

Add a lazy binary operator type Intersection (and maybe an n-ary variant) representing the intersection of two sets S1 and S2.
Also have a convenience alias ∩(S1, S2), for which Julia's built-in alias is intersect.

Related but simpler: #67

[schillic]

1. What do we do if the intersection is not representable? Overapproximate? Underapproximate? Support both with a parameter?
2. Do we want to have a lazy type Intersection? It would be almost insonsistent to not have this, but the support vectors might not be as easy as with the other types.

[mforets]

yes, i think ∩ should be lazy. we can provide an option to compute it exactly, as it is the case for the minkowski sum of 2d clouds of points, for example.

[schillic]

Okay, I edited the first post.

[schillic]

Is it correct that, assuming that the intersection is nonempty, the support vector is just the minimum/maximum of both operands' support vectors?

function σ(d::AbstractVector{N}, I::Intersection{N, S1, S2})::AbstractVector{N} where {N<:Real}
    v = copy(d)
    sv1 = σ(d, I.X1)
    sv2 = σ(d, I.X2)
    for i in 1:length(d)
        v[i] = d[i] < 0 ? max(sv1[i], sv2[i]) : min(sv1[i], sv2[i])
    end
end

I am not sure about the case where a vector entry is 0.

And of course we need to detect that the intersection is nonempty. Can we just ask σ(-d, I) and see if the results contradict?
EDIT: No, take two nonintersecting boxes with the same x coordinates. Asking for d = [1, 0] does not detect emptiness of the intersection.

[mforets]

cc: @viryfrederic

[schillic]

Okay, this is Section 8.1, first paragraph in Le Guernic's thesis. I just have to study it.

EDIT: Actually, this section is only for detecting emptiness, which would rather fit for #67.
What we want here is Section 8.3, and it sounds complicated.

And forget my algorithm above. I think it works for hyperrectangles, but definitely not for arbitrary sets (take two circles for instance).

[schillic]

The implementation we have now just crashes when asked for the support vector. We should think about what we can do here, maybe solve a complicated optimization problem or resort to subcases.

[mforets]

we could also write an intersect function that works by dispatching on some special pairs of sets for which we can implement it.

[schillic]

@mforets found this paper about the general case.

[schillic]

We should pull out the LinearConstraints.intersection function here, too. See #57.

[mforets]

still this is open:

the implementation (of the intersection) we have now just crashes when asked for the support vector.

one approach is to compute the concrete intersection (done in #173), and ask for the support vector. but i wouldn't do it this way since this wouldn't be a lazy operation at all. seems to me that it will be preferable to apply Lemma 4 from Frehse and Ray.

[schillic]

Well, there are different levels of laziness.

1. Intersection waits with computing the intersection until you ask for it. This is what we could have with Polyhedra interface #173.
2. All our other lazy types never compute the actual set but only provide the support vector of a given direction by passing the query to their child sets. This is what you meant, and I agree that this is better (assuming it is actually cheaper).

[mforets]

Lots of interesting material: https://www.geometrictools.com/Documentation/Documentation.html

[schillic]

Another interesting page: http://www.realtimerendering.com/intersections.html

[schillic]

Closing this one and continuing the meta collection in #1391.