Welcome to the MacNN Forums.

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

You are here: MacNN Forums > Software - Troubleshooting and Discussion > Developer Center > Determining if two rectangles overlap (binary manipulation)

Determining if two rectangles overlap (binary manipulation)
Thread Tools
Synotic
Mac Elite
Join Date: Oct 2000
Status: Offline
Reply With Quote
Jan 14, 2008, 10:06 PM
 
Hi guys,

I am working on a project where I need to determine if two rectangles are overlapping or not. I have something working, but it is inefficient, and uses unnecessary comparisons. I was looking on the internet for something better, and I found an interesting article here. It says that it's possible to determine the overlap "at a cost of just 1 boolean operation and a comparison." The problem is that my binary manipulation skills aren't up to snuff and I'm having trouble understanding the resulting algorithm:
Assume, that we have the values of 4 edges of the first rectangle ABCD in a variable X, coded in 4 bits; and similarly those of the second rectangle EFGH in a variable Y. The order of the edges does not matter, as long as both variables use the same order and the 4 bits are in the same position.

Then X OR Y will perform all 4 Boolean OR operations in one go. Let's store the result in variable Z and name the 4 resulting bits IJKL.

Now it is only left to find out, if any of the bits in IJKL is 0. If so, no overlapping area exists for the two inputs. If all 4 bits are set to 1, though, then such an overlapping area exists.

And because the 4 bits form an unambigeous value when all set, this can be found out with just one comparison. E.g., assume that the 4 bits all are in the least significant bits of a word (bit values from LSB to MSB: 1+2+4+8). Then:

IF Z = 15 THEN
Overlapping
ELSE
Not Overlapping
FI
Let's say that my coordinate system is at the top left and I have one rectangle (1, 5, 2, 2) and another rectangle (1, 4, 3, 3), where they're in the order (top, right, bottom, left). How would I, in general, implement this in actual code? I am planning to actually better understand what's going on behind the scenes, but if possible, I'd like to figure out first .

Thanks for any help!
     
numero
Junior Member
Join Date: Mar 2000
Location: Salem, OR, USA
Status: Offline
Reply With Quote
Jan 17, 2008, 02:57 AM
 
I don't believe that this article will help you with your problem. The article deals with two sub areas of two rectangles and not just two rectangles.

For your problem you have to figure out if there is an intersection of the horiz. edges of Rect. A with Rect. B AND an intersection with the vert. edges of Rect. A with Rect. B.

Be careful with the case of one rectangle encompassing the other.

I was going to do pseudo code, but it is late. Post what you have and I can let you know if I see any problems or efficiency improvements.
     
Catfish_Man
Mac Elite
Join Date: Aug 2001
Status: Offline
Reply With Quote
Jan 17, 2008, 03:03 AM
 
NSIntersectsRect()?
     
Synotic  (op)
Mac Elite
Join Date: Oct 2000
Status: Offline
Reply With Quote
Jan 17, 2008, 04:35 AM
 
Thanks for the responses guys.

Catfish_Man: I am actually doing JavaScript development, so I don't think I'll be able to use that

numero: You're absolutely right. I should have realized something was up when I was trying to fit four integer widths into 4 bits. I ended up looking around the web and adapted a general algorithm into this:

r_b >= i_t && r_t <= i_b && r_r >= i_l && r_l <= i_r

where r_* is one rectangle and i_* is another. It's a lot better than what I had before and I can't imagine it getting any simpler, but if you have any ideas, be my guest .

If you guys are interested in what I am working on, I am trying to develop some generic web based tools for selecting a group of images (or any HTML elements), and then dragging them into albums. Here is an example of what I have so far:

Rubber band image selection

After selecting a group of pictures, you can start dragging them. The actual rubber band selection code can get a little confused if you drag outside of the light gray frame, but this is prohibited in the second example, and seems to fix the funniness. You can command-click additional images. Shift-clicking isn't yet enabled. Still working on it.

One thing you'll notice is that if you make the window nice and small, and try to drag to the edge, it won't move. This is because I had to disable the text selection mechanism because it messes up everything else. That meant I had to code up a mechanism to auto scroll the window when you're in certain proximity to the edge (and accelerate as you get closer to the edge). It turned out to be quite a bit more work than I originally envisioned, but it seems to work:

Scrolling

You can drag from inside the frame to outside the window, but the selection doesn't escape the frame. As you approach the edge of the window, it begins to scroll. It isn't as smooth as I'd like it in Firefox, but again I'm still working on. There's a lot of subtlety in making it work just right.

Sorry for the rambling on, but I'm really happy with how it's turning out. I plan to eventually package it up and offer it as a reusable class when I'm done (the code's very messy right now). As far as I know, there isn't one available freely.

And no, I haven't tested in IE. And yes, I know I'm in for a world of pain
( Last edited by Synotic; Jun 14, 2008 at 06:06 PM. Reason: Updated links)
     
   
Thread Tools
 
Forum Links
Forum Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Top
Privacy Policy
All times are GMT -4. The time now is 10:39 AM.
All contents of these forums © 1995-2017 MacNN. All rights reserved.
Branding + Design: www.gesamtbild.com
vBulletin v.3.8.8 © 2000-2017, Jelsoft Enterprises Ltd.,