java – 将adiacent矩形合并为多边形
我有一组具有相同宽度和高度的矩形，并且始终是adiacent。 我知道所有顶点的位置，每个顶点只有4个（因为是正方形）。
这张图片可以解释这个： 
如果有任何差距，如果算法将“填补”差距，则可以。
我搜索了很多，找不到任何好的东西。我需要一个简单的算法，它不一定非常有效。让我们说我们得到了7个矩形，就像图像中的第二个多边形示例一样。 如果我首先将1与2合并，然后将我们的新多边形与3合并，那么就可以了，依此类推，它不必那么快，因为最多会有50个矩形。
我真的很喜欢Dariusz答案的效率。 它可能会满足您的所有要求，在这种情况下也可以使用它。
但是，有一些问题浮现在脑海中。
如果合并后有多个形状怎么办？ 如何检测这些形状是分开的还是嵌套的？ 就此而言，如果简单地给出一组边缘，则不容易判断它是否构成形状，或者是否留在形状内部。
例如，在合并相邻方块后请考虑以下图表：
+----------------+ | | | +------------+ | | | | | | | +--------+ | | | | | | | | | | | | | | | | +--------+ | | | | | | | +------------+ | | | +----------------+ 这里有两个形状 – 一个在另一个里面。 但是，有3组连接边。 为了查看内部矩形是形状还是形状中的空白，您必须从外部矩形开始向内工作。 这样做将导致知道形状基本上是围绕另一个矩形的矩形的轮廓。 但是，如果要移除外边缘，则生成的形状将只是一个空心矩形 – 一个形状。
假设这与您的问题相关（可能不是），则以下算法可能更合适：
而不是在开头将所有矩形的所有边缘的集合放在一起，而是将每个矩形分开在Polygon列表中。 每个Polygon都有自己的一组边。
合并Polygon在此列表中共享边缘，直到您留下一组不同的Polygon （即不再进行合并）。
List plist; // Populate the list with the polygons... for (int i=0; ii; 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
最后，您将获得一个单独的Polygon s列表。
sharesEdge只是循环遍历每个Polygon的边缘， sharesEdge它们是否有任何共同之处。
merge与Dariusz的答案完全相同 - 删除边缘对。
一些假设 - 所有初始多边形都具有单位长度的边。 如果不是这样，那么在合并时可能需要拆分边缘，并且有更复杂的方法来检查共享边。
如果需要通过将嵌套形状吸收到更大的形状（即填充间隙 ）来处理嵌套形状，那么它会变得有点棘手。 您首先要创建边的路径。 如果边缘全部连接，则这是一个简单的形状，其边缘定义周长。 如果没有，那么应该有一个外周边和一个或多个内周边。 忽略内周边并将形状解析为简单 - 即仅保留外周边的边缘。 然后，在形状上循环，看看是否有任何形状在另一个内部。 如果是这样，请将其删除。
因为您的形状仅由矩形组成且它们始终相邻，所以合并算法比没有这些假设的算法简单得多。
- 从矩形创建所有边的列表。 一个矩形有4条边。
- 让
Edge成为一个具有正确定义的compareTo()和equals()。 - 对边列表进行排序（使用
compareTo）。 - 遍历列表。 如果列表TWICE中存在相同的边缘，请从列表中删除它们。
- 其余边是多边形的边。