6
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\begingroup$ 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.) $\endgroup$ – murray Jul 28 '14 at 14:01
  • 4
    $\begingroup$ M can represent and operate on interval sets: List @@ IntervalIntersection[Interval @@ intervalsA, Interval @@ intervalsB] --> {{1.5, 2}, {3, 3.5}, {5, 6}} $\endgroup$ – alancalvitti Jul 28 '14 at 14:12
  • $\begingroup$ Thanks a lot ! It works really well with the required speed ! :) I feel kind of stupid because I didn't use those intervals properly. $\endgroup$ – Mammouth Jul 28 '14 at 14:17
  • $\begingroup$ @alancalvitti Excellent - Why don't you put this as an answer? $\endgroup$ – eldo Jul 28 '14 at 14:19
  • $\begingroup$ Related: my own (old) question from Stack Overflow: (5784046) $\endgroup$ – Mr.Wizard Jul 28 '14 at 14:29
3
$\begingroup$ 
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}]

Improve this answer
$\endgroup$
2
  • $\begingroup$ A bit classier, but slightly less efficient than List @@ IntervalIntersection[Interval @@ intervalsA, Interval @@ intervalsB]. $\endgroup$ – Mammouth Jul 28 '14 at 14:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Mr.Wizard Jul 28 '14 at 15:17
0
$\begingroup$

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}]}*)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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