java - 将adiacent矩形合并为多​​边形

Question

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

这张图片可以解释这个:

如果有任何差距,如果算法将"填补"差距,则可以.

我搜索了很多,找不到任何好的东西.我需要一个简单的算法,它不一定非常有效.让我们说我们有7个矩形,就像图像中的第二个多边形示例一样.如果我先将1与2合并,然后将我们的新多边形与3合并,那么就可以了,依此类推,它不一定非常快,因为最多会有50个矩形.

Answer 1

因为您的形状仅由矩形组成且它们始终相邻,所以合并算法比没有这些假设的算法简单得多.

• 从矩形创建所有边的列表.一个矩形有4个边.
• 让Edge与正确定义一个类compareTo()和equals().
• 对边列表进行排序(使用compareTo).
• 遍历列表.如果列表TWICE中存在相同的边缘,请从列表中删除它们.
• 其余边是多边形的边.

Answer 2

我真的很喜欢达柳斯回答的效率。它可能满足您的所有要求，在这种情况下就选择它吧。

然而，我想到了一些问题。

如果合并后有多个形状怎么办？如何检测这些形状是独立的还是嵌套的？就这一点而言，如果只是给你一组边缘，那么很难判断它是否构成了一个形状，或者形状内留下的空隙。

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

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

这里实际上有两种形状——一种在另一种里面。然而，有 3 组相连的边。为了查看内部矩形是形状还是形状内的空白，您必须从外部矩形开始并向内操作。这样做将导致知道该形状基本上是围绕另一个矩形的矩形的轮廓。然而，如果您要删除外边缘，所得的形状将只是一个空心矩形 - 一种形状。

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

不要在开始时将所有矩形的所有边的集合放在一起，而是将每个矩形单独保存在 s 列表中Polygon。每个Polygon都有自己的一组边缘。

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

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

最后，您将Polygon在 中获得一个单独的 s列表plist。

sharesEdge只需在每个边缘上循环Polygon，看看它们是否有共同点。

merge与 Dariusz 的答案完全相同 - 删除边缘对。

一些假设 - 所有初始多边形都具有单位长度的边。如果情况并非如此，那么您可能需要在合并时分割边，并使用更复杂的方法来检查共享边。

如果嵌套形状需要通过将它们吸收到更大的形状中（即填充间隙）来处理，那么它会变得有点棘手。您首先要创建一条边缘路径。如果边全部相连，那么这是一个简单的形状，其边定义了周长。如果不是，则应该有一个外周界和一个或多个内周界。忽略内周界并将形状解析为简单 - 即仅保留外周界的边缘。然后，循环遍历这些形状，看看是否有任何一个形状在另一个形状的内部。如果是这样，请将其删除。