Calculate the area of rectangles union

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

• Program parameters should be validated

• Input file format should be validated.

Examples:

Input:

1 1 7 7

Output:

36

Input:

1 1 3 3  
2 2 4 4

Output:

7

My solution:

```
public class Main {

private List rectangles = new ArrayList<>();

public static void main(String[] args) {
if (args.length != 2) {
throw new IllegalArgumentException("Invalid arguments number\nProgram 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");
}

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)

StackExchange Code Review Q#104258, answer score: 4