Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: checking for overlap

• To: mathgroup at smc.vnet.net
• Subject: [mg20093] Re: [mg20065] checking for overlap
• From: "Wolf, Hartmut" <hwolf at debis.com>
• Date: Thu, 30 Sep 1999 02:43:08 -0400
• Organization: debis Systemhaus
• References: <199909290733.DAA11845@smc.vnet.net.>
• Sender: owner-wri-mathgroup at wolfram.com

DennisW555 schrieb:
> 
> 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?
> 
Hello Dennis,

for check of containment of numbers in intervals there exist the
Mathematica functions Interval and IntervalMemberQ, e.g.:

Let's define some test data (in your format):

ints = Delete[Partition[Sort[Table[Random[Real, 100.], {200}]], 2], 
    Union[Table[{Random[Integer, {1, 100}]}, {60}]]]

Convert it to "Intervals":

ints = Interval /@ ints

Length[ints]

52

And some time values (sorted for convenience):

tvals = Sort[Table[Random[Real, 100.], {100}]]


We can check for any combination of intervalls and time values:

With[{membs = Outer[IntervalMemberQ, ints, tvals]}, 
    Position[membs, True]] // Timing

{0.4 Second, {{3, 1}, {4, 2}, {5, 3}, {7, 6}, {7, 7}, {9, 8}, {10, 9},
{12, 
      16}, {12, 17}, {12, 18}, {14, 20}, {15, 21}, {18, 24}, {18, 25},
{20, 
      30}, {23, 37}, {23, 38}, {23, 39}, {23, 40}, {24, 41}, {24, 42},
{24, 
      43}, {24, 44}, {24, 45}, {28, 47}, {28, 48}, {30, 52}, {30, 53},
{36, 
      62}, {39, 85}, {39, 86}}}

This are the remains of 52 x 100 tests. The first components denote the
index to ints, the second the index to tvals. So time values 6 and 7
both hit the 7th interval.

This method works always and is good if the intervals are largely
overlapping. In case the time intervals are disjoint (and you have your
intervals and time values ordered) you can do much better, e.g. like:

Module[{contained = {}, t = 1}, 
    With[{tmax = Length[tvals]}, 
      Do[While[t <= tmax && tvals[[t]] < ints[[i]][[1,1]], t++]; 
         While[t <= tmax && IntervalMemberQ[ints[[i]], tvals[[t]] ], 
            AppendTo[contained, {i, t++}] ],
      {i, 1, Length[ints]}]
      ]; contained] // Timing

{0.04 Second, {{3, 1}, {4, 2}, {5, 3}, {7, 6}, {7, 7}, {9, 8}, {10, 9},
{12, 
      16}, {12, 17}, {12, 18}, {14, 20}, {15, 21}, {18, 24}, {18, 25},
{20, 
      30}, {23, 37}, {23, 38}, {23, 39}, {23, 40}, {24, 41}, {24, 42},
{24, 
      43}, {24, 44}, {24, 45}, {28, 47}, {28, 48}, {30, 52}, {30, 53},
{36, 
      62}, {39, 85}, {39, 86}}}

(You can further improve, if you want and need, e.g. not use Append, but
I left it here for clarity.)

kind regards, hw

• References:
  • checking for overlap
    • From: dennisw555@aol.com (DennisW555)