Archive for December, 2010

Concise code to check overlap of line segments in 1D

Again I am doing something where I want to see if two rectangles overlap on the X or Y axis, so I got to derive my preferred math for doing this again.

Because it’s easier to write, consider that I’m looking at the rectangles on the X axis, and the rectangles are name A and B. So I can write the rectangle’s left/right edges on a number line as:

A:
AL AR

B:
BL BR

So I was doing the usual intuitive thing of trying to come up with the ways that the two rectangles can overlap… here’s a few:

  • AL BL BR AR
  • AL BL AR BR
  • BL AL BR AR
  • ugh, I give up, I don’t even want to come up with the logic to match this

Thankfully the opposite case is a lot easier to list. ┬áHere’s the ways the two rectangles could be NOT overlapping:

  • AL AR BL BR
  • BL BR AL AR

So the code for the above “Not overlapping” would be AR < BL || BR < AL

Then it becomes easy to get my desired result

  1. !(AR < BL || BR < AL) # inverse
  2. AR >= BL && BR >= AL # apply demorgan’s law
  3. BL <= AR && AL <= BR # reverse the inequalities so it looks nice

Done!

Leave a comment