Подключение конечных точек стены

ProgramBox

Подключение конечных точек стены

Post author:admin
Запись опубликована:14 апреля, 2023
Post category:Вопросы по программированию

#python #numpy #computer-vision #computational-geometry

#python #numpy #компьютерное зрение #вычислительная геометрия

Вопрос:

У меня есть следующий список точек, которые представляют стены:

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

Я формирую набор полигонов из этих стен со следующим:

 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)

Полигоны в конечном итоге выглядят следующим образом:

Что я хотел бы сделать, так это соединить конечные точки стены таким образом, чтобы они не перекрывались, как показано на рисунке. Какой был бы оптимальный алгоритм для этого?

Вот код для создания изображения:

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

1. добавьте код для построения изображения

2. Я не использую для этого никакой библиотеки. Просто for p in polys: print(f"<polygon points='{str(p).strip('[]')}'/>") и тогда вы можете использовать что-то вроде w3schools.com/html/tryit.asp?filename=tryhtml_svg_circle для построения svg.

3. Также убедитесь, что вы правильно указали размеры для svg, для этого конкретного образца должно хватить 1200×1300.

4. При заданных значениях стен большинство ваших линий наклонные. Но показанное вами изображение имеет идеальные вертикальные и горизонтальные линии. Вы что-нибудь сделали для этого?

5. Изображение формируется из полигонов.

Ответ №1:

Не совсем ясно, какова ваша конечная цель. Какую из строк вы хотите вырезать? Все свободные концы или только те, которые немного длинноваты? А как насчет разной толщины линий?

Самое простое, что я придумал, это преобразовать walls в строки определенной ширины, а затем дискретизировать конечные точки этих строк, таким образом, результирующее изображение выглядит немного чище:

 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)

Другая возможность — действительно посмотреть на перекрытия разных прямоугольников и попытаться сдвинуть соответствующие границы. Но у вас так много разных случаев, что трудно найти хорошее общее решение, и это действительно зависит от того, что вы ищете.

Я добавил eps в walls2overlap , чтобы также включить прямоугольники, которые не совсем пересекаются. И я прокомментировал строку, чтобы по-другому обрабатывать свободные концы. Много тонкой настройки, проб и ошибок…

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

1. Большое спасибо! Второй предоставленный вами скрипт, похоже, именно то, что я искал. Как бы вы ни были обеспокоены обобщением этого, я еще не тестировал его, но если бы вы могли уточнить, каковы были ваши основные проблемы, это было бы очень полезно 🙂

2. Я рад, что смог помочь. Если вы просто хотите обрезать все концы, это должно сработать достаточно хорошо. Однако, как вы можете видеть на темных пятнах, этот алгоритм создает несколько действительно маленьких прямоугольников, которые, возможно, следует полностью удалить. И я не обрабатываю ширину линии, потому что я не знаю, какого поведения вы ожидаете здесь. Вы можете видеть на левой границе наименьшего прямоугольника, что все еще есть возможности для улучшения 😉