java how to merge multiple rectangles into one polygon

Question

I hope someone can help as 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 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 ie. 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 can calculate the coordinates of all four corners of each Rectangle ie. Top, Right, Bottom, Left ie. 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 not sure if I can apply this to my case - also its written in Python and not Java.

Merging multiple adjacent rectangles into one polygon

Answer 1

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());
    }

}