我有一组矩形,它们具有相同的宽度和高度,并且始终相邻。 我知道所有顶点的位置,每个顶点只有4个。(因为是正方形)。
这张图片可以解释这个问题:
如果有任何间隙,算法将“填补”间隙也可以。
我搜索了很多,但没有找到什么好的方法。 我需要一个简单的算法,它不必非常高效。 假设我们获得了像图像中第二个多边形示例中的7个矩形。 如果我先将1与2合并,然后将我们的新多边形与3合并,以此类推,这样就可以了,因为最多只有50个矩形。
Edge
成为一个类,并正确定义compareTo()
和equals()
方法。compareTo
)。我非常喜欢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的答案执行-删除成对的边缘。
一些假设-所有初始多边形都具有单位长度的边缘。如果不是这样,则在合并时可能需要拆分边缘,并且需要更复杂的方法来检查共享的边缘。
如果需要通过将嵌套形状吸收到较大的形状中(即“填补间隙”)来处理嵌套形状,则会变得有些棘手。您将首先创建一个边缘路径。如果边缘都连接起来,则这是一个简单的形状,其边缘定义了周长。否则,应该有一个外围周长和一个或多个内围周长。忽略内部周长并将形状解析为简单形式-即仅保留外部周长中的边缘。然后,循环遍历形状,并看看其中是否有任何形状在另一个形状中。如果是,则将其移除。
noduri
的成员,但仍在循环遍历它们。如果不改变循环方式,就不能修改列表的成员。 - Trenin
Area
类。 - Brad Mace