Algorithm for finding area of all rectangles
Lets say we get rectangles in form of 4 points: their (x1, y1), ..., (x4, y4) We want to calculate the total area they cover. We want to count the total area, if more rectangles overlap, we count this area only once.
I'm not really looking for finished solution, pseudocode or some links to algorithms and data structures useful here would be appreciated.
the form of rectangles is: given by three integers: left position, right position and height. for example:
L:0 R:2 H:2
L:1 R:3 H:3
L:-1 R:4 H:1
total area would be: 10
the max value for x axis is from -1e9 to 1e9, starts at x=L and ends at x=R y cannot be lower than 0 and always starts at y=0 and ends at y=H
Let's assume that your rectangles have integer coordinates in a very small range, say 0 to 10. Then an easy approach is to create a grid and paint the rectangles onto it:
The occupied "pixels" could be stored in a set or they could be set bits in a bitmap. When rectangles overlap, the intersection is just marked as occupied again and so contributes only once the the area. The area is the number of occupied cells.
For large dimensions, the data structures would become too big. Also, painting a rectangle that is several million pixels wide would be slow.
But the technique can still be applied when we use compressed coordinates. Your grid then has only the coordinates that are actual coordinates of the rectangles. The cells have variable widths and heights. The number of cells depends on the number of rectangles, but it is independent of the minimum and maximum coordinates:
The algorithm would look like this:
- Find all unique x coordinates. Sort them in ascending order and store (coordinate, index) pairs in a dictionary for easy look-up.
- Do the same for the y coordinates.
- Paint the rectangles: Find the indices of x and y ranges and occupy the cells between them.
- Calculate the area by summing the area of all occupied cells.
These rectangles have their base at y=0? I'm assuming that's true. So these are like buildings in a city viewed from a distance. You're trying to trace the skyline.
Store the rectangles in one array so you can use the array indices as unique IDs. Represent each left and right rectangle edge as an "event" that includes the ID for the rectangle it belongs to and the x-coordinate of the corresponding edge. Put all the events in a list EL and sort by x-coordinate. Finally you'll need dynamically a sorted set (e.g. a Java TreeSet) of rectangle IDs sorted by corresponding rectangle height descending. It's called SL, the "sweep line". Due the way it's sorted, SL.first is always the ID of the highest rectangle currently referenced by the SL.
Now you can draw the outline of the collection of rectangles as follows:
SL = <empty> // sweep line x0 = EL.first.left // leftmost x among all rectangle edges lastX = x0 for each event E in EL // process events left-to-right Let y0 = if SL.isEmpty then 0 else SL.first.height // current y if E.ID in SL // event in SL means sweep line is at rectangle's right edge remove E.ID from SL else // event means sweep line is a new rectangle's left edge add E.ID to SL Let y1 = if SL.isEmpty then 0 else SL.first.height // new y if y1 != y0 output line seg (lastX, y0) -> (E.x, y0) output line seg (E.x, y0) -> (E.x, y1) lastX = E.x output final line seg (lastX, 0) -> (x0, 0)
Because this sounds like homework or maybe an interview question, I'll let you revise this algorithm to provide the area of the swept-out shape rather than drawing its edge.