How to merge multiple rectangles into one polygon

Question

I am struggling with this part of my task at work. I've deliberately not detailed the context of the work task to try and keep the focus on the problem. I have to merge rectangles into a single polygon as shown in the attached image, but I need the list of points so that I can write these out into Polygon shape (DOM object) for a Swing canvas and then SVG export.

I know the origin of each rectangle, i.e. the upper left x and y coordinates (float x, float y) and also the width (float) and height (float) of each rectangle, so from this I can calculate the coordinates of all four corners of each rectangle, i.e. top, right, bottom, left, i.e. top = origin = x, y, right = x + width, bottom = x + width, y + height and left = x, y + height.

I have a List<Rectangle> rectangles and would like an algorithm which will translate this list into a single polygon (List<Points> where a point represents the coordinates (x, y) of each point as shown in the diagram marked red "x"s.

I will then use this list of points to write out an element in the DOM for printing a web page eventually in SVG. So, my end result has to be a list of points (i.e. x,y coordinates for constructing a polygon shape in SVG).

I did see this answer which does something similar, but I'm not sure if I can apply this to my case - also it's written in Python and not Java: Merging multiple adjacent rectangles into one polygon

Answer 1

After looking at a similar problem, I found a significantly faster implementation of the java awt solution.

Path2D path = new Path2D.Double();

path.append(rect1, false);
path.append(rect2, false);

Finally, create an area to get rid of the overlapping lines.

Area a = new Area(path);

For a couple rectangles the https://stackoverflow.com/a/73535402/2067492 is a good solution, this was developed to convert pixels into an area where there can be millions of rectangles.

Answer 2

You can do this much more simply by using Java's Area class

    Area area = new Area();
    area.add(new Area(rect1));
    area.add(new Area(rect2));
    area.add(new Area(rect3));

From there you can test for intersectons and area.contains as needed. If you want to convert it into a polygon or draw the result, grab the area.getPathIterator(null); and iterate over the vertexes.

Answer 3

Here is a solution my colleague and I came up with. Hope it can help someone else.

public class PolygonHelper {

    public Polygon makePolygon(List<Rectangle> rectangles){
        List<Point> points = calcPoints(rectangles);
        return new Polygon(points);
    }

    private List<Point> calcPoints(List<Rectangle> rectangles) {
        List<Point> ret = new ArrayList<>();

        List<Float> yCoords = new ArrayList<>(getAllYCoords(rectangles));
        yCoords.sort(Comparator.naturalOrder());

        float previousLeftCoord = 0;
        float previousRightCoord = 0;

        for(float yCoord : yCoords) {
            System.out.println("Considering yCoords "+ yCoord);
            float minimumXLeftCoord = minXLeftCoord(yCoord, rectangles);
            float maximumXRightCoord = maxXRightCoord(yCoord, rectangles);
            System.out.println("min X: "+minimumXLeftCoord);
            System.out.println("max X: "+maximumXRightCoord);

            if(yCoord == yCoords.get(0)) {
                ret.add(new Point(minimumXLeftCoord, yCoord));
                ret.add(new Point(maximumXRightCoord, yCoord));

            } else {

                if(minimumXLeftCoord!=previousLeftCoord) {
                    ret.add(0, new Point(previousLeftCoord, yCoord));
                    ret.add(0, new Point(minimumXLeftCoord, yCoord));
                } else {
                    ret.add(0, new Point(minimumXLeftCoord, yCoord));
                }

                if(maximumXRightCoord!=previousRightCoord) {
                    ret.add(new Point(previousRightCoord, yCoord));
                    ret.add(new Point(maximumXRightCoord, yCoord));
                } else {
                    ret.add(new Point(maximumXRightCoord, yCoord));
                }

            }

            previousLeftCoord = minimumXLeftCoord;
            previousRightCoord = maximumXRightCoord;
            System.out.println(ret);
        }

        return ret;

    }

    private Set<Float> getAllYCoords(List<Rectangle> rectangles) {
        List<Float> allBottomYCoords = rectangles.stream().map(rectangle -> rectangle.getBottom().getY()).collect(Collectors.toList());
        List<Float> allTopYCoords = rectangles.stream().map(rectangle -> rectangle.getTop().getY()).collect(Collectors.toList());

        Set<Float> allCoords = new HashSet<>();
        allCoords.addAll(allTopYCoords);
        allCoords.addAll(allBottomYCoords);
        return allCoords;
    }

    private float minXLeftCoord(Float y, List<Rectangle> rectangles) {
        return rectanglesAtY(y, rectangles).stream().map(rect -> rect.getLeft().getX()).min(Comparator.naturalOrder()).get();
    }

    private float maxXRightCoord(Float y, List<Rectangle> rectangles) {
        return rectanglesAtY(y, rectangles).stream().map(rect -> rect.getRight().getX()).max(Comparator.naturalOrder()).get();
    }

    private List<Rectangle> rectanglesAtY(Float y, List<Rectangle> rectangles) {
        List<Rectangle> rectsAtYExcBottomLines = rectsAtYExcBottomLines(y, rectangles);

        if(rectsAtYExcBottomLines.size()>0) {
            // there are rectangles that are not closing here, so ignore those that are closing.
            return rectsAtYExcBottomLines;
        } else {
            // there are only rectangle bottom lines so we need to consider them.
            return rectsAtYIncBottomLines(y, rectangles);
        }
    }

    private List<Rectangle> rectsAtYExcBottomLines(Float y, List<Rectangle> rectangles) {
        return rectangles.stream()
                .filter(rect -> rect.getTop().getY()<=y && rect.getBottom().getY()>y).collect(Collectors.toList());
    }

    private List<Rectangle> rectsAtYIncBottomLines(Float y, List<Rectangle> rectangles) {
        return rectangles.stream()
                .filter(rect -> rect.getTop().getY()<=y && rect.getBottom().getY()==y).collect(Collectors.toList());
    }

}