Sunday, December 11, 2011

No. 27 - Area of Rectangles

Problem: Please implement a function which gets area of a set of rectangles, whose edges are parallel to X-axis or Y-axis.

Rectangles are defined as the following:
/* === Assumming: left <= right; top <= bottom === */
struct Rect
{
    int left;
    int right;
    int top;
    int bottom;
};

Analysis: The merged shape of overlapping rectangles is no longer a rectangle, and there is no equation to calculate the merged area directly. Therefore, we should split it into a set of rectangles.

A solution to split overlapping rectangles is based on x-values of all left and right edges. For example, there are three rectangles in Figure 1.
Figure 1: Three rectangles
We get all x-values of the three rectangles, which are X1, X2, …, X6 in Figure 2, and then split the merged shape into five rectangles based on x-values.

We should merge y-values of rectangles in ranges of x-value. For instance, both Rect1 and Rect2 fill into the x-value range between X2 and X3. Therefore, we should merge the y-value range of Rect1 and Rect2 to calculate the rectangle piece between X2 and X3.
Figure 2: Split rectangles into pieces based on x-values
Since ranges of x-values and y-values are necessary information to calculate area, we can define a class Range:

struct Range
{
    int less;
    int greater;

    Range(int l, int g)
    {
        less = (l < g) ? l : g;
        greater = (l + g) - less;
    }

    bool IsOverlapping(const Range& other)
    {
        return !(less > other.greater || other.less > greater);
    }

    void Merge(const Range& other)
    {
        if(IsOverlapping(other))
        {
            less = (less < other.less) ? less : other.less;
            greater = (greater > other.greater) ? greater : other.greater;
        }
    }
};

The overall algorithm to calculate the area of overlapping rectangles is: We firstly get all x-values of all rectangles, and then check whether every rectangle fills into each range formed by two neighboring x-values. If there are multiple rectangles fill into an x-value range, we merge their ranges of y-value before we calculate the area of a piece of merged rectangle.

The following function GetArea implements this algorithm. For optimization purpose, we sort all input rectangles according to their x-values of right edges, and sort a vector of all x-values.

int GetArea(vector<Rect>& rects)
{
    // sort rectangles according to x-value of right edges
    sort(rects.begin(), rects.end());

    vector<int> xes;
    GetAllX(rects, xes);
    sort(xes.begin(), xes.end());

    int area = 0;
    vector<int>::iterator iterX1 = xes.begin();
    vector<Rect>::const_iterator iterRect = rects.begin();
    for(; iterX1 != xes.end() && iterX1 != xes.end() - 1; ++ iterX1)
    {
        vector<int>::iterator iterX2 = iterX1 + 1;

        // filter out duplicated X-es
        if(*iterX1 < *iterX2)
        {
            Range rangeX(*iterX1, *iterX2);

            while(iterRect->right < *iterX1)
                ++ iterRect;

            list<Range> rangesOfY;
            GetRangesOfY(rects, iterRect, rangeX, rangesOfY);
            area += GetRectArea(rangeX, rangesOfY);
        }
    }

    return area;
}

bool operator < (const Rect& rect1, const Rect& rect2)
{
    return (rect1.right < rect2.right);
}

The following function GetAllX gets all x-values of all input rectangles.

void GetAllX(const vector<Rect>& rects, vector<int>& xes)
{
    vector<Rect>::const_iterator iter = rects.begin();
    for(; iter != rects.end(); ++ iter)
    {
        xes.push_back(iter->left);
        xes.push_back(iter->right);
    }
}

The function GetRangesOfY gets the ranges of y-values which fill into a range of x-value. It should be noticed that there might be multiple non-overlapping rectangles fill into an x-value range. For example, Rect1 and Rect2 in Figure do not overlap with each other. Therefore, we cannot merge their ranges of y-values. That is why it has a list of ranges of y-values for a range of x-value in the function GetRangesOfY.
Figure 3: Another example of three overlaping rectangles

void GetRangesOfY(const vector<Rect>& rects, vector<Rect>::const_iterator iterRect, const Range& rangeX, list<Range>& rangesOfY)
{
    for(; iterRect != rects.end(); ++ iterRect)
    {
        if(rangeX.less < iterRect->right && rangeX.greater > iterRect->left)
            InsertRangeY(rangesOfY, Range(iterRect->top, iterRect->bottom));
    }
}

The function InsertRangeY inserts a range of y-value into a list. When the range overlaps with another range existing in the list, we should remove the existing range and then insert a new merged range.

void InsertRangeY(list<Range>& rangesOfY, Range& rangeY)
{
    list<Range>::iterator iter = rangesOfY.begin();
    while(iter != rangesOfY.end())
    {
        if(rangeY.IsOverlapping(*iter))
        {
            rangeY.Merge(*iter);

            list<Range>::iterator iterCopy = iter;
            ++ iter;
            rangesOfY.erase(iterCopy);
        }
        else
            ++ iter;
    }

    rangesOfY.push_back(rangeY);
}

