Connecting wall endpoints

Question

I have the following list of points that represent walls:

walls = [[  76.7403, 1283.2495,  894.5198, 1310.0122],
        [ 864.3867,  415.2406,  891.3730, 1287.3810],
        [  80.0975,  402.9981,  899.7578,  428.0596],
        [  75.9861,  404.3390,  101.6148, 1292.0922],
        [ 469.9275, 1118.6304,  481.1644, 1300.6523],
        [ 500.6000,  897.3496,  876.6120,  908.2079],
        [ 102.0548,  753.6523,  402.9403,  764.0107],
        [ 247.2823,  968.0134,  320.4769,  977.5980],
        [ 503.2201,  898.0987,  515.2742, 1136.6272],
        [ 400.9270,  689.1513,  411.8462,  907.2622],
        [ 353.0995, 1123.1868,  362.8233, 1293.9554],
        [ 248.6094,  967.5870,  261.0458, 1124.8018],
        [ 246.0828,  896.9332,  411.2629,  906.4570],
        [ 880.6799,   60.5249,  892.5886,  411.2219],
        [ 249.5214, 1116.5377,  259.7009, 1290.2698],
        [ 309.1409,  899.7199,  320.3546,  978.5977],
        [  85.6537, 1118.2689,  259.5562, 1128.9491],
        [ 249.0276,  763.1385,  261.5212,  905.9616],
        [  86.2850, 1117.8192,  501.5602, 1128.5548],
        [ 240.1799, 1117.4913,  385.9280, 1128.2761],
        [ 288.5830, 1117.4141,  515.1036, 1128.3738],
        [ 512.2842, 1015.8013,  592.7465, 1022.5025],
        [ 249.2041,  748.7802,  260.6894, 1140.3009],
        [ 401.1811,  687.2712,  411.9943,  779.8344],
        [ 380.8932, 1040.3300,  386.9687, 1126.2324]]  

I'm forming a set of polygons from these walls with the following:

polys = []
for w in walls:
  x0, y0, x1, y1 = w
  poly = [
            (x0, y0), (x1, y0),
            (x1, y1), (x0, y1)
        ]
  poly = list(itertools.chain.from_iterable(poly))
  polys.append(poly)

The polygons end up looking as follows:

What I would like to do is connect the wall endpoints such that they wouldn't overlap as seen in the picture. What would be an optimal algorithm to do this?

Here is the code to produce the image:

<svg width="1200" height="1300">
<polygon points='76.7403, 1283.2495, 894.5198, 1283.2495, 894.5198, 1310.0122, 76.7403, 1310.0122'/>
<polygon points='864.3867, 415.2406, 891.373, 415.2406, 891.373, 1287.381, 864.3867, 1287.381'/>
<polygon points='80.0975, 402.9981, 899.7578, 402.9981, 899.7578, 428.0596, 80.0975, 428.0596'/>
<polygon points='75.9861, 404.339, 101.6148, 404.339, 101.6148, 1292.0922, 75.9861, 1292.0922'/>
<polygon points='469.9275, 1118.6304, 481.1644, 1118.6304, 481.1644, 1300.6523, 469.9275, 1300.6523'/>
<polygon points='500.6, 897.3496, 876.612, 897.3496, 876.612, 908.2079, 500.6, 908.2079'/>
<polygon points='102.0548, 753.6523, 402.9403, 753.6523, 402.9403, 764.0107, 102.0548, 764.0107'/>
<polygon points='247.2823, 968.0134, 320.4769, 968.0134, 320.4769, 977.598, 247.2823, 977.598'/>
<polygon points='503.2201, 898.0987, 515.2742, 898.0987, 515.2742, 1136.6272, 503.2201, 1136.6272'/>
<polygon points='400.927, 689.1513, 411.8462, 689.1513, 411.8462, 907.2622, 400.927, 907.2622'/>
<polygon points='353.0995, 1123.1868, 362.8233, 1123.1868, 362.8233, 1293.9554, 353.0995, 1293.9554'/>
<polygon points='248.6094, 967.587, 261.0458, 967.587, 261.0458, 1124.8018, 248.6094, 1124.8018'/>
<polygon points='246.0828, 896.9332, 411.2629, 896.9332, 411.2629, 906.457, 246.0828, 906.457'/>
<polygon points='880.6799, 60.5249, 892.5886, 60.5249, 892.5886, 411.2219, 880.6799, 411.2219'/>
<polygon points='249.5214, 1116.5377, 259.7009, 1116.5377, 259.7009, 1290.2698, 249.5214, 1290.2698'/>
<polygon points='309.1409, 899.7199, 320.3546, 899.7199, 320.3546, 978.5977, 309.1409, 978.5977'/>
<polygon points='85.6537, 1118.2689, 259.5562, 1118.2689, 259.5562, 1128.9491, 85.6537, 1128.9491'/>
<polygon points='249.0276, 763.1385, 261.5212, 763.1385, 261.5212, 905.9616, 249.0276, 905.9616'/>
<polygon points='86.285, 1117.8192, 501.5602, 1117.8192, 501.5602, 1128.5548, 86.285, 1128.5548'/>
<polygon points='240.1799, 1117.4913, 385.928, 1117.4913, 385.928, 1128.2761, 240.1799, 1128.2761'/>
<polygon points='288.583, 1117.4141, 515.1036, 1117.4141, 515.1036, 1128.3738, 288.583, 1128.3738'/>
<polygon points='512.2842, 1015.8013, 592.7465, 1015.8013, 592.7465, 1022.5025, 512.2842, 1022.5025'/>
<polygon points='249.2041, 748.7802, 260.6894, 748.7802, 260.6894, 1140.3009, 249.2041, 1140.3009'/>
<polygon points='401.1811, 687.2712, 411.9943, 687.2712, 411.9943, 779.8344, 401.1811, 779.8344'/>
<polygon points='380.8932, 1040.33, 386.9687, 1040.33, 386.9687, 1126.2324, 380.8932, 1126.2324'/>
</svg>

