There is a solution listed at the link http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.html for finding the total area of multiple rectangles such that the overlapped area is counted only once.
The above solution can be extended to compute only the overlapped area(and that too only once even if the overlapped area is covered by multiple rectangles) with horizontal sweep lines for every pair of consecutive vertical sweep lines.
If aim is just to find out the total area covered by the all the rectangles, then horizontal sweep lines are not needed and just a merge of all the rectangles between two vertical sweep lines would give the area.
On the other hand, if you want to compute the overlapped area only, the horizontal sweep lines are needed to find out how many rectangles are overlapping in between vertical (y1, y2) sweep lines.
Here is the working code for the solution I implemented in Java.
import java.io.*;
import java.util.*;
class Solution {
static class Rectangle{
int x;
int y;
int dx;
int dy;
Rectangle(int x, int y, int dx, int dy){
this.x = x;
this.y = y;
this.dx = dx;
this.dy = dy;
}
Range getBottomLeft(){
return new Range(x, y);
}
Range getTopRight(){
return new Range(x + dx, y + dy);
}
@Override
public int hashCode(){
return (x+y+dx+dy)/4;
}
@Override
public boolean equals(Object other){
Rectangle o = (Rectangle) other;
return o.x == this.x && o.y == this.y && o.dx == this.dx && o.dy == this.dy;
}
@Override
public String toString(){
return String.format("X = %d, Y = %d, dx : %d, dy : %d", x, y, dx, dy);
}
}
static class RW{
Rectangle r;
boolean start;
RW (Rectangle r, boolean start){
this.r = r;
this.start = start;
}
@Override
public int hashCode(){
return r.hashCode() + (start ? 1 : 0);
}
@Override
public boolean equals(Object other){
RW o = (RW)other;
return o.start == this.start && o.r.equals(this.r);
}
@Override
public String toString(){
return "Rectangle : " + r.toString() + ", start = " + this.start;
}
}
static class Range{
int l;
int u;
public Range(int l, int u){
this.l = l;
this.u = u;
}
@Override
public int hashCode(){
return (l+u)/2;
}
@Override
public boolean equals(Object other){
Range o = (Range) other;
return o.l == this.l && o.u == this.u;
}
@Override
public String toString(){
return String.format("L = %d, U = %d", l, u);
}
}
static class XComp implements Comparator<RW>{
@Override
public int compare(RW rw1, RW rw2){
//TODO : revisit these values.
Integer x1 = -1;
Integer x2 = -1;
if(rw1.start){
x1 = rw1.r.x;
}else{
x1 = rw1.r.x + rw1.r.dx;
}
if(rw2.start){
x2 = rw2.r.x;
}else{
x2 = rw2.r.x + rw2.r.dx;
}
return x1.compareTo(x2);
}
}
static class YComp implements Comparator<RW>{
@Override
public int compare(RW rw1, RW rw2){
//TODO : revisit these values.
Integer y1 = -1;
Integer y2 = -1;
if(rw1.start){
y1 = rw1.r.y;
}else{
y1 = rw1.r.y + rw1.r.dy;
}
if(rw2.start){
y2 = rw2.r.y;
}else{
y2 = rw2.r.y + rw2.r.dy;
}
return y1.compareTo(y2);
}
}
public static void main(String []args){
Rectangle [] rects = new Rectangle[4];
rects[0] = new Rectangle(10, 10, 10, 10);
rects[1] = new Rectangle(15, 10, 10, 10);
rects[2] = new Rectangle(20, 10, 10, 10);
rects[3] = new Rectangle(25, 10, 10, 10);
int totalArea = getArea(rects, false);
System.out.println("Total Area : " + totalArea);
int overlapArea = getArea(rects, true);
System.out.println("Overlap Area : " + overlapArea);
}
static int getArea(Rectangle []rects, boolean overlapOrTotal){
printArr(rects);
// step 1: create two wrappers for every rectangle
RW []rws = getWrappers(rects);
printArr(rws);
// steps 2 : sort rectangles by their x-coordinates
Arrays.sort(rws, new XComp());
printArr(rws);
// step 3 : group the rectangles in every range.
Map<Range, List<Rectangle>> rangeGroups = groupRects(rws, true);
for(Range xrange : rangeGroups.keySet()){
List<Rectangle> xRangeRects = rangeGroups.get(xrange);
System.out.println("Range : " + xrange);
System.out.println("Rectangles : ");
for(Rectangle rectx : xRangeRects){
System.out.println("\t" + rectx);
}
}
// step 4 : iterate through each of the pairs and their rectangles
int sum = 0;
for(Range range : rangeGroups.keySet()){
List<Rectangle> rangeRects = rangeGroups.get(range);
sum += getOverlapOrTotalArea(rangeRects, range, overlapOrTotal);
}
return sum;
}
static Map<Range, List<Rectangle>> groupRects(RW []rws, boolean isX){
//group the rws with either x or y coordinates.
Map<Range, List<Rectangle>> rangeGroups = new HashMap<Range, List<Rectangle>>();
List<Rectangle> rangeRects = new ArrayList<Rectangle>();
int i=0;
int prev = Integer.MAX_VALUE;
while(i < rws.length){
int curr = isX ? (rws[i].start ? rws[i].r.x : rws[i].r.x + rws[i].r.dx): (rws[i].start ? rws[i].r.y : rws[i].r.y + rws[i].r.dy);
if(prev < curr){
Range nRange = new Range(prev, curr);
rangeGroups.put(nRange, rangeRects);
rangeRects = new ArrayList<Rectangle>(rangeRects);
}
prev = curr;
if(rws[i].start){
rangeRects.add(rws[i].r);
}else{
rangeRects.remove(rws[i].r);
}
i++;
}
return rangeGroups;
}
static int getOverlapOrTotalArea(List<Rectangle> rangeRects, Range range, boolean isOverlap){
//create horizontal sweep lines similar to vertical ones created above
// Step 1 : create wrappers again
RW []rws = getWrappers(rangeRects);
// steps 2 : sort rectangles by their y-coordinates
Arrays.sort(rws, new YComp());
// step 3 : group the rectangles in every range.
Map<Range, List<Rectangle>> yRangeGroups = groupRects(rws, false);
//step 4 : for every range if there are more than one rectangles then computer their area only once.
int sum = 0;
for(Range yRange : yRangeGroups.keySet()){
List<Rectangle> yRangeRects = yRangeGroups.get(yRange);
if(isOverlap){
if(yRangeRects.size() > 1){
sum += getArea(range, yRange);
}
}else{
if(yRangeRects.size() > 0){
sum += getArea(range, yRange);
}
}
}
return sum;
}
static int getArea(Range r1, Range r2){
return (r2.u-r2.l)*(r1.u-r1.l);
}
static RW[] getWrappers(Rectangle []rects){
RW[] wrappers = new RW[rects.length * 2];
for(int i=0,j=0;i<rects.length;i++, j+=2){
wrappers[j] = new RW(rects[i], true);
wrappers[j+1] = new RW(rects[i], false);
}
return wrappers;
}
static RW[] getWrappers(List<Rectangle> rects){
RW[] wrappers = new RW[rects.size() * 2];
for(int i=0,j=0;i<rects.size();i++, j+=2){
wrappers[j] = new RW(rects.get(i), true);
wrappers[j+1] = new RW(rects.get(i), false);
}
return wrappers;
}
static void printArr(Object []a){
for(int i=0; i < a.length;i++){
System.out.println(a[i]);
}
System.out.println();
}
