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)
- checking for overlap