将多个相邻的矩形合并为一个多边形 [英] Merging multiple adjacent rectangles into one polygon

问题描述

背景：我正在为小型购物中心设计网站，该网站有多个长方形单位可供租用。当一个商店出现时，它可以租用一个或多个单位，并且我想要生成一个由商店组成的地图（无单位的单位）

问题：

我有一个矩形列表（ units ），由成对的点定义 - <$ c $我想将它们合并到多边形中，所以我可以正确地设置它们的样式（然后我将通过Canvas / SVG / VML渲染它们

• 单位总是矩形


• 单位有不同的尺寸
>

• 单位总是相邻的（它们之间没有空格）
  
  
  

  因此（最好PHP的，但我可以处理伪代码）的操作，我想有一个多边形点的数组。
  
  

  
  

  谢谢。
  
  

  PS：我一直在看这个，我发现了多个'接近我想要的'问题+答案，但我太累了，或者我已经与数学课联系太久了：）
  方案

O'Rourke研究了一个与这个问题有关的问题（以及与计算几何相关的许多问题），并因此产生了一个非常漂亮的方法来有效地解决问题。他的方法在，如果需要的话。

Background: I am working on a site for small shopping center, which has multiple rectangular "units" to rent. When a "shop" comes, it can rent one or multiple "units", and I'd like to generate a map consisting of shops (sans unrented units)

Problem:

I have a list of rectangles (units), defined by pairs of points – [[lefttop_x;lefttop_y];[rightbottom_x;rightbottom_y]] – and I want to merge them into polygons, so I can properly style them (which I will then render via Canvas/SVG/VML/Raphael.js).

• Units are always rectangles
• Units have different sizes
• Units are always adjacent (there is no space between them)

As a result of this (preferably PHP, but I can deal with pseudocode) operation, I'd like to have an array of polygons points.

Thank you.

P.S.: I've been looking into this, and I found multiple 'close to what I want' questions+answers, but I am either too tired or I've been out of touch with maths for too long :)

解决方案

O'Rourke has studied a problem that is related to this one (along many others that relate to Computational Geometry) and as a consequence, produced a very beautiful method to efficiently solve it. His method is described in the paper Uniqueness of orthogonal connect-the-dots and is also clearly illustrated at http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/sdroui9/p0_introduction.html. Note that it says that the polygon shouldn't share vertices in order to apply this method, but this happens very often in the problem we are discussing here. Thus, all we need to do is to eliminate vertices that are shared. Note that this still produces a polygon, and it is the polygon that is wanted as result. Also observe that the list of rectangles must not contain duplicates (I will assume that is the case, otherwise preprocess it to make the list unique).

I've used Python to code it, and if there is any doubt about its meaning, feel free to ask. Here is an overview of the implementation. We start with a list of rectangles described according to OP's notation. Then we obtain the four vertices of each rectangle, discarding shared vertices along the way. This is efficiently achieved using a set. Now we simply apply the algorithm mentioned. Note that I use two hash tables, edges_h (for horizontal edges) and edges_v (for vertical edges), to store the polygon edges. These hash tables effectively work as an undirected graph. Thus, after all the edges are obtained it is easy and fast to obtain the ordered vertices of the polygon. Pick any (key, value) from the hash table edges_h, for example. Now, the next ordered vertex is the one given by edges_v[value] = next_value, and the next one by edges_h[next_value] and so on. Repeat this process till we hit the first chosen vertex, and it is done.

A quick view into the mentioned algorithm is:

1. Sort points by lowest x, lowest y
2. Go through each column and create edges between the vertices 2i and 2i + 1 in that column
3. Sort points by lowest y, lowest x
4. Go through each row and create edges between the vertices 2i and 2i + 1 in that row.

# 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

the result is a list of ordered vertices for the polygon:

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

We can also experiment with a more complicated layout:

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]])

which is represented as the following set of rectangles:

and the method produces the following lists:

[(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)]

which, if drawn, represents the polygons in blue and red, respectively, as in:

As simple benchmarks go:

• 1000 rectangles: ~ 0.04 seconds
• 10000 rectangles: ~ 0.62 seconds
• 100000 rectangles: ~ 8.68 seconds

These timings are simply the average of 10 runs on a busy outdated machine. Rectangles were randomly generated.

EDIT:

Implementation in PHP if needed.

这篇关于将多个相邻的矩形合并为一个多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！