Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Here is my problem: I have two very large lists of intervals (stored as many couples in the form {{"start point", "end point"}, ..., {"start point", "end point"}), and I want the result of the intersection of those lists.

Here is an example :

intervalsA = {{1, 2}, {3, 4}, {5, 7}, {8, 8.5}};
intervalsB = {{1.5, 3.5}, {4.1, 6}, {9, 10}};

The expected result is: overlap = {{1.5, 2}, {3, 3.5}, {5, 6}};

I tried using Interval, IntervalUnion and IntervalIntersection, but nothing worked. The only working method that I found uses Piecewise functions where each interval is set as 1. By multiplying the two piecewise functions, I have something similar to the intersection, but the solution is very inefficient.

I hope I am clear and precise enough.

share|improve this question
    
Do you want the intersections of each of the intervals in the first list with each of the intervals in the second list? (Presumably you do not want intersections of corresponding entries in each of the two lists, since in the example your lists have different lengths.) –  murray Jul 28 at 14:01
4  
M can represent and operate on interval sets: List @@ IntervalIntersection[Interval @@ intervalsA, Interval @@ intervalsB] --> {{1.5, 2}, {3, 3.5}, {5, 6}} –  alancalvitti Jul 28 at 14:12
    
Thanks a lot ! It works really well with the required speed ! :) I feel kind of stupid because I didn't use those intervals properly. –  Mammouth Jul 28 at 14:17
    
@alancalvitti Excellent - Why don't you put this as an answer? –  eldo Jul 28 at 14:19
    
Related: my own (old) question from Stack Overflow: (5784046) –  Mr.Wizard Jul 28 at 14:29

2 Answers 2

up vote 3 down vote accepted
intervalsA = {{1, 2}, {3, 4}, {5, 7}, {8, 8.5}};
intervalsB = {{1.5, 3.5}, {4.1, 6}, {9, 10}};
IntervalIntersection @@ Interval @@@ {intervalsA, intervalsB}

Interval[{1.5, 2}, {3, 3.5}, {5, 6}]

share|improve this answer
    
A bit classier, but slightly less efficient than List @@ IntervalIntersection[Interval @@ intervalsA, Interval @@ intervalsB]. –  Mammouth Jul 28 at 14:35
    
@Mammouth I don't see any difference in performance, and I think there shouldn't be as they are essentially equivalent. By the way the parentheses are extraneous here. –  Mr.Wizard Jul 28 at 15:17

or more general:

youFunction[intervals__] := Composition[
    DeleteCases[#, Interval[]] &,
    DeleteDuplicates,
    (IntervalIntersection @@ # &) /@ # &,
    Subsets[#, {2}] &,
    Join[##] &
    ][intervals];

intervalsA = Interval /@ {{1, 2}, {3, 4}, {5, 7}, {8, 8.5}};
intervalsB = Interval /@ {{1.5, 3.5}, {4.1, 6}, {9, 10}};
youFunction[intervalsA, intervalsB]
(*{Interval[{1.5, 2}], Interval[{3, 3.5}], Interval[{5, 6}]}*)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.