python - 关闭多边形的算法

Question

我有一个多边形的一部分周长，需要将其闭合。请引用这张图片

正如我所见，只有一种独特的方法可以在不分割多边形且边不相交的情况下闭合多边形。

闭合边为 b->c,d->e,f->g,h->a

是否有任何算法可以实现这一点？

我只能想到一种暴力方法，尝试所有可能的组合并检查它是否形成一个封闭的多边形(任何好的算法来检查它是否是封闭的多边形？)

有没有更好的方法或已知的算法？

注意:顶点只能用单条直线连接，多边形不一定是凸的

此外，您可以放心地假设这些线段总是形成多边形，因为我从多边形中获取这些线段并且我试图重新创建多边形

Answer 1

我认为在“行为良好”(小间隙，不太不规则的形状等)的情况下，可能会采用以下方法。这个想法是假设解决方案(输入线段的特定排列，然后假设与直线连接)最小化定义感兴趣多边形边界的结果 MultiLineString 的长度。

为了解决这个问题，下面的实现使用了 2-opt对旅行商问题的启发式。它按以下步骤进行:

1. 顶点集定义为所有输入线段端点的并集
2. 它尝试连接这些点，以便在属于同一输入线段的点始终连接的约束下最小化生成的 MultiLineString 的总长度(即，允许 2-opt 算法仅分割边连接不同的线段 - 这由主双 for 循环中的额外 if 条件处理。

结果是:

import logging
import random
import sys
from shapely.geometry import LineString, Polygon
from shapely.ops import polygonize, linemerge

#prevent shapely from showing an error message on is_valid tests  
logger = logging.getLogger()
logger.setLevel(logging.ERROR)

#input lines (LineStrings)
lines = [
    [(3.15,3.94), (4.06,3.91), (4.27,3.49)],
    [(0.84,2.99), (0.97,3.67), (1.68,3.91), (2.68,3.92)],
    [(4.46,3.23), (5.12,2.97), (4.60,2.00)],
    [(4.13,1.44), (4.41,0.68), (1.14,1.99)]
]
random.shuffle(lines)

N, pnts = 0, []
pnt2line = {}
for line_id, line in enumerate(lines):
    #for each line, save its endpoints and remember
    #to which line each point belongs
    for pnt in [line[0], line[-1]]:
        pnt2line[N] = line_id
        pnts.append(pnt)
        N += 1

#as initial guess, try to connect these points sequentially
route = [i for i in range(0, N)]

def nrm_idx(N, idx):
    return (N + idx) % N

def get_polygon(route):
    #for given route, attempt to construct the resulting polygon
    segments = []
    m = len(route)
    for idx in range(0, m):
        i, j = route[idx], route[nrm_idx(m, idx+1)]
        if pnt2line[i] == pnt2line[j]:
            #if two consecutive points belong to the same line, consider this line
            segments.append(lines[pnt2line[i]])
        else:
            #otherwise, connect these points with a straight line
            segments.append([pnts[i], pnts[j]])

    return Polygon(linemerge(segments))

def get_weight(route):
    P = get_polygon(route)
    return P.length if P.is_valid else sys.maxsize

def edge_is_fixed(pnt_i, pnt_j):
    #check if an edge specified by point pnt_i/pnt_j can be dissected or not
    #in the latter case, the points belong to the same line/line segment
    return (pnt2line[pnt_i] == pnt2line[pnt_j])

def opt_swap(route, i, k):
    #perform 2-opt swap
    return route[0:i] + route[i:k+1][::-1] + route[k+1:]

flag = True
while flag:
    flag = False
    best_weight = get_weight(route)

    for i in range(0, N-1):
        for k in range(i+1, N):

            if edge_is_fixed(route[nrm_idx(N, i-1)], route[i]) or edge_is_fixed(route[k], route[nrm_idx(N, k+1)]):
                continue

            new_route = opt_swap(route, i, k)
            weight = get_weight(new_route)

            if weight < best_weight:
                route = new_route[:]
                best_weight = weight
                flag = True

P = get_polygon(route)
for x, y in P.exterior.coords:
    print(x, y)

对于您的输入(近似值)，结果确实是: