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, 2014 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, 2014 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, 2014 at 14:17
  • $\begingroup$ @alancalvitti Excellent - Why don't you put this as an answer? $\endgroup$
    – eldo
    Jul 28, 2014 at 14:19
  • $\begingroup$ Related: my own (old) question from Stack Overflow: (5784046) $\endgroup$
    – Mr.Wizard
    Jul 28, 2014 at 14:29

2 Answers 2

Reset to default
4
$\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, 2014 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, 2014 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.