1
$\begingroup$

This is for a web app, but I think it's a general geometric problem, and almost certainly a solved one:

I have a rectangle $(A)$ and I know its size. I'm trying to figure out if there's another rectangle $(B)$ overlapping mine, and by how much to $25\%$ accuracy. (That is, I want to know if $B$ is covering $0\%$, $0-25\%$, $25-50\%$, $50-75\%$ or $100\%$ of $A$.)

  • There may or may not be a second rectangle.
  • There may be more than one other rectangle.
  • The rectangles are all oriented parallel to each other (no rotation).
  • I can only test by checking for an overlap at a particular point on my rectangle's surface.

I'm trying to figure out the most efficient possible arrangement of detection points. Ideally, I'd simply be able to count up the number of hits to know the $\%$ in some kind of simple linear way. Something like the image in this overlap detection drawing.

$\hskip{2.8in}$Overlap detection Drawing

  • 0
    The answer might depend on whether the sides of the other rectangles are always perpendicular/parallel to the sides of the first rectangle.2012-02-29
  • 0
    They are parallel. Well... in theory, there could be rotation, but it's extremely rare, so let's assume "no" for now. It doesn't have to be a perfect approximation.2012-02-29
  • 0
    So for an overlap of >25%, the centre of the rectangle will be covered. And I have a feeling that there will be points along the line from the centre to each vertex that suffice to show more overlap? I'm not sure.2012-02-29
  • 0
    >50%, I agree, but couldn't you have an overlap like that in the drawing that was just shy of 50% without the centre being covered?2012-02-29
  • 0
    Oh yeah. I was just imagining congruent rectangles sliding over each other. And even there I was being silly. So this is true: it is a necessary condition on >50% being covered, that the centre is covered. But it is not sufficient. A sufficient condition for >25% coverage is one vertex and the centre covered. But this is not necessary.2012-02-29
  • 0
    0-25% seems to be the tricky bit. I think I have to check each point along the perimeter to be certain about that.2012-02-29

1 Answers 1