java - 将多边形合并为一个多边形

Question

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

此图片可以说明这一点：

如果有任何差距，是确定的，如果该算法将“补”的差距。

我搜索了很多，找不到什么好.. 我需要一个简单的算法，它并不一定是有效的.. 比方说，我们有7个矩形像从第二多边形例如图片。 好吧，如果我先将1与2合并，然后将我们的新多边形与3合并，依此类推，它不必那么快，因为最多会有50个矩形。

Answer 1

我真的很喜欢Dariusz的答案的效率。它可能是它符合你的所有要求，在这种情况下去吧。

但是，有一些问题想到。

如果合并后有多个形状会怎样？你如何检测这些形状是分开的还是嵌套的？就此而言，如果简单地给出一组边，就不容易判断它是否构成一个形状，或形状内留下的空隙。

例如，考虑下面的图合并相邻的方块后：

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

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

假设这是有关您的问题（可能不是），那么下面的算法可能更适合：

而不是抛出集中的所有矩形的所有边缘在一起之初，保持每个矩形在Polygon s的列表中分开。每个Polygon都有自己的一组边。

合并Polygon s在此列表中共享一个边缘，直到您剩下一组不同的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的List。

sharesEdge只是遍历每个Polygon的边缘，并看看它们是否有任何共同点。

merge完全按照Dariusz的回答 - 去除边缘对。

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

如果需要通过将嵌套形状吸收到较大形状中来处理嵌套形状（即填充填充空位），则会变得有点棘手。你首先要创建一条边的路径。如果边缘全部连接，则这是一个简单的形状，其边缘定义了边界。如果没有，那么应该有一个外部周边，以及一个或多个内部周边。忽略内周边并将形状解析为简单 - 即仅保留外周边的边缘。然后，循环形状，看看是否有任何形状在另一个里面。如果是这样，请将其删除。

Answer 2

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

• 创建矩形中所有边的列表。一个矩形有4条边。
• 让Edge成为具有正确定义的compareTo()和equals()的类别。
• 排序边缘列表（使用compareTo）。
• 遍历列表。如果TWICE列表中存在相同的边缘，则从列表中删除它们。
• 其余的边缘是你的多边形的边缘。