Scala Range contains (anything in another Range)?

Question

I am trying to define a simple Scala method to determine if two rectangles overlap in any capacity. I believe the way to do this would be something along the lines of:

if (! (Range_of_rectangle1.contains(anything in Range_of_rectangle2) ) ) => false

And this would need to be done for both the x-axis and the y-axis... But I'm new enough to Scala that I don't sure how to write something like someRange.contains( anything in another Range).

The code I have currently for determining the overlap sorta works but has some problems, as I will discuss:

First I define a Rectangle (and there is a reason that its a case class in my code, but that's unrelated to this task).

case class Rectangle (minx: Int, maxx: Int, miny: Int, maxy: Int)

Then I create the function to look if two rectangles overlap

def rectanglesOverlap(r1: Rectangle, r2:Rectangle): Boolean = {
  r2 match {
     //In English: if r2's minx OR miny are not anywhere in the range of r1's x-axis, then there's no overlap along the x-axis
     //If the range of r1's x-axis does NOT contain anything from r2's x-axis, they don't overlap
     case x_overlap1 if (! (  (r1.minx to r1.maxx).contains(r2.minx) || (r1.minx to r1.maxx).contains(r2.maxx) ) ) => false //where r1 is larger rectangle 
     case y_overlap1 if (! (  (r1.miny to r1.maxy).contains(r2.miny) || (r1.miny to r1.maxy).contains(r2.maxy) ) ) => false
     //If the range of r2's x-axis does NOT contain anything from r1's x-axis, they don't overlap
     case x_overlap2 if (! (  (r2.minx to r2.maxx).contains(r1.minx) || (r2.minx to r2.maxx).contains(r1.maxx) ) ) => false //where r2 is larger rectangle
     case y_overlap2 if (! (  (r2.miny to r2.maxy).contains(r1.miny) || (r2.miny to r2.maxy).contains(r1.maxy) ) ) => false
     case _ => true
  }
}

So what the code tries to do is start with the x- and y-axis of one of the rectangles, and check if the other rectangle's minx/y OR maxx/y is in there....

See the problem?

When I tested it, I got "false" for this:

val q1 = Rectangle(1, 18, 1, 18)  
val q2 = Rectangle(1,8,8,16) 
scala> rectanglesOverlap(q1, q2) 
res0: Boolean = false

And the reason for this is obvious. Its false because the q2 y-axis is 8-16 and neither q1 miny (1) or q1 maxy (18) fall within the 8-16 range. However, its clear that they overlap.

So know that I conceptually know what's wrong with my code, I'm trying to figure out how to programmatically do something like this:

someRange.contains( anything in another Range).

But my efforts of searching Google and Stack Overflow haven't yielded the proper solution. Help?

https://stackoverflow.com/questions/23302698/java-check-if-two-rectangles-overlap-at-any-point — flavian, Jun 08 '17 at 23:18
@flavian - Oh, I didn't think of checking the Java questions for something similar. That's a really good idea! — SnarkShark, Jun 09 '17 at 15:23
@jwvh - Do you want to post your comment as an answer so I can accept it as the right answer to my question? — SnarkShark, Jun 09 '17 at 15:24

score 2 · Accepted Answer · answered Jun 09 '17 at 15:43

2

When you want to know where one collection overlaps another, you're looking for their "intersection".

someRange.intersect(anotherRange)

or

(1 to 18) intersect (8 to 16)

and to turn it into a Boolean

((1 to 18) intersect (8 to 16)).nonEmpty

answered Jun 09 '17 at 15:43

jwvh

50,871
7
38
64

Be careful with this: `intersect` is implemented in `SeqLike`, meaning it uses the naive approach of iterating over the first `Seq`, and checking if each item is contained in the second `Seq`. For large ranges, this is very inefficient. It'd be better to check `someRange.contains(anotherRange.start) || someRange.contains(anotherRange.end)` – Magicmaaan Jun 21 '19 at 18:45

Scala Range contains (anything in another Range)?

1 Answers1