Best way to calculate set intersection/set difference for a set represented as vector of interval vectors

[eparrott]

Hi,

I have a custom solver implemented which returns a series of sets each represented as a std::vector containing the inside boxes for the given set. I was wondering what the most efficient way to take the set intersection and set difference between multiple sets would be, given this starting format.

Thanks!

[gchabert]

You should have a look to Ibex sets, which already implement those set operations in a clever way

[eparrott]

Gilles,

Thanks! I've been looking at using sets, and they appear to generally do what I'd like, but I'm unsure of how to actually convert the std::vector into a set object. Also, I see the set intersection operation but I don't see an explicit way to do a set difference.

Cheers

[gchabert]

Oh yes, I thought I had implemented the set difference but apparently, no. Sorry, it was 7 years ago :) Building a Set from a vector of boxes is easy: you start from the empty Set and then use the union operator |= iteratively with each box of the vector. To do a set difference, you can build the negation of a set using the previous trick (to get the negation of a box, you can use the diff operator) and then an intersection . This is my only suggestion with Ibex... Of course, you may also consider implementing you own algorithms

[eparrott]

Thank you, I'll give that a try!

[eparrott]

Hi Gilles,

I tried using your approach to iteratively create a set from a vector of boxes starting from the empty set and then iteratively applying the union operation, and I've run into the issue where I'm unable to get all the way through the list of boxes before getting a "segmentation fault (core dumped)" error, which I suspect has to do with the size/dimension of the boxes in the list. Do you have any alternate suggestions as to how to proceed?