Answer 1

It is not quite clear what your final goal is. Which of the lines do you want to cut? All loose ends or just the ones that are a little bit too long? And what about the different thicknesses of the lines?

The simplest thing I came up with is to convert the walls to lines with a specific width and than to discretize the end points of those lines, this way the resulting image looks a little bit cleaner:

import matplotlib.pyplot as plt
import numpy as np


def walls2lines(walls):
    lines = []
    widths = []
    for w in walls:
        x0, y0, x1, y1 = w
        if (x1-x0) > (y1 - y0):
            widths.append(y1-y0)
            lines.append(((x0, y0 + widths[-1] / 2), (x1, y0 + widths[-1] / 2)))
        else:
            widths.append(x1-x0)
            lines.append(((x0 + widths[-1] / 2, y0), (x0 + widths[-1] / 2, y1)))

    return np.array(lines), np.array(widths)


def discretize_np(x, step):
    difference = x % step  # distance to the next discrete value
    difference[difference > step / 2] -= step  # round correctly
    return x - difference


lines, widths = walls2lines(walls=walls)
lines = discretize_np(lines, step=50)
widths *= 10 / widths.max()

fig = plt.figure()
ax = fig.subplots()

for l, w in zip(lines, widths):
    ax.plot(*l.T, lw=w, alpha=0.5)

Another possibility is to really look at the overlaps of different rectangles and try to shift the respecting boundaries. But you have so many different cases that it is hard to find a good general solution and it really depends on what you are looking for.

I added an eps to walls2overlap to also include rectangles that do not quite intersect. And I commented a line to handle the free ends differently. A lot of fine tuning and trial and error...

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
from matplotlib.collections import PatchCollection


def walls2overlap(walls, eps=0):

    idx_overlap = np.ones((len(walls), len(walls)), dtype=bool)
    for i, w_i in enumerate(walls):
        for j, w_j in enumerate(walls):
            (x0_i, x1_i), (y0_i, y1_i) = w_i
            (x0_j, x1_j), (y0_j, y1_j) = w_j
            if (x0_i > x1_j+eps or x1_i < x0_j-eps or
                y0_i > y1_j+eps or y1_i < y0_j-eps):
                idx_overlap[i, j] = False

    return idx_overlap


def get_orientations(walls):
    """
    0: horizontal, 1: vertical
    """
    (x0, x1), (y0, y1) = walls.transpose(1, 2, 0)
    return ((x1 -x0) < (y1 - y0)).astype(int)


def cut_walls(walls, idx_overlap):
    """Move the walls to the most extreme boundary
     of all intersecting walls of different orientation."""
    for i, w_i in enumerate(walls):
        o_i = orientations[i]
        idx_temp = np.logical_and(idx_overlap[i], orientations != o_i)
        if idx_temp.sum() <= 0:  # Set to 1, to keep free ended walls
            continue
        walls[i, o_i, 0] = np.min(walls[idx_temp, o_i, 0])
        walls[i, o_i, 1] = np.max(walls[idx_temp, o_i, 1])

    return walls


walls = np.reshape(walls, (-1, 2, 2), order='F')
idx_overlap = walls2overlap(walls=walls, eps=10)
orientations = get_orientations(walls)
walls = cut_walls(walls=walls, idx_overlap=idx_overlap)

fig, ax = new_fig(aspect=1)
rects = [Rectangle(xy=w[:, 0], width=w[0, 1] - w[0, 0], height=w[1, 1] - w[1, 0])
         for w in walls]
ax.add_collection(PatchCollection(rects, color='k', alpha=0.5))