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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.