Calculate the area of rectangles union

Question 1

I’ve been given the following task:

Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program arguments. Input is represented by N lines with 4 numbers separated by spaces, defining 2 opposite vertices of the rectangle. Output file should contain 1 number – the resulting area of the rectangles’ union.

Additional constraints:

$1 le N le 100$
$-10000 le x1$ , $y1$ , $x2$ , $y2 le 10000$
Memory consumption < 16 MB
Program parameters should be validated
Input file format should be validated.

Examples:

Input:

1 1 7 7

Output:

Input:

1 1 3 3  
2 2 4 4

Output:

My solution:

public class Main {

    private List<Rectangle> rectangles = new ArrayList<>();

    public static void main(String[] args) {
        if (args.length != 2) {
            throw new IllegalArgumentException("Invalid arguments numbernProgram usage: java Main input output");
        }

        Main computer = new Main();
        long area = computer.computeAreaFromFile(args[0]);
        computer.writeAreaToFile(area, args[1]);
    }

    public long computeAreaFromFile(String inputFileName) {
        rectangles.clear();

        String line;
        try (BufferedReader inputFileReader = new BufferedReader(new FileReader(inputFileName))) {
            long area = 0;

            while ((line = inputFileReader.readLine()) != null) {
                Rectangle rectangle = Rectangle.fromString(line);
                area += addRectangleArea(rectangle, false);
            }

            return area;
        } catch (FileNotFoundException e) {
            throw new IllegalArgumentException("Input file not found");
        } catch (IOException e) {
            throw new RuntimeException(e);
        } catch (NumberFormatException | IndexOutOfBoundsException e) {
            throw new IllegalArgumentException("Input file contains incorrect line");
        }
    }

    private int addRectangleArea(Rectangle newRectangle, boolean isIntersection) {
        int result = 0;

        boolean hasIntersections = false;

        for (Rectangle existingRectangle : rectangles) {
            if (!existingRectangle.contains(newRectangle)) {
                List<Rectangle> complements = existingRectangle.complementOf(newRectangle);
                if (complements.size() > 0) {
                    hasIntersections = true;

                    for (Rectangle complement : complements) {
                        result += addRectangleArea(complement, true);
                    }

                    break;
                }
            }
        }

        if (!hasIntersections) {
            result += newRectangle.area();
        }

        if (!isIntersection) {
            rectangles.add(newRectangle);
        }

        return result;
    }

    private void writeAreaToFile(long area, String outputFileName) {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
            writer.write(String.valueOf(area));
        } catch (IOException e) {
            throw new RuntimeException("Could not open file " + outputFileName);
        }
    }
}

class Rectangle {
    public final int x1;
    public final int y1;
    public final int x2;
    public final int y2;

    public static Rectangle fromString(String input) throws NumberFormatException, IndexOutOfBoundsException {
        String[] splitInput = input.split(" ");

        if (splitInput.length != 4) {
            throw new IndexOutOfBoundsException();
        }

        return new Rectangle(Integer.valueOf(splitInput[0]),
            Integer.valueOf(splitInput[1]),
            Integer.valueOf(splitInput[2]),
            Integer.valueOf(splitInput[3]));
    }

    public Rectangle(int x1, int y1, int x2, int y2) {
        this.x1 = Math.min(x1, x2);
        this.y1 = Math.min(y1, y2);
        this.x2 = Math.max(x1, x2);
        this.y2 = Math.max(y1, y2);
    }

    /**
     * Finds a relative complement of the specified rectangle.
     *
     * @param rectangle rectangle to find a complement of.
     * @return {@link List} of the rectangles forming the resulting complement.
     */
    public List<Rectangle> complementOf(Rectangle rectangle) {
        List<Rectangle> intersections = new ArrayList<>();

        if (rectangle.x2 > x1 && x2 > rectangle.x1 && rectangle.y2 > y1 && y2 > rectangle.y1) {
            if (rectangle.y1 <= y1) {
                intersections.add(new Rectangle(rectangle.x1, rectangle.y1, rectangle.x2, y1));
            }

            if (y2 <= rectangle.y2) {
                intersections.add(new Rectangle(rectangle.x1, y2, rectangle.x2, rectangle.y2));
            }

            if (rectangle.x1 <= x1) {
                intersections.add(new Rectangle(rectangle.x1, Math.max(y1, rectangle.y1), x1, Math.min(y2, rectangle.y2)));
            }

            if (x2 <= rectangle.x2) {
                intersections.add(new Rectangle(x2, Math.max(y1, rectangle.y1), rectangle.x2, Math.min(y2, rectangle.y2)));
            }
        }

        return intersections;
    }

    /**
     * Calculates area of this rectangle.
     *
     * @return area of this rectangle.
     */
    public int area() {
        return Math.abs((x1 - x2) * (y1 - y2));
    }

