algorithm to calculate perimeter of unioned rectangles

Question

I'm trying to calculate the perimeter of the union of a n rectangles, of which I have the bottom left and top right points. Every rectangle sits on the x axis (bottom left corner of every rectangle is (x, 0)). I've been looking into different ways of doing this and it seems like the Sweep-Line algorithm is the best approach. I've looked at Graham Scan as well. I'm aiming for an O(n log n) algorithm. Honestly though I am lost in how to proceed, and I'm hoping someone here can do their best to dumb it down for me and try to help me understand exactly how to accomplish this.

Some things I've gathered from the research I've done:

We'll need to sort the points (I'm not sure the criteria in which we are sorting them).

We will be dividing and conquering something (to achieve the O (log n)).

We'll need to calculate intersections (What's the best way to do this?)

We'll need some sort of data structure to hold the points (Binary tree perhaps?)

I'll ultimately be implementing this algorithm in Java.

Answer 1

The algorithm is a lot of fiddly case analysis. Not super complicated, but difficult to get completely correct.

Say all the rectangles are stored in an array A by lower left and upper right corner (x0, y0, x1, y1). So we can represent any edge of a rectangle as a pair (e, i) where e \in {L, R, T, B} for left, right, top, and bottom edge and i denotes A[i]. Put all pairs (L, i) in a start list S and sort it on A[i].x0.

We'll also need a scan line C, which is a BST of triples (T, i, d) for top edges and (B, i, d) for bottom. Here i is a rectangle index, and d is an integer depth, described below. The key for the BST is the edges' y coordinates. Initially it's empty.

Note that at any time you can traverse C in order and determine which portions of the sweep line are hidden by a rectangle and not. Do this by keeping a depth counter, initially zero. From least y to greatest, when you encounter a bottom edge, add 1 to the counter. When you see a top edge, decrement 1. For regions where the counter is zero, the scan line is visible. Else it's hidden by a rectangle.

Now you never actually do that entire traversal. Rather you can be efficient by maintaining the depths incrementally. The d element of each triple in C is the depth of the region above it. (The region below the first edge in C is always of depth 0.)

Finally we need an output register P. It stores a set of polylines (doubly linked lists of edges are convenient for this) and allows queries of the form "Give me all the polylines whose ends' y coordinates fall in the range [y0..y1]. It's a property of the algorithm that these polylines always have two horizontal edges crossing the scan line as their ends, and all other edges are left of the scan line. Also, no two polylines intersect. They're segments of the output polygon "under construction." Note the output polygon may be non-simple, consisting of multiple "loops" and "holes." Another BST will do for P. It is also initially empty.

Now the algorithm looks roughly like this. I'm not going to steal all the fun of figuring out the details.

 while there are still edges in S
   Let V = leftmost vertical edge taken from S
   Determine Vv, the intersection of V with the visible parts of C
   if V is of the form (L, i) // a left edge
     Update P with Vv (polylines may be added or joined)
     add (R, i) to S
     add (T, i) and (B, i) to C, incrementing depths as needed
   else // V is of the form (R, i) // a right edge
     Update P with Vv (polylines may be removed or joined)
     remove (T, i) and (B, i) from C, decrementing depths as needed

As P is updated, you'll generate the complex polygon. The rightmost edge should close the last loop.

Finally, be aware that coincident edges can create some tricky special cases. When you run into those, post again, and we can discuss.

The run time for the sort is of course O(n log n), but the cost of updating the scan line depends on how many polygons can overlap: O(n) for degenerate cases or O(n^2) for the whole computation.

Good luck. I've implemented this algorithm (years ago) and a few others similar. They're tremendous exercises in rigorous logical case analysis. Extremely frustrating, but also rewarding when you win through.

Answer 2

The trick is to first find the max height at every segment along the x axis (see the picture above). Once you know this, then the perimeter is easy:

NOTE: I haven't tested the code so there might be typos.

// Calculate perimeter given the maxY at each line segment.
double calcPerimeter(List<Double> X, List<Double> maxY) {
    double perimeter = 0;

    for(int i = 1; i < X.size(); i++){
        // Add the left side of the rect, maxY[0] == 0
        perimeter += Math.abs(maxY.get(i) - maxY.get(i - 1))

        // add the top of the rect
        perimeter += X.get(i) - X.get(i-1);
    }

    // Add the right side and return total perimeter
    return perimeter + maxY.get(maxY.size() - 1);
}

Putting it all together, you will need to first calculate X and maxY. The full code will look something like this:

double calcUnionPerimeter(Set<Rect> rects){
    // list of x points, with reference to Rect
    List<Entry<Double, Rect>> orderedList = new ArrayList<>();

    // create list of all x points
    for(Rect rect : rects){
        orderedList.add(new Entry(rect.getX(), rect));
        orderedList.add(new Entry(rect.getX() + rect.getW(), rect));
    }

    // sort list by x points 
    Collections.sort(orderedList, new Comparator<Entry<Double,Rect>>(){
        @Override int compare(Entry<Double, Rect> p1, Entry<Double, Rect> p2) {
            return Double.compare(p1.getKey(), p2.getKey());
        }
    });

    // Max PriorityQueue based on Rect height
    Queue<Rect> maxQ = new PriorityQueue<>(orderedList, new Comparator<Rect>(){
        @Override int compare(Rect r1, Rect r2) {
            return Double.compare(r1.getH(), r2.getH());
        }
    }

    List<Double> X = new ArrayList<>();
    List<Double> maxY = new ArrayList<>();

    // loop through list, building up X and maxY
    for(Entry<Double, Rect> e : orderedList) {
        double x = e.getKey();
        double rect = e.getValue();
        double isRightEdge = x.equals(rect.getX() + rect.getW());

        X.add(x);
        maxY.add(maxQ.isEmpty() ? 0 : maxQ.peek().getY());

        if(isRightEdge){ 
            maxQ.dequeue(rect);   // remove rect from queue
        } else {         
            maxQ.enqueue(rect);   // add rect to queue
        }
    }

    return calcPerimeter(X, maxY);
}