9

I wrote a drawing function that draws various on-screen sprites. These sprites can only overlap up to a point. If they have to much overlap, they become too obscured. As a result I need to detect when these sprites are too much overlapped. Luckily, the problem is simplified in that the sprites can be treated as orthogonal rectangles. I'd like to know by how much these rectangles overlap. Right now, I just brute force it by testing each pixel in one rectangle to see if the other contains it. I count these and calculate the percentage overlap. I think there's probably a better, less brute force approach. What algorithm can I use to determine this?

I'm using wxwidgets.

dagorym
  • 5,695
  • 3
  • 25
  • 23
max
  • 1,020
  • 1
  • 15
  • 25
  • What have you got so far? Is this homework? – Donut Sep 17 '09 at 19:54
  • 1
    Is this a homework question? Also, you should consider defining the "percentage" more clearly. Your question can be interpreted at least two ways - for example, as the percentage of the total covered area that is occupied by both rectangles instead of one of them, or the percentage of the area of rect1 that is covered by rect2. – jprete Sep 17 '09 at 19:55
  • 1
    http://stackoverflow.com/questions/244452/what-is-an-efficient-algorithm-to-find-area-of-overlapping-rectangles – madcolor Sep 17 '09 at 19:55
  • 2
    Also, percentage of which rectangle? If a very large rectangle overlaps a much smaller rectangle, it could be (say) 50% of the small rectangle is overlapped, while .1% of the large rectangle is overlapped. – Chris Simmons Sep 17 '09 at 19:56
  • Yeah it depends which one is on top. Crap question tbh – demoncodemonkey Sep 17 '09 at 19:58
  • The "&" in your function prototype is a syntax error in C. – pmg Sep 17 '09 at 20:01
  • 2
    Who voted this as "blatantly offensive?" That's somewhat silly. Similarly with not-programming-related. It is. Rather, I'd say it's not a question. It's more of a command ("do this for me"). Obviously homework. So max: You won't learn if you don't try. Tell us what you have so far, where you're stuck, etc... If you don't want to do your own work, why would we want to? We want to help, that's why we are here, but most people here also know doing your homework isn't really helping you. – GManNickG Sep 17 '09 at 20:08
  • I've also removed the C tags since this is not C code. Also, inb4 someone adds "plz-send-teh-code". **Don't.** Tags are for searching, not for being cute. – GManNickG Sep 17 '09 at 20:09
  • 4
    Homework!? I wish. Look at my other questions in my profile. Does it look like I'm in school? I'll delete it if it upsets people I guess. – max Sep 17 '09 at 20:13
  • The point is you haven't put any effort into yourself. If you have, how are we to know unless you show it? Nobody here wants to do your work, we want to teach and help. There's a difference. Where are you stuck? What have you tried? Why do you need to do this? Give us the big picture, and your attempts to fill it in. Don't delete it, fix it. Look at your "question", and tell me if you can find a question mark. What's your question? – GManNickG Sep 17 '09 at 20:18
  • @max: This is a math question, not a programming question. If you have figured out the math formula and are having trouble coding it, post another question showing the formula you are trying to code. – Drew Dormann Sep 17 '09 at 20:36
  • 1
    This is a much better question, now. – GManNickG Sep 17 '09 at 21:52

1 Answers1

9

The results depends on how you define overlapping percentage, to keep it symmetric, I would code it like this:

double CalculatePercentOverlap(const wxRect& rect1, const wxRect& rect2)
{
  wxRect inter = rect1.Intersect(rect2);
  if (inter.IsEmpty())
    return 0;
  return (double)(inter.GetWidth()*inter.GetHeight()) * 2.0 /
    (double)(rect1.GetWidth()*rect1.GetHeight() + 
             rect2.GetWidth()*rect2.GetHeight());
}
jdehaan
  • 19,700
  • 6
  • 57
  • 97
  • Ahh you are brilliant. Did not know of the intersect function. Hey, people are getting upset about this looking like a homework question. I was too terse in my questioning. So, I'll probably delete it. Does deleting remove your points cause if it does i'll leave it. Thanks. – max Sep 17 '09 at 20:17
  • Do the wxRect objects handle rectangles that aren't parallel with the axes? – baumgart Sep 17 '09 at 20:23
  • 1
    @max - it would remove the points if his rep were recalculated, which will happen eventually – John Rasch Sep 17 '09 at 20:24
  • 2
    I'd leave this. Don't delete your question since somebody in the future could find this useful. – GManNickG Sep 17 '09 at 20:39
  • 1
    Also, you should prefer `static_cast` over C-style casts. – GManNickG Sep 17 '09 at 20:45
  • 1
    @max you can still edit your question, explaining what you meant. that will probably make people retract their -1 or upvote you – Johannes Schaub - litb Sep 17 '09 at 20:54
  • 1
    Should be noted that this function returns the percentage that the smaller rectangle is to the larger one. So the parameter order does not matter CalculatePercentageOverlay(wxRect(0,0,200,200), wxRect(0,0,50,50)) gives the same answer as CalculatePercentageOverlay(wxRect(0,0,50,50), wxRect(0,0,200,200)) – max Sep 29 '09 at 07:13
  • @max sounds to me like a kind of special case (rects having a common corner) if you translate the smaller one to the negative coodinates, then you will have non trivial results. The "overlap" relation must be symmetric I think because there is no order R1 must relate to R2 as R2 to R1. Hope I understood you well :-) – jdehaan Sep 29 '09 at 10:22