The function GetRectArea below gets the total area of all rectangle pieces in a range of x-value.

int GetRectArea(const Range& rangeX, const list<Range>& rangesOfY)
{
    int width = rangeX.greater - rangeX.less;
   
    list<Range>::const_iterator iter = rangesOfY.begin();
    int area = 0;
    for(; iter != rangesOfY.end(); ++ iter)
    {
        int height = iter->greater - iter->less;
        area += width * height;
    }

    return area;
}

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your printed books, please contact me (zhedahht@gmail.com) . Thanks.

17 comments:

  1. Hi Harry,

    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key Area of Rectangles in the entire space.

    I am a freelancer and I previously created an account using a Gmail address and obtained my certification with this account. During the registration process of the APN program it needs a non-Gmail address so i used my professional address, how can i merge or link the certifications of my first account with the APN program?
    An Elastic Load Balancer ensures that the incoming traffic is distributed optimally across various AWS instances. A buffer will synchronize different components and makes the arrangement additional elastic to a burst of load or traffic.

    Super likes !!! for this amazing post. I think everyone should bookmark this.

    Thanks a heap,
    Kevin

    ReplyDelete

  2. Sain Bainuu,

    Thanks for highlighting this and indicating about No. 27 - Area of Rectangles where more study and thought is necessary.

    If I buy a Route 53 domain name, can I create an email address and use it with gmail? If so, how? AWS Tutorial
    I do not want to use Workmail, or SES or an EC2 instance.
    All I want is a username, password, and SMTP and whatever else is needed to link my route 53 email to gmail.

    Very useful article, if I run into challenges along the way, I will share them here.

    Cheers,
    Irene Hynes

    ReplyDelete
  3. Hi Bro,


    So bloody thorough! Ah! So happy and blissed out! I feel redeemed by reading out No. 27 - Area of Rectangles . Keep up the good work!

    On our AWS linux AMIs this morning I'm noticing that the openssl cannot be updated past version 1.0.1k, that is vulnerable to the DROWN attack. We'd like to update to the 1.0.1s version, but it's not available. Of most concern is the NAT instances that AWS creates for the VPC, we've got them locked down with security groups, but would still like to be able to patch the instances. AWS Training






    THANK YOU!! This saved my butt today, I’m immensely grateful.


    MuchasGracias,
    Ajeeth

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Cheap Essay Writing Service

    In my opinion apart from getting all the questions right, the best way to impress the interviewer is to answer behavioral questions seamlessly. Several large companies have added additional focus to behavioral interviews.

    ReplyDelete
  6. No deposit bonus 2021 | Casino - TrickToAction
    The best part about 파워볼 중국점 사이트 벳무브 no deposit bonus is 먹튀검증소 that 메이저 토토 사이트 넷마블 you can win real money playing your favorite casino games for free. At the 토토 사이트 추천 샤오 미 same time, you need to batman 토토 넷마블 do not take advantage

    ReplyDelete
  7. This is why the Advocate Law Center has provided legal assistance, advocacy, and representation to clients throughout the these communities for decades. With attorneys who are skilled and Criminal Defense Lawyerexperienced in family law, personal injury, and criminal defense, we can provide your family with the legal help needed to help your family move forward in life, with each family member’s needs being addressed.

    ReplyDelete
  8. To find the area of a rectangle with decimals, simply use the same formula as you would for a rectangle with whole numbers: A = l x w. However, in this case, the length and width measurements will include decimals.

    Read more: The Power of Blind Review: A Game-Changing LSAT Strategy

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. This comment has been removed by the author.

    ReplyDelete
  11. Thank you for this implementation. I've ported it to C# to aid me in the construction of a prototype design automation program using a genetic algorithm. Your name and a link to this article are part of the source code now.

    ReplyDelete
  12. You can see some of the results in my blog, by the way....
    https://human-assisted.blogspot.com/2023/04/prototypes-ports-and-appropriateness.html

    ReplyDelete
  13. Thanks for the information! Please continue sharing such valuable insights. Looking kase abusharkh amy berry forward to more updates.

    ReplyDelete
  14. Break through fitness plateaus with Cross Training at ESTLR Athletics. Our holistic approach combines powerlifting, CrossFit, and strength training for a diversified fitness experience.

    ReplyDelete
  15. A dedicated Dentistry CAD designers, We Dental CAD services utilize our expertise in computer-aided design to create precise and lifelike dental prosthetics.

    ReplyDelete
  16. Containers Hawaii is your go-to source for top-quality shipping container hawaii, offering a diverse range of services and custom modifications. As Hawaii's trusted container provider, the website provides a user-friendly experience, allowing visitors to explore specials, purchase or rent containers, and explore customization options.

    ReplyDelete