    /**
     * Checks if this rectangle contains the specified rectangle.
     *
     * @param rectangle rectangle to check for.
     * @return true if rectangle inside this, false otherwise.
     */
    public boolean contains(Rectangle rectangle) {
        return x1 <= rectangle.x1 && rectangle.x2 <= x2 && y1 <= rectangle.y1 && rectangle.y2 <= y2;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Rectangle)) {
            return false;
        }

        Rectangle other = (Rectangle) o;
        return x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2;
    }

    @Override
    public int hashCode() {
        int result = 17;

        result = 37 * result + x1;
        result = 37 * result + y1;
        result = 37 * result + x2;
        result = 37 * result + y2;

        return result;
    }

    @Override
    public String toString() {
        return String.format("Rectangle with x1: %s y1: %s x2: %s y2: %s", x1, y1, x2, y2);
    }
}

I have several questions/considerations:

Is the provided solution correct?
I assume the complexity of this algorithm is $O(n^2)$ . Can it be improved?
I’ve overridden toString(), equals() and hashCode() methods, although I’ve never called them (except toString() while debugging). Is it bad practise to do so?
I feel that comments in javadoc are lame. How can they be improved and are they necessary at all?
computeAreaFromFile() does 2 things: it reads file content and performs actual calculations. I think this method should be split, however I’m not sure how I could do this.

Question 2

The time for the approach you gave is in $O(n ^ 2)$ .

Dec. 10, 2018

Details about a possible solution

This is Klee’s measure problem for $d = 2$ .

Apparently, an optimal algorithm for this case exists and is called Bentley’s algorithm. Its running time is $O(n cdot log(n))$ . However, it seems that the 1977 paper that describes it is unavailable. It uses sweep-line approach and a dynamic 1-d segment tree.

We have $n$ axis-aligned rectangles. Our sweep-line moves across $x$ . We have events along $x$ that correspond to start of rectangle and end of rectangle. The intersection of the sweep-line with a collection of rectangles is essentially a 1-d measure problem. We have $2 cdot n$ events with at most $2 cdot n$ distinct x values. We use a 1-d segment tree that we maintain via inserts and deletes to give 1-d measure that we “pull” with delta- $x$ ‘s to give incremental contributions to 2-d measure. The costly operations are sort and insert/delete.

Higher dimensions are more difficult to handle. We might then be better served by using higher-dimensional segment tree with intersection queries or an R-tree variant with intersection queries. This would depend on which is larger — $d cdot log(n)$ or $log^{textrm{max}(d - 1, 1)}(n)$ for $d geq 1$ — the former being smaller may imply that R-tree is better; the latter (i.e. we note that this time is with fractional cascading) being smaller implies segment tree is better.

For more details, see the links.

References

Bentley – Algorithms for Klee’s rectangle problems (1977) — possibly unavailable
Elizarov – Finding missing range in multidimensional domain – Answer (2017)
https://cs.stackexchange.com/q/73819
Erickson – Klee’s measure problem (1998)
http://jeffe.cs.illinois.edu/open/klee.html
Chlebus – On the Klee’s measure problem in small dimensions (1998)

Question 3

Correctness

(See the update at the end.)

I don’t believe your algorithm is correct. Here is the way I would expect to see it solved:

Define a function rectDiff(r,s) which computes the difference of two rectangles r and s. It may return an empty list (if r is completely contained in s), a list of just r (if r is disjoint from s) or a list of two smaller rectangles r1, r2 representing the parts of r which do not intersect s. This is probably what your .complementsOf() method does.

Given this rectDiff function, I would compute the area like this:

Pseudo-code:

theRects = ...read rects from a file...

rectangles = []
totalArea = 0

for r in theRects:
  pieces = [r]
  for s in rectangles:
    pieces = takeAway(pieces, s)
  for t in pieces:
    totalArea += area(t)
  append r to rectangles

def takeAway(pieces, s):
  # pieces is a list of (disjoint) rects
  # s is a single rect
  # returns a new list of (disjoint) rects
  newPieces = []
  for t in pieces:
    append rectDiff(t,s) to newPieces
  return newPieces

The point is that when considering a new rectangle r you need to remove from r the overlap with all previous rectangles, and then you can add the area of the surviving complements to the total area.

Your code, however, adds the area of a complement right away to the total area.

Range trees

If you employ the ideas in this article, you can use range trees to write the code this way:

for r in theRectangles:
  let rlist = the list of rects in rectangles which overlap with r
  pieces = [r]
  for s in rlist:
    pieces = takeAway(pieces, s)
  ...
  add r to rectangles

The idea is that using a range tree rlist might be a lot smaller than the full list rectangles.

Update

Your algorithm is probably correct since you recursively call addRectangleArea() on each complement piece.

However, there is an inefficiency in the algorithm. Suppose:

rectangles = [ r1, r2, r3, ... ]

and we are processing a new rectangle r. Let

cs1 = rectDiff(r, r1) = complements of r compared to r1
    = [ c1, c2, ... ]

Your code calls addRectangleArea(c1) which then will compute rectDiff(c1, r1). However, this difference will always be empty. When considering c1 (or c2 or any rectangle in cs1) you can start with r2 in the rectangles list on the recursive call.

Leave a Reply Cancel reply