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

Peroxy

Are you allowed to use the inbuilt APIs or this some kind school assignment? – Sherfield

which in-built APIs ? no this not a school assignment - this is part of a task I have to do for work. Why has the question been down voted already ?! – Peroxy

Because you are asking people to give you the answer instead of trying to code it yourself. – Hourihan

You can use Area to add shapes together. Assuming you're using something like java.awt.Rectangle, then you can wrap it in a Area and add it to another Area which represents the final state. You might also have a look java.awt.Rectangle, as it has a number of add methods as well – Sherfield

I have made several attempts at coding it myself and I was not happy with my solution - it didnt work correctly and I dont think it would form the basis of a solution so I decided to bin it and start again. I have read up an algorithm by Sedgewick but this seems overly complicated for my task. I was hoping to get some pointers into the right direction at least. – Peroxy

Thanks MadProgrammer. I did have a look at Rectangle Awt especially the Intersection method but this is just a boolean and I didnt really think it could help me. I will check-out the Area class to see how it works. I am not really using AWT - the Rectangle class I mentioned in my question above is my own defined class - as is the Point class mentioned and the Polygon. – Peroxy

I worked on a simpler problem to find the intersection of two rectangles, and I found it simplified things if I split it into multiple cases, considering what happened when one rectangle was completely to the left, right, top, bottom, containing lengthwise, containing height wise (and perhaps a few other cases) of the other. – Abamp

Will the Area method give me the points though ? My end goal is to produce a Polygon and print this in SVG file - so I need the list of Points in order to render this in SVG. – Peroxy

@David Choweller thanks. My first attempt was along these lines - but it produced some horrible code and didnt cover all my cases so I would like to look for a more robust solution. – Peroxy

I found that it helped my thinking process if I split the cases into multiple methods and named them in very intuitive ways, instead of putting all the messy calculations in one big method. – Abamp

It seems like the rectangles in the diagram are missing a case that could complicate things: when you have 3 rectangles that all intersect each other. Maybe this is an indication that you can handle the cases two rectangles at a time. – Abamp

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

}

Peroxy

Thank you, your codes works well in my electon project – Nadabus

Thank you. It saved my day. 🙌 – Woodchuck

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.

Terat

This is so much cleaner than the accepted solution! Thanks! – Nippers

Answer 3

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://mcmap.net/q/1463720/-how-to-merge-multiple-rectangles-into-one-polygon is a good solution, this was developed to convert pixels into an area where there can be millions of rectangles.

Mutinous

Is it ok to have disconnected shapes in a Path2D? It has an iterator, how does it iterate if there is a disconnect? – Terat

@KyleBerezin Why not? There is a move method when creating a path 2D. You can look at the PathIterator class and see the details. Essentially you get the coordinates for each point, and it tells you how those coordinates are incorporated into the class. For example, it might be a PathIterator.SEG_MOVETO I'm not sure I understand your question. – Mutinous

Very interesting. I always thought Path2D had to be continuous. I'm going to have to look into it more. – Terat