COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### interval intersection

• Email
• Follow

```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

```
 0
Reply bob136 (434) 10/27/2005 5:17:22 AM

See related articles to this posting

```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
>

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.
```
 0
Reply cri (1432) 10/27/2005 6:13:18 AM

```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/
```
 0
Reply christer_ericson (167) 10/27/2005 6:30:42 AM

```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.

```
 0
Reply makc.the.great (199) 10/27/2005 1:30:20 PM

```thanks, rich, chris.  smart stuff

```
 0
Reply bob136 (434) 10/27/2005 2:25:53 PM

```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.
```
 0
Reply cri (1432) 10/27/2005 3:27:12 PM

```your numbers are misterious.

```
 0
Reply makc.the.great (199) 10/27/2005 5:00:32 PM

```On 27 Oct 2005 10:00:32 -0700, makc.the.great@gmail.com wrote:

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.
```
 0
Reply cri (1432) 10/27/2005 6:46:47 PM

```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
>
>

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
```
 0
Reply fusionfive (563) 10/28/2005 12:08:27 PM

```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
>>
>>
>
> 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

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.
```
 0
Reply kers (527) 10/28/2005 12:52:20 PM

```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
>>>
>>>
>>
>> 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.
```
 0
Reply kers (527) 10/28/2005 12:57:33 PM

```--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
>

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--
```
 0
Reply never11 (71) 10/29/2005 8:13:50 AM

```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
>>>
>>>
>>
>>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
```
 0
Reply fusionfive (563) 10/29/2005 11:49:15 AM

```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
>>>>
>>>>
>>>
>>>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.
```
 0
Reply kers (527) 10/31/2005 8:51:23 AM

13 Replies
47 Views

Similar Articles

12/10/2013 2:25:47 PM
[PageSpeed]