连接墙端点
Connecting wall endpoints
我有以下代表墙的点列表：
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>
不太清楚你的最终目标是什么。
你想剪掉哪条线？所有松散的末端还是只是有点太长的末端？那么线条粗细不同呢？
我想出的最简单的方法是将 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)
另一种可能性是真正查看不同矩形的重叠并尝试移动相关边界。但是你有这么多不同的案例，很难找到一个好的通用解决方案，这真的取决于你在寻找什么。
我在 walls2overlap 中添加了 eps 以包含不完全相交的矩形。我评论了一行以不同方式处理自由端。
大量的微调和反复试验...
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))
我有以下代表墙的点列表：
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>
不太清楚你的最终目标是什么。 你想剪掉哪条线？所有松散的末端还是只是有点太长的末端？那么线条粗细不同呢？
我想出的最简单的方法是将 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)
另一种可能性是真正查看不同矩形的重叠并尝试移动相关边界。但是你有这么多不同的案例，很难找到一个好的通用解决方案，这真的取决于你在寻找什么。
我在 walls2overlap 中添加了 eps 以包含不完全相交的矩形。我评论了一行以不同方式处理自由端。
大量的微调和反复试验...
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))