interval intersection - comp.programming

On 26 Oct 2005 22:17:22 -0700, bob@coolgroups.com wrote: >what is the fastest way to find the intersection of two 1-dimensional >intervals? > >here's an example: > >interval 1: 0 to 50 >interval 2: 25 to 80 > >answer: 25 to 50 The obvious method to find the intersection c of intervals a and b is the formula c.start = max(a.start,b.start) c.end = min(a.end,b.end) with the caveat that there is no intersection if c.end <= c.start. What else would you do? Richard Harter, cri@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com I started out in life with nothing. I still have most of it left.

In article <1130390241.982643.265310@f14g2000cwb.googlegroups.com>, bob@coolgroups.com says... > what is the fastest way to find the intersection of two 1-dimensional > intervals? Let interval 1 be given by [a,b] and interval 2 by [c,d] (where a <= b, c <= d) then the intersection is the interval [max(a,c),min(b,d)]. How you best implement the min() and max() operations is highly architecture-dependent; some architectures have native min() and max() instructions, on others you would have to implement them as if tests (or similar). -- Christer Ericson http://realtimecollisiondetection.net/

Richard Harter wrote: > c.start = max(a.start,b.start) > c.end = min(a.end,b.end) > What else would you do? well, for example, if a.end is < b.start, there is no point in doing 2nd "if", right? but this 1st "if" itself doesn't add anything to intersection, so if it fails, and there is intersection, we still have 2 "if"-s to do, which makes it 3 "if"-s in total... so the point is that overall speed could be improved, if you know that a number of not-intersecting intervals will be substantially more than a number of intersecting ones.

On 27 Oct 2005 06:30:20 -0700, makc.the.great@gmail.com wrote: > >Richard Harter wrote: >> c.start = max(a.start,b.start) >> c.end = min(a.end,b.end) >> What else would you do? > >well, for example, if a.end is < b.start, there is no point in doing >2nd "if", right? but this 1st "if" itself doesn't add anything to >intersection, so if it fails, and there is intersection, we still have >2 "if"-s to do, which makes it 3 "if"-s in total... so the point is >that overall speed could be improved, if you know that a number of >not-intersecting intervals will be substantially more than a number of >intersecting ones. > Point taken. There are alternatives that, under the right conditions, might be faster. Your analysis is incomplete. To test for non-intersection you also have to test for a.start > b.end (interval b can lay on either side of interval a) so, given equal probabilities of order of none-intersecting intervals, the average number of if's required for the non-intersection test is 1.5 for non-intersecting intervals and 2 for intersecting intervals. In the standard method we need a third test, c.start < c.end, to test for intersection. Thus the number of if's required are: Method Non-intersecting Intersecting check 1.5 4 no check 3 3 So it would appear that when the percentage of non-intersecting intervals is greater than 40% checking would be a win, and when it is less than 40% it would be a loss. However that is not the whole matter. First, determining max and min are more costly than simple if tests. Second, in modern machines many of the instructions can be done in parallel. In my experience, these sort of special case checks don't gain anything unless (a) the rate of occurrence of the special cases is significant, and (b) the cost of the remainder of the sequence is very large compared to the cost of the test. YMOV. Richard Harter, cri@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com I started out in life with nothing. I still have most of it left.

On 27 Oct 2005 10:00:32 -0700, makc.the.great@gmail.com wrote: >your numbers are misterious. Think about for a while. HTH. HAND. Richard Harter, cri@tiac.net http://home.tiac.net/~cri, http://www.varinoma.com I started out in life with nothing. I still have most of it left.

bob@coolgroups.com wrote: > what is the fastest way to find the intersection of two 1-dimensional > intervals? > > here's an example: > > interval 1: 0 to 50 > interval 2: 25 to 80 > > answer: 25 to 50 > Here's an implementation in Oberon: (* Gets intersection of specified intervals. Calculates the intersection [lower, upper] of the intervals [lower1, upper1] and [lower2, upper2]. The flag empty is set to TRUE if the intersection is empty. *) PROCEDURE GetIntersection(lower1, upper1, lower2, upper2: LONGINT; VAR lower, upper: LONGINT; VAR empty: BOOLEAN); BEGIN IF (upper1 < lower2) OR (upper2 < lower1) THEN empty := TRUE ELSE IF lower1 > lower2 THEN lower := lower1 ELSE lower := lower2 END; IF upper1 < upper2 THEN upper := upper1 ELSE upper := upper2 END; empty := FALSE; END END GetIntersection; August

