Fastest way to check if ranges only intersect, but not subsume

Question

Let's say I have two ranges (x1,x2) and (z1,z2). What is fastest way to check if they intersect?

 if 
 #case: (2,4), (3,6)
 x1 > z1 < x2 and (z2 < x1 or z2 > x2)
 or
 #case: (2,4) , (1,3)
 x1 > z2 < x2 and (z1 < x1 or z1 > x2)
 or
 #case: (3,6), (2,4)
 ............. reverse(1) x <--> z
 or
 #case: (1,3), (2,4)
 ............. reverse(2) x <--> z

BTW containing one range in the other is OK, for example

 (2,5) , (3,4)
 (2,5) , (3,5)
 (2,5) , (2,4)

(this makes the question not a duplicate. In addition the conditions are <, > rather than >=, <=. And one more I expect input ranges to be also unordered, for example (x2,x1),(z2,z1) ; (z1,z2),(x1,x2) )

But this, for example, does not count as intersection:

 (2,5), (2,5)

What is a faster way with less checks?

NOT a duplicate ... here is the solution :

def olap(x1,x2,z1,z2):

    if x1 == x2 or z1 == z2 : return True
    if x1 == z1 and x2 == z2 : return True

    if x1 > x2 : x1,x2 = x2,x1
    if z1 > z2 : z1,z2 = z2,z1
    if x1 > z1 or x2 > z2 : z1,z2,x1,x2 = x1,x2,z1,z2

    return x1 < z1 < x2 and (z2 < x1 or z2 > x2)

In my opinion - using python ranges and sets operations. Fox example: r1 = set(range(x1,x2)) r2 = set(range(z1,z2)) # Use sets intersections operators... — Daniel Agam, Oct 23 '22 at 14:09
@DanielAgam IMO, this is a bad suggestion. It will solve a simple mathematical problem in an extremely cumbersome way. — Mechanic Pig, Oct 23 '22 at 14:42

Nikos Athanasiou · Answer 1 · 2022-10-24T10:32:49.453

1

Simplest check is to verify a property of intersecting intervals: None of the leftmost endpoints (smaller) can be higher than a rightmost endpoint (higher).

 x1        x2
a ------------              if x1 > y2: a would be to the right of b            
       b ----------------   if y1 > x2: b would be to the right of a
           y1           y2

def overlap(x1, x2, y1, y2):
    """ Overlap means neither of the intervals 
        is "to the right or left" of the other.
    """
    return x1 <= y2 and y1 <= x2

edited Oct 24 '22 at 10:32

answered Oct 23 '22 at 14:15

Nikos Athanasiou

29,616
15
87
153

i see.. i have to order the range in advance i.e. (4,2) => (2,4) – sten Oct 23 '22 at 14:24
@sten Not "order", just getting the min and max (assuming there's >2 elements). implemetation should depend on your use case: if you don't check everything for overlapping maybe you don't want to pre-process all intervals and do it on the fly inside your function. That been said I don't how good an "interval" representation if it's in arbitrary ordering – Nikos Athanasiou Oct 23 '22 at 14:31

Fastest way to check if ranges only intersect, but not subsume

1 Answers1