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

Question

我在工作中正在努力完成这部分任务。我故意不详细说明工作任务的背景，以尽量将注意力集中在问题上。我必须将矩形合并为单个多边形，如附图所示，但我需要点列表，以便我可以将它们写入 Swing 画布的多边形形状（DOM 对象），然后导出 SVG。

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

我有一个

List<Rectangle> rectangles

并且想要一种算法，可以将此列表转换为单个多边形（

List<Points>

，其中一个点代表每个点的坐标（x，y），如标记为红色“x”的图表所示.

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

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

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

}

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

并迭代顶点。

Answer 3

在查看类似问题后，我发现 java awt 解决方案的实现速度明显更快。

Path2D path = new Path2D.Double();

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

最后，创建一个区域以消除重叠的线条。

Area a = new Area(path);

对于几个矩形，https://stackoverflow.com/a/73535402/2067492是一个很好的解决方案，开发它是为了将像素转换为可以有数百万个矩形的区域。