php - Merging multiple adjacent rectangles into one polygon

Question

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

Answer 1

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.