如何将多个矩形合并成一个多边形

Question

我在工作中遇到了这个问题。为了便于关注问题，我故意没有详细说明工作任务的背景。 我需要将矩形合并成单个多边形，如附图所示，但是我需要点的列表，以便我可以将其写入Swing画布的多边形形状(DOM对象)，然后导出到SVG。

我知道每个矩形的起点，即左上角的x和y坐标（float x，float y），以及每个矩形的宽度（float）和高度（float），因此我可以计算出每个矩形的所有四个角的坐标，即顶部、右侧、底部、左侧，即顶部=原点=x，y，右侧=x+宽度，底部=x+宽度，y+高度和左侧=x，y+高度。

我有一个List<Rectangle>，希望有一个算法将此列表转换为单个多边形（List<Points>，其中一个点表示如红色“x”所示的每个点的坐标（x，y）。

然后，我将使用这个点列表在DOM中写出一个元素，最终在SVG中打印网页。因此，我的最终结果必须是一系列点（即用于构造SVG中多边形形状的x，y坐标）。

我看到了这个类似的答案，但是我不确定是否可以应用到我的情况中 - 而且它是用Python编写的，而不是Java: 将多个相邻的矩形合并为一个多边形

- robbie70

---

你可以使用内置的API吗？还是这是某种学校作业？ - MadProgrammer

你可以使用 Area 将形状组合在一起。假设你正在使用类似 java.awt.Rectangle 的东西，那么你可以将其包装在一个 Area 中，并将其添加到另一个代表最终状态的 Area 中。你也可以查看 java.awt.Rectangle，因为它有许多 add 方法。 - MadProgrammer

我曾经尝试过自己编写代码，但是我对自己的解决方案并不满意——它不能正确地工作，而且我认为它也不能成为一个解决方案的基础，所以我决定放弃并重新开始。我已经阅读了Sedgewick的算法，但这似乎对我的任务过于复杂。我希望至少能得到一些指引。 - robbie70

感谢MadProgrammer。我确实看了一下Awt中的Rectangle，特别是Intersection方法，但这只是一个布尔值，我真的不认为它能帮助我。我会查看Area类来了解它的工作原理。我并没有真正使用AWT - 我在我的问题中提到的Rectangle类是我自己定义的类 - 同样的情况也适用于Point类和Polygon。 - robbie70

我曾经处理过一个更简单的问题，即查找两个矩形的交集。我发现将其分成多个情况会使事情变得简单，考虑当一个矩形完全在左侧、右侧、顶部、底部、包含另一个矩形的长度或高度（以及其他一些情况）时会发生什么。 - David Choweller

Answer 1

这是我和我的同事想出来的一个解决方案。希望它能帮助其他人。

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

}

- robbie70

---

谢谢，您的代码在我的Electron项目中运行良好。 - Sherali Turdiyev

谢谢。它救了我的一天。 - Cüneyt

Answer 2

您可以使用Java的Area类更简单地完成此操作。

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

从那里，您可以根据需要测试交集和区域包含关系。如果您想将其转换为多边形或绘制结果，请获取area.getPathIterator(null);并迭代顶点。

- Kyle Berezin

---

这比已接受的解决方案干净多了！谢谢！ - tresf