How to merge two rectangles given arrays of their coordinates?

Question

Say I have two arrays of coordinates (x,y) of two rectangles, for example [(0, 0), (0, 1), (2, 1), (2, 0)] and [(1, 0), (1, 2), (3, 2), (3, 0)], how would I merge these two coordinate arrays into one array that represents the resulting polygon?

It might look like this, graphically:

   _ _
 _|_  |
|_|_|_|

to

   _ _
 _|   |
|_ _ _|

with resulting array [(0, 0), (0, 1), (1, 1), (1, 2), (3, 2), (3, 0)].

I'm trying to design some sort of merge algorithm but I'm not sure where to get started.

For input, there will be two arrays, and this method will return one merged array.

I'm just totally lost on where to start.

Answer 1

As a pointer maybe consider the following:

I am assuming that each array (r1 and r2) is constructed the same way as in: [(bottom left) (top left) (top right) (top left)]

If there is any overlap of the rectangles (bodies and not just corners) then the result could be between four to twelve different coordinates inside your new array.

We first check which pair is the furthest left, if there is one we add it to the new array. Comparing r1's bottom left's X coordinate to r2's bottom left's X coordinate should be enough. If NOT and both rectangle's left side is on the same X coordinate we add the bottom left one with the lower Y value and the top left one with the bigger Y value. This logic can be applied to all four sides.

In the case we have e.g. a furthest left side we still need to check whether the lesser left side overlaps to the top or bottom. We do this by by simply subtracting top left r1's Y from top left r2's Y value. If there is a difference (aka the lesser left side is higher, we add the R2 top left coordinates to the array together with (r2 X's, r1 Y's). A similar logic needs to be applied for all sides in case there is a more extreme side.

So a general flow for this would be to

1. Check for the most outer edges. These can be added without any changes. A simple one-coordinate comparison should be enough for that. If there is an outer edge follow see (2) else see (3)
2. Check whether the NOT most outer edge is longer into the other direction. So for example in case for the left check, assume r1 is further left. Check whether the r2's top left is higher than r1's top left. If this is the case add r2's top left together with a new coordinate that is (r2 top left x | r1 top left Y). Keep in mind that for example in this situation r2's leftist edge could be both: overarching to the top and overarching to the bottom!
3. Since both edges are on the same level (e.g. same X value) we need to see which is e.g. bottom left is further down, take it and add it together with the top left that is further up.

Answer 2

(Never hurts to order things (but here it might not help): order the points in positive rotation, say starting from left-upper edge.)

For a merge (a.topx .. a.bottomx) and (b.topx .. b.bottomx) must overlap, same for y.

The outer rect is outer.topx = min(a.topx, b.topx) and so on.

X-coordinates, possibly incidental, are outer.topx, a.topx, b.topx, outer.bottom.x. Now you find one border of the polygon. And so on.

The connecting inner edges are trivial.

Mind that there are many forms, but the generalized one is:

...._____.....
:___|    |___:
|___      ___|
:...|____|...:

Whether you might desire a more general algorithm to merge any polygon is the question, as adding a third rectangle will become an entirely different case.

Answer 3

First, make sure that the bottom-left corner of the first rectange isn't inside the other rectange. If it is, swap them. The corners can overlap or the corner can be on a side of the other rectange, it is fine.

Then, start walking alongside the left rectange counter clock wise, so to the right on the bottom side. check if you will end because you:

1. reach the end first
2. hit the left wall of the other rectangle first

If you reach the end, continue walking up on the right edge of the first rectange. If you hit the other rectange, walk down on the left wall of the other rectangle.

Repeat until you hot the left-bottom corner of the first rectangle again. At each point you need to remember: which way you are going / on which side are you going (since you always travel counter clock wise, one can easily be computed from the other) and what rectange are you on.

If you don't hit the other rectange at all on your walk, it means that the rectanges eigter don't touch, or the second rectangle is inside the first one.

Make sure do think through the ineualities that you will use, example:

 ______
|  |_| |
|      |
|______|

Should these 2 ractangle merge as one, or a 6-polygon with 3 lines in a straight line? Or should this:

 _
|_|_
  |_|

Be 2 diferent rectangles, or 1 8-polygon with 2 same points?

Answer 4

There are many degrees of freedom regaring the approaches and actual implementation here. Some relevant questions to consider, just from the tip of my head:

• Are the coordinates always integers?
• Are the input shapes always (axis-aligned) rectangles?
• Do the rectangles always overlap?
• Are the points always at different coordinates?
• Are the edges never equal?
• ...

In some cases (if the first three questions are answered with "Yes"), you could probably go for a technically very simple approach: Just consider the whole input as a "grid", where the rectanges define the grid cells that are "filled", and in the end, return the border of the filled area.

If the answer to one of them may be "No", then you're opening a can of worms, with many, many subtleties.

Fortunately, the people at Sun/Oracle have worked this out pretty well, and there may still be a simple solution even for very complex problems: You can convert the input into shapes, and then use the Area#add method to compute the merged shape.

This is implemented in this example. But note that this is not very efficient, compared to, say, the grid-based approach that could be used for simpler cases. And it still leaves the question open about what should happen for non-overlapping rectangles. However, at least for the given inputs, the result is the expected one:

import java.awt.Point;
import java.awt.Shape;
import java.awt.geom.Area;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RectangleMerge {

    public static void main(String[] args) {
        List<Point2D> pointsA = Arrays.asList(new Point(0, 0), new Point(0, 1), new Point(2, 1), new Point(2, 0));
        List<Point2D> pointsB = Arrays.asList(new Point(1, 0), new Point(1, 2), new Point(3, 2), new Point(3, 0));

        System.out.println(merge(pointsA, pointsB));
    }

    private static List<Point2D> merge(List<? extends Point2D> pointsA, List<? extends Point2D> pointsB) {
        Area aa = new Area(toShape(pointsA));
        aa.add(new Area(toShape(pointsB)));
        return toPoints(aa);
    }

    private static Shape toShape(List<? extends Point2D> points) {
        Path2D path = new Path2D.Double();
        for (int i = 0; i < points.size(); i++) {
            Point2D p = points.get(i);
            if (i == 0) {
                path.moveTo(p.getX(), p.getY());
            } else {
                path.lineTo(p.getX(), p.getY());
            }
        }
        path.closePath();
        return path;
    }

    private static List<Point2D> toPoints(Shape shape) {
        List<Point2D> result = new ArrayList<Point2D>();
        PathIterator pi = shape.getPathIterator(null, 0.0);
        double[] coords = new double[6];
        while (!pi.isDone()) {
            int segment = pi.currentSegment(coords);
            switch (segment) {
            case PathIterator.SEG_MOVETO:
            case PathIterator.SEG_LINETO:
                result.add(new Point2D.Double(coords[0], coords[1]));
                break;
            }
            pi.next();
        }
        return result;
    }

}