August Karlstrom wrote: > bob@coolgroups.com wrote: >> what is the fastest way to find the intersection of two 1-dimensional >> intervals? >> >> here's an example: >> >> interval 1: 0 to 50 >> interval 2: 25 to 80 >> >> answer: 25 to 50 >> > > Here's an implementation in Oberon: > > (* Gets intersection of specified intervals. Calculates the > intersection [lower, upper] of the intervals [lower1, upper1] and > [lower2, upper2]. The flag empty is set to TRUE if the intersection > is empty. *) > > PROCEDURE GetIntersection(lower1, upper1, lower2, upper2: LONGINT; > VAR lower, upper: LONGINT; > VAR empty: BOOLEAN); > BEGIN > IF (upper1 < lower2) OR (upper2 < lower1) THEN empty := TRUE > ELSE > IF lower1 > lower2 THEN lower := lower1 > ELSE lower := lower2 > END; > IF upper1 < upper2 THEN upper := upper1 > ELSE upper := upper2 > END; > empty := FALSE; > END > END GetIntersection; Isn't that a little heavweight? def intersection( x1, y1, x2, y2) = (max( x1, x2 ), min( y1, y2 )) seems adequate to me. (max, min, and isEmpty are all one-liners, if they're not already to hand.) Also, your procedure doesn't assign to lower/upper if the result is empty, making it easy (when not checking `empty`) to produce garbage; also, since it doesn't deliver any useful result, it doesn't compose (suppose I want the intersection of three intervals); and it requires the invention of not only two integer variables for actual parameters, but also a arguably-redundant boolean variable. -- Chris "it's all paraphernalia" Dollin son of a gun, listen to the plants, breathless. shifting sands - life in the fast lane.

Chris Dollin wrote: > August Karlstrom wrote: > >> bob@coolgroups.com wrote: >>> what is the fastest way to find the intersection of two 1-dimensional >>> intervals? >>> >>> here's an example: >>> >>> interval 1: 0 to 50 >>> interval 2: 25 to 80 >>> >>> answer: 25 to 50 >>> >> >> Here's an implementation in Oberon: >> >> (* Gets intersection of specified intervals. Calculates the >> intersection [lower, upper] of the intervals [lower1, upper1] and >> [lower2, upper2]. The flag empty is set to TRUE if the intersection >> is empty. *) >> >> PROCEDURE GetIntersection(lower1, upper1, lower2, upper2: LONGINT; >> VAR lower, upper: LONGINT; >> VAR empty: BOOLEAN); >> BEGIN >> IF (upper1 < lower2) OR (upper2 < lower1) THEN empty := TRUE >> ELSE >> IF lower1 > lower2 THEN lower := lower1 >> ELSE lower := lower2 >> END; >> IF upper1 < upper2 THEN upper := upper1 >> ELSE upper := upper2 >> END; >> empty := FALSE; >> END >> END GetIntersection; > > Isn't that a little heavweight? > > def intersection( x1, y1, x2, y2) = (max( x1, x2 ), min( y1, y2 )) To clarify post-hoc: my bit isn't Oberon; it's just that the cited code seems to take a lot of characters to say not so much. (I'm sure there are more compact ways of writing the Oberon.) -- Chris "it's all paraphernalia" Dollin son of a gun, listen to the plants, breathless. shifting sands - life in the fast lane.

--Signature_Sat__29_Oct_2005_10_13_51_+0200_AYOYjRpzUG1vEnhP Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable bob@coolgroups.com (26 Oct 2005 22:17:22 -0700): > what is the fastest way to find the intersection of two 1-dimensional > intervals? > > here's an example: > > interval 1: 0 to 50 > interval 2: 25 to 80 > > answer: 25 to 50 Pseudo-code generating intersection [x, y] of [a, b] and [c, d]: x =3D max(a, c); y =3D min(b, d); if (y < x) return NO_INTERSECTION; This code assumes that b >=3D a and d >=3D c. Graphical explanation: a----------b c------------d x------y There is an intersection (y >=3D x). a-------b c--------d y--x There is no intersection (y < x). Regards. ----- Public key "Ertugrul Soeylemez <never@drwxr-xr-x.org>" (id: CE402012) Fingerprint: 0F12 0912 DFC8 2FC5 E2B8 A23E 6BAC 998E CE40 2012 HKP: hkp://subkeys.pgp.net/ LDAP: ldap://keyserver.pgp.com/ HTTP: http://www.keyserver.de/ --Signature_Sat__29_Oct_2005_10_13_51_+0200_AYOYjRpzUG1vEnhP Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFDYy9Ba6yZjs5AIBIRAs/rAJ9SROEaBZv1FjLLIOxaRyEbSF5sJQCgrmmM 5OGmSU02biFwVJfQKk17WmI= =LJDI -----END PGP SIGNATURE----- --Signature_Sat__29_Oct_2005_10_13_51_+0200_AYOYjRpzUG1vEnhP--

