Java - 合并相邻的矩形成为一个多边形

Question

我有一组矩形，它们具有相同的宽度和高度，并且始终相邻。 我知道所有顶点的位置，每个顶点只有4个。（因为是正方形）。

这张图片可以解释这个问题：

如果有任何间隙，算法将“填补”间隙也可以。

我搜索了很多，但没有找到什么好的方法。 我需要一个简单的算法，它不必非常高效。 假设我们获得了像图像中第二个多边形示例中的7个矩形。 如果我先将1与2合并，然后将我们的新多边形与3合并，以此类推，这样就可以了，因为最多只有50个矩形。

- Boldijar Paul

---

似乎是简单的计算，判断顶点是否包含在较大的形状内。我会先寻找外部顶点，然后确认哪些边缘可以被消除。 - MaineCoder

抱歉，我无法理解您的回答... - Boldijar Paul

我删除了我的回答，因为凸包算法似乎有些过头了（而且你也不想要一个凸多边形）。 - user2314737

“填补空缺”是否意味着在您的第三个示例中，可以移除形状中间的孔？ - Trenin

可能还想看一下Area类。 - Brad Mace

Answer 1

由于您的形状仅由矩形组成，并且它们始终相邻，因此进行合并的算法要比没有这些假设要简单得多。

• 创建一个包含所有矩形边缘的列表。一个矩形有4条边。
• 让Edge成为一个类，并正确定义compareTo()和equals()方法。
• 对边缘列表进行排序(使用compareTo)。
• 遍历列表，如果同一条边在列表中出现两次，则将它们都从列表中删除。
• 剩下的边是您的多边形的边缘。

- Dariusz

---

这正是我即将发布的内容。简单而快速。 - Michał Rybak

@Dariusz 你能保证最终只得到一个多边形吗？如果矩形集合是不连通的，合并后会得到2个或更多个分离的矩形怎么办？这个算法仍然有效，但OP可能想知道剩下了多少个多边形，在这个算法之后，很难说。 - Trenin

@Dariusz 如果有多个嵌套形状怎么办？我正在尝试查看如何检测和解决嵌套形状，这并不是一件简单的事情。 - Trenin

这些是矩形，我们有非常具体的输入数据。嵌套的形状总是完全嵌套或者完全不嵌套。因此检测很简单 - 例如，检查一个形状的单个顶点是否在另一个形状内部。 - Dariusz

合并相邻的矩形后，您将不再拥有简单的矩形。考虑一组像放大数字“6”中的像素一样排列的正方形。我认为检测封闭部分内是否存在嵌套形状并不是微不足道的，而不是凸集中的其他区域，这将是第二个形状。 - Trenin

Answer 2

我非常喜欢Dariusz的回答的高效率。如果它符合你的所有要求，那么你可以选择它。

然而，有一些问题需要考虑。

如果在合并后出现多个形状怎么办？如何检测这些形状是分开的还是嵌套的？同样，如果你只是给出一组边缘，很难确定它构成了一个形状还是留下了一个形状内部的空洞。

例如，在合并相邻正方形之后，请考虑以下图示：

##################
##################
##################
###            ###
###  ########  ###
###  ########  ###
###  ########  ###
###  ########  ###
###            ###
##################
##################
##################

这里有两个形状，内部一个包含在外部一个中。然而，有三组相连的边缘。为了确定内部矩形是形状还是外部形状中的空洞，您必须从外部矩形开始向内工作。这样做将使您知道该形状基本上是围绕另一个矩形的矩形轮廓。但是，如果移除外部边缘，则得到的形状将仅为一个空心矩形-一个形状。

假设这与您的问题相关（可能不是），则以下算法可能更合适：

而不是在开始时将所有矩形的所有边缘集合在一起，将每个矩形保持在Polygon列表中。每个Polygon都有自己的边缘集。

合并此列表中共享边缘的Polygon，直到剩下一组不同的Polygon（即不能再进行合并）。

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 列表。 sharesEdge 只是循环遍历每个 Polygon 的边缘，看它们是否有任何共同点。 merge 完全按照Dariusz的答案执行-删除成对的边缘。

一些假设-所有初始多边形都具有单位长度的边缘。如果不是这样，则在合并时可能需要拆分边缘，并且需要更复杂的方法来检查共享的边缘。

如果需要通过将嵌套形状吸收到较大的形状中（即“填补间隙”）来处理嵌套形状，则会变得有些棘手。您将首先创建一个边缘路径。如果边缘都连接起来，则这是一个简单的形状，其边缘定义了周长。否则，应该有一个外围周长和一个或多个内围周长。忽略内部周长并将形状解析为简单形式-即仅保留外部周长中的边缘。然后，循环遍历形状，并看看其中是否有任何形状在另一个形状中。如果是，则将其移除。

- Trenin

---

@Paul 在你的代码中，你正在删除列表noduri的成员，但仍在循环遍历它们。如果不改变循环方式，就不能修改列表的成员。 - Trenin

@Paul 另外，删除顶点对并不能保证能够成功。如果两个正方形仅共享一个角而没有共享边，则它们无法合并。 - Trenin

看这张照片，我想解释的有错吗？http://postimg.org/image/of8u14ujf/ 请告诉我应该如何修改我的代码，记住我有一个具有x和y位置而不是边缘的顶点列表。 - Boldijar Paul

@Paul 如果你想要像图片中那样的一个多边形，那么你不能移除那个顶点。如果没有那个顶点，你最终会得到连接剩余顶点的角度。你能用你的代码表达出所需的多边形吗？如果可以的话，我会用单个顶点替换成对的顶点。 - Trenin

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/44795/discussion-between-paul-and-trenin - Boldijar Paul