java-将渐进的矩形合并到一个多边形中 [英] java - merge adiacent rectangles into a polygon

问题描述

我有一组矩形，这些矩形具有相同的宽度和高度，并且总是相交的. 我知道所有顶点的位置，每个顶点只有4个(因为是正方形).

I have a set of rectangles that have the same width and height and are always adiacent. I know the position of all the vertices, each one having only 4. (because is a square).

此图片可以解释以下内容:

This image can explain this:

如果有任何空白，算法可以填充"空白就可以了.

If there are any gaps, is ok if the algorithm will 'fill' the gap.

我搜索了很多，但找不到任何好东西. 我需要一个简单的算法，它不必那么高效. 假设我们从图像中获得了第二个多边形示例中的7个矩形. 可以，如果我先将1与2合并，然后将我们的新多边形与3合并，依此类推，不必那么快，因为最多可以有50个矩形.

I searched a lot, and could not find anything good.. I need an simple algorithm, it doesn't have to be that efficient.. Let's say that we got 7 rectangles like in the second polygon example from the image. Is ok if I first merge 1 with 2, then merge our new polygon with 3, and so on, it doesn't have to be that fast, because there will be maximum 50 rectangles.

推荐答案

我真的很喜欢Dariusz回答的效率.可能是它满足了您的所有要求，在这种情况下，它就会随之而来.

I really l like the efficiency of Dariusz's answer. And it might be that it meets all your requirements, in which case go with it.

但是，我想到了一些问题.

However, there are a few problems that come to mind.

合并后如果有多个形状怎么办?如何检测这些形状是分开的还是嵌套的?因此，如果仅给您一组边缘，就很难分辨出它是构成形状还是形状内部留有空隙.

What if there are multiple shapes after merging? How can you detect if these shapes are separate, or nested? For that matter, if you are simply given a set of edges, it is not easy to tell if it constitutes a shape, or the void left inside a shape.

例如，合并相邻的正方形后，请考虑下图:

For example, consider the following diagram after merging adjacent squares:

+----------------+
|                |
| +------------+ |
| |            | |
| | +--------+ | |
| | |        | | |
| | |        | | |
| | +--------+ | |
| |            | |
| +------------+ |
|                |
+----------------+

这里确实有2种形状-另一种形状.但是，有3套连接的边.为了查看内部矩形是形状还是形状中的空隙，您必须从外部矩形开始并向内工作.这样做将导致您知道形状基本上是围绕另一个矩形的矩形的轮廓.但是，如果要去除外边缘，则最终的形状将只是空心矩形-一种形状.

Here there are really 2 shapes - 1 inside another. However, there are 3 sets of connected edges. In order to see if the inner rectangle is a shape or a void within a shape, you must start at the outer rectangle and work inwards. Doing so will result in knowing that the shape is basically an outline of a rectangle surrounding another rectangle. If you were to remove the outer edges, however, the resulting shape would simply be a hollow rectangle - one shape.

假设这与您的问题有关(可能与您的问题无关)，那么以下算法可能更合适:

Assuming this is relevant to your problem (it might not be), then the following algorithm may be more suitable:

不是将所有矩形的所有边的集合都放在开头，而是将每个矩形放在Polygon的列表中分开.每个Polygon都有自己的一组边.

Instead of throwing the set of all the edges of all the rectangles together at the beginning, keep each rectangle separate in a list of Polygons. Each Polygon has its own set of edges.

此列表中的合并Polygon共享一条边，直到您剩下一组不同的Polygon(即无法再进行合并)为止.

Merge Polygons in this list that share an edge until you are left with a set of distinct Polygons (i.e. no more merges can take place).

List<Polygon> plist;

// Populate the list with the polygons...

for (int i=0; i<plist.size(); i++) {
  Polygon p1 = plist.get(i);
  boolean distinct = false;
  while (!distinct) {
    distinct = true;
    for (int j=plist.size()-1 ; j>i; j--) {
      Polygon p2 = plist.get(j);
      if (p1.sharesEdge(p2)) {
        // Merge the two polygons
        p1.merge(p2);
        // One less shape
        plist.remove(j);
        distinct = false;
      } // if (p1.sharesEdge(p2))
    } // for (int j=plist.size()-1 ; j>i; j--) 
  } // while (!distinct)
} // for (int i=0; i<plist.size(); i++)

最后，您将在plist中有一个单独的Polygon列表.

At the end, you will have a list of separate Polygons in plist.

sharesEdge只是在每个Polygon的边缘上循环并查看它们是否有相同之处.

sharesEdge simply loops over the edges of each Polygon and sees if they have any in common.

merge的作用与Dariusz的答案完全相同-删除成对的边缘.

merge does exactly as Dariusz's answer - remove pairs of edges.

一些假设-所有初始多边形的边长均为单位长度.如果不正确，那么合并时可能需要拆分边缘，并使用更复杂的方法检查共享边缘.

Some assumptions - all initial polygons have edges of unit length. If this is not true, then you may need to split edges up when merging and have a more complicated method of checking for shared edges.

如果需要通过将嵌套形状吸收为更大的形状(即填充间隙)来处理嵌套形状，则它会有些棘手.您将从创建边缘的路径开始.如果所有边缘都连接在一起，则这是一个简单的形状，其边缘定义了周长.如果没有，则应该有一个外周边和一个或多个内周边.忽略内周边并将形状解析为简单的形状-即仅保留外周边的边缘.然后，在这些形状上循环，看看是否有任何一个形状在另一个形状之内.如果是这样，请将其删除.

If nested shapes need to be handled by absorbing them into the larger shape (i.e. filling the gaps), then it gets a little tricky. You'd start by creating a path of the edges. If the edges are all connected, then this is a simple shape where its edges define the perimeter. If not, then there should be one outer perimeter, and one or more inner perimeters. Ignore the inner perimeters and resolve the shape to to simple - i.e. only the edges in the outer perimeter are kept. Then, loop over the shapes and see if any of the shapes is inside the other. If so, remove it.

这篇关于java-将渐进的矩形合并到一个多边形中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！