Re: checking for overlap

*To*: mathgroup at smc.vnet.net*Subject*: [mg20098] Re: [mg20065] checking for overlap*From*: "David Park" <djmp at earthlink.net>*Date*: Thu, 30 Sep 1999 02:43:10 -0400*Sender*: owner-wri-mathgroup at wolfram.com

>I am looking for an elegant way of checking for overlap. > >Suppose I have a set of time intervals given by >ints = {{t1,t2},{t3,t4},{t5,t6}. ...} and another set of times >tvals = {u1,u2,u3, ...}. > What is a fast, elegant way of checking which of the tvals is within any of >the ints time intervals? > >Thanks, >Dennis > > Dennis, Perhaps I should know better than to touch these kinds of problems, but here is my try. You will probably get some better methods from the real mathematicians in MathGroup. Here is a test case. ints = Table[{2n, 2n + 1}, {n, 0, 4}]; Create ints2 by applying Interval to ints. ints2 = Interval @@ ints Interval[{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}] Here is a random set of tvals. tvals = Table[Random[Real, {0, 10}], {10}] {7.28844, 7.97387, 1.4635, 8.27075, 4.35604, 0.938894, 6.27754, 3.95451, 4.18765, 3.76676} It is not clear whether you just want True or False answers for each value, want a list of the positions, or want to select out the values. This selects the values that lie in the intervals. Select[tvals, IntervalMemberQ[ints2, #] &] {8.27075, 4.35604, 0.938894, 6.27754, 4.18765} Here is the timing for a longer case on a 166 Mh Pentium. 100 values with 50 intervals. ints2 = Interval @@ Table[{2n, 2n + 1}, {n, 0, 49}]; tvals = Table[Random[Real, {0, 100}], {1000}]; Select[tvals, IntervalMemberQ[ints2, #] &]; // Timing {1.32 Second, Null} The timing appears to be linear with the number of tvals and the number of intervals. David Park djmp at earthlink.net http://home.earthlink.net/~djmp/