php - 将多个相邻的矩形合并为一个多边形

Question

背景:我在一个小型购物中心网站上工作，该网站有多个矩形“单元”可供出租。当“商店”到来时，它可以租用一个或多个“单元”，我想生成一张由商店组成的 map (没有未租用的单元)

问题:

我有一个矩形列表(单位)，由点对定义 – [[lefttop_x;lefttop_y];[rightbottom_x;rightbottom_y]] – 我想要将它们合并成多边形，这样我就可以正确地设置它们的样式(然后我将通过 Canvas/SVG/VML/Raphael.js 进行渲染)。

• 单位总是矩形
• 单位有不同的大小
• 单元总是相邻的(它们之间没有空格)

作为这个(最好是 PHP，但我可以处理伪代码)操作的结果，我想要一个多边形点数组。

谢谢。

P.S.:我一直在研究这个，我发现了多个“接近我想要的”问题+答案，但我要么太累了，要么我太久没有接触数学了:)

Answer 1

O'Rourke 研究了一个与此问题相关的问题(以及许多其他与计算几何相关的问题)，因此提出了一种非常漂亮的方法来有效地解决它。论文中描述了他的方法 Uniqueness of orthogonal connect-the-dots并且在 http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/sdroui9/p0_introduction.html 中也有清楚的说明。 .请注意，它说多边形不应共享顶点才能应用此方法，但这在我们在这里讨论的问题中经常发生。因此，我们需要做的就是消除共享的顶点。请注意，这仍然会生成一个多边形，并且它是需要的多边形结果。还要注意矩形列表不能包含重复项(我假设是这种情况，否则对其进行预处理以使列表唯一)。

我已经使用 Python 对其进行了编码，如果对其含义有任何疑问，请随时提问。 这是实现的概述。我们从根据 OP 的符号描述的矩形列表开始。然后我们获得每个矩形的四个顶点，沿途丢弃共享顶点。使用 set 可以有效地实现这一点。现在我们简单地应用提到的算法。请注意，我使用了两个哈希表，edges_h(用于水平边)和 edges_v(用于垂直边)来存储多边形边。这些哈希表有效地用作无向图。这样，在得到所有的边之后，就可以很容易快速地得到多边形的有序顶点。例如，从哈希表 edges_h 中选择任何(键，值)。现在，下一个有序顶点是由 edges_v[value] = next_value 给出的，下一个由 edges_h[next_value] 等等。重复这个过程，直到我们到达第一个选择的顶点，就完成了。

对上述算法的快速了解是:

1. 按最低的 x、最低的 y 对点进行排序
2. 遍历每一列并在该列的顶点 2i 和 2i + 1 之间创建边
3. 按最低 y、最低 x 排序点
4. 遍历每一行并在该行的顶点 2i 和 2i + 1 之间创建边。

# These rectangles resemble the OP's illustration.
rect = ([[0,  10], [10, 0]],
        [[10, 13], [19, 0]],
        [[19, 10], [23, 0]])

points = set()
for (x1, y1), (x2, y2) in rect:
    for pt in ((x1, y1), (x2, y1), (x2, y2), (x1, y2)):
        if pt in points: # Shared vertice, remove it.
            points.remove(pt)
        else:
            points.add(pt)
points = list(points)

def y_then_x(a, b):
    if a[1] < b[1] or (a[1] == b[1] and a[0] < b[0]):
        return -1
    elif a == b:
        return 0
    else:
        return 1

sort_x = sorted(points)
sort_y = sorted(points, cmp=y_then_x)

edges_h = {}
edges_v = {}

i = 0
while i < len(points):
    curr_y = sort_y[i][1]
    while i < len(points) and sort_y[i][1] == curr_y: //6chars comments, remove it
        edges_h[sort_y[i]] = sort_y[i + 1]
        edges_h[sort_y[i + 1]] = sort_y[i]
        i += 2
i = 0
while i < len(points):
    curr_x = sort_x[i][0]
    while i < len(points) and sort_x[i][0] == curr_x:
        edges_v[sort_x[i]] = sort_x[i + 1]
        edges_v[sort_x[i + 1]] = sort_x[i]
        i += 2

# Get all the polygons.
p = []
while edges_h:
    # We can start with any point.
    polygon = [(edges_h.popitem()[0], 0)]
    while True:
        curr, e = polygon[-1]
        if e == 0:
            next_vertex = edges_v.pop(curr)
            polygon.append((next_vertex, 1))
        else:
            next_vertex = edges_h.pop(curr)
            polygon.append((next_vertex, 0))
        if polygon[-1] == polygon[0]:
            # Closed polygon
            polygon.pop()
            break
    # Remove implementation-markers from the polygon.
    poly = [point for point, _ in polygon]
    for vertex in poly:
        if vertex in edges_h: edges_h.pop(vertex)
        if vertex in edges_v: edges_v.pop(vertex)

    p.append(poly)


for poly in p:
    print poly

结果是多边形的有序顶点列表:

[(0, 0), (0, 10), (10, 10), (10, 13), (19, 13), (19, 10), (23, 10), (23, 0)]

我们还可以尝试更复杂的布局:

rect = ([[1, 2], [3, 1]], [[1, 4], [2, 2]], [[1, 6], [2, 4]], [[2, 6], [3, 5]],
        [[3, 8], [4, 4]], [[2, 8], [3, 7]], [[3, 10], [5, 8]], [[3, 4], [9, 3]],
        [[4, 5], [7, 4]], [[6, 8], [7, 5]], [[6, 9], [8, 8]], [[8, 9], [10, 6]],
        [[9, 6], [10, 3]])

表示为以下一组矩形:

并且该方法生成以下列表:

[(6, 9), (6, 5), (4, 5), (4, 8), (5, 8), (5, 10), (3, 10), (3, 8),
 (2, 8), (2, 7), (3, 7), (3, 6), (1, 6), (1, 1), (3, 1), (3, 2),
 (2, 2), (2, 5), (3, 5), (3, 3), (10, 3), (10, 9)]

[(9, 4), (9, 6), (8, 6), (8, 8), (7, 8), (7, 4)]

如果绘制，则分别代表蓝色和红色的多边形，如下所示:

作为简单的基准测试:

• 1000 个矩形:~ 0.04 秒
• 10000 个矩形:~ 0.62 秒
• 100000 个矩形:~ 8.68 秒

这些时间只是在繁忙的过时机器上运行 10 次的平均值。矩形是随机生成的。

编辑:

Implementation in PHP如果需要的话。