Chris Dollin wrote: > August Karlstrom wrote: > > >>bob@coolgroups.com wrote: >> >>>what is the fastest way to find the intersection of two 1-dimensional >>>intervals? >>> >>>here's an example: >>> >>>interval 1: 0 to 50 >>>interval 2: 25 to 80 >>> >>>answer: 25 to 50 >>> >> >>Here's an implementation in Oberon: >> >>(* Gets intersection of specified intervals. Calculates the >>intersection [lower, upper] of the intervals [lower1, upper1] and >>[lower2, upper2]. The flag empty is set to TRUE if the intersection >>is empty. *) >> >> PROCEDURE GetIntersection(lower1, upper1, lower2, upper2: LONGINT; >> VAR lower, upper: LONGINT; >> VAR empty: BOOLEAN); >> BEGIN >> IF (upper1 < lower2) OR (upper2 < lower1) THEN empty := TRUE >> ELSE >> IF lower1 > lower2 THEN lower := lower1 >> ELSE lower := lower2 >> END; >> IF upper1 < upper2 THEN upper := upper1 >> ELSE upper := upper2 >> END; >> empty := FALSE; >> END >> END GetIntersection; > > > Isn't that a little heavweight? > > def intersection( x1, y1, x2, y2) = (max( x1, x2 ), min( y1, y2 )) In a high-level functional language with lots of predefined functions, of course the definition will be shorter (but also slower). > Also, your procedure doesn't assign to lower/upper if the result is > empty, making it easy (when not checking `empty`) to produce garbage; > also, since it doesn't deliver any useful result, it doesn't compose > (suppose I want the intersection of three intervals); and it requires > the invention of not only two integer variables for actual parameters, > but also a arguably-redundant boolean variable. OK, you certainly have a point here. The following version is probably better: (* Gets intersection of specified intervals. Calculates the intersection [a, b] of the intervals [a1, b1] and [a2, b2]. If the intersection is empty then a > b. *) PROCEDURE GetIntersection(a1, b1, a2, b2: LONGINT; VAR a, b: LONGINT); BEGIN IF a1 > a2 THEN a := a1 ELSE a := a2 END; IF b1 < b2 THEN b := b1 ELSE b := b2 END END GetIntersection; I admit that names like upper and lower may be a bit too verbose, but I don't think x and y are good names since it makes me think of two-dimensional coordinates. I prefer a and b. Note also that Oberon doesn't have built in functions for the minimum/maximum value of integers. But of course we can define them in some utility module M. In that case the function is as short as PROCEDURE GetIntersection(a1, b1, a2, b2: LONGINT; VAR a, b: LONGINT); BEGIN a := M.Max(a1, a2); b := M.Min(b1, b2) END GetIntersection; August

August Karlstrom wrote: > Chris Dollin wrote: >> August Karlstrom wrote: >> >> >>>bob@coolgroups.com wrote: >>> >>>>what is the fastest way to find the intersection of two 1-dimensional >>>>intervals? >>>> >>>>here's an example: >>>> >>>>interval 1: 0 to 50 >>>>interval 2: 25 to 80 >>>> >>>>answer: 25 to 50 >>>> >>> >>>Here's an implementation in Oberon: (snipped) >> Isn't that a little heavweight? >> >> def intersection( x1, y1, x2, y2) = (max( x1, x2 ), min( y1, y2 )) > > In a high-level functional language with lots of predefined functions, > of course the definition will be shorter (but also slower). Each of `max` and `min` is a one-liner, so even if they're not predefined the definition is /still/ lots shorter. Whether or not it's /slower/ depends on lots and lots of things, such as the type structure of the language, whihc aren't visible in the fragment I wrote above. (For which I have a shortcoded implementation, so it's not just handwaving.) > > Also, your procedure doesn't assign to lower/upper if the result is >> empty, making it easy (when not checking `empty`) to produce garbage; >> also, since it doesn't deliver any useful result, it doesn't compose >> (suppose I want the intersection of three intervals); and it requires >> the invention of not only two integer variables for actual parameters, >> but also a arguably-redundant boolean variable. > > OK, you certainly have a point here. The following version is probably > better: > > (* Gets intersection of specified intervals. Calculates the > intersection [a, b] of the intervals [a1, b1] and [a2, b2]. If the > intersection is empty then a > b. *) > > PROCEDURE GetIntersection(a1, b1, a2, b2: LONGINT; > VAR a, b: LONGINT); > BEGIN > IF a1 > a2 THEN a := a1 ELSE a := a2 END; > IF b1 < b2 THEN b := b1 ELSE b := b2 END > END GetIntersection; Still doesn't compose. > I admit that names like upper and lower may be a bit too verbose, but I > don't think x and y are good names since it makes me think of > two-dimensional coordinates. I prefer a and b. I think you're right that x1/2 and y1/2 have too much of the coordinate flavour. > Note also that Oberon > doesn't have built in functions for the minimum/maximum value of > integers. But of course we can define them in some utility module M. In > that case the function is as short as > > PROCEDURE GetIntersection(a1, b1, a2, b2: LONGINT; > VAR a, b: LONGINT); > BEGIN > a := M.Max(a1, a2); b := M.Min(b1, b2) > END GetIntersection; I like that much better. (Min & Max needn't be in a different module, of course, although they're sufficiently useful that they should be shared somehow.) -- Chris "it's all paraphernalia" Dollin son of a gun, listen to the plants, breathless. shifting sands - life in the fast lane.