Find count of overlapping rectangles

0
votes

Given a cartesian plane and rectangle on this plane where bottom-left corner has coordinates (x1, y1), the top-right one has coordinates (x2, y2).

Now I need to find the count of those rectangles that have the common area with the rectangle with a bottom-left corner coordinates (x1, y1) and a top-right corner coordinates (x2, y2).

How this can be done in an efficient way?

Their can be many such queries of the form x1 y1 x2 y2 and for given rectangle i need to find count of overlapping rectangles.Also even if the two rectangles only share a common point, they are still regarded as sharing common area.There can be a few same rectangles on the plane, they should be regarded as a few different rectangles.

The main point is rectangles can be added and deleted at any given instant.

Constraints :

Their can be total of 10^5 queries.And each coordinate can go from 1 to 10^9.

My approach : We know that Suppose we have two rectangles R1 and R2. Let (x1, y1) be the location of the bottom-left corner of R1 and (x2, y2) be the location of its top-right corner. Similarly, let (x3, y3) and (x4, y4) be the respective corner locations for R2. The intersection of R1 and R2 will be a rectangle R3 whose bottom-left corner is at (max(x1, x3), max(y1, y3)) and top-right corner at (min(x2, x4), min(y2, y4)).

If max(x1, x3) > min(x2, x4) or max(y1, y3) > min(y2, y4) then R3 does not exist, ie R1 and R2 do not intersect.

Now main problem with me that ma facing is say we have insert query of say (I X1 Y1 X2 Y2) and delete query of type(D index) which will delete rectangle inserted at index th query of insertion.How to handle them efficiently

2
algorithm
I have a quick question on your question. You begin by saying that you have a single rectangle, but toward the end of your question you're implying that there can be multiple rectangles. Is the goal to store a collection of rectangles and determine how many overlapping regions there are at any instant, given that rectangles can be added and deleted? - templatetypedef
@templatetypedef Yeah their can be multiple same rectangles too. Adn they are considered different.Also their can be insertion of rectangle and deletion of ith inserted rectangle - just code
@justcode To confirm - the problem is to maintain a set of rectangles and support the operations "add rectangle," "remove rectangle," and "report the total number of overlapping rectangles?" - templatetypedef
@templatetypedef Yeah right.But their can be MULTIPLE SAME RECTANGLES too.So set wont be perfect word to use - just code
I think you need two dimensional interval tree. - Ivaylo Strandjev

2 Answers

0
votes

An R-tree should work. See http://en.wikipedia.org/wiki/R-tree for more.

0
votes

I wrote a solution in C# for a similar problem

https://github.com/ERufian/Overlap/blob/master/RectangleOverlap/Heap.cs

With minor modifications it would do what you need:

namespace RectangleOperations
{
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Windows;

  public static class Heaped
  {
    public static int GetOverlap(double x1, double y1, double x2, double y2, Rect[] rects, int rectCount)
    {
      Rect startingArea = new Rect(new Point(x1, y1), new Point(x2, y2));
      return Overlap(startingArea, 0, 0, rects, rectCount)
    } 

    private static int Overlap(Rect currentArea, int currentIndex, int currentCount, Rect[] rects, int rectCount)
    {
      List<int> counts = new List<int>();
      for (int i = currentIndex; rectCount > i; i++)
      {
        Rect newArea = currentArea;
        newArea.Intersect(rects[i]);

        // include point and edge (size 0) overlaps
        if (0 <= newArea.Size.Height && 0 <= newArea.Size.Width) 
        {
          counts.Add(Overlap(newArea, i + 1, currentCount + 1));
        }
      }

      return (0 == counts.Count) ? currentCount : counts.Max();
    }
  }
}

Some help for translating this code if not using C#

Rect.Intersect calculates the intersection of the current rectangle with another rectangle and replaces the current rectangle.

List<> is a dynamic array (that grows as you add items), you can use regular arrays but then you'll need to calculate sizes, keep track of how many items were actually added and provide a way to calculate the Max.