算法，收多边形

Question

我有一个多边形的周长的一部分，需要关闭it.Please参照这一形象

我所看到的只有一个闭合多边形不将多边形独特的方式并且没有边缘相交。

，截止边缘是B-> C，D-> E，F - >克，H->一

是否有任何的算法方式实现这一目标？

我能想到的只有一个强力的方法，尝试各种可能的组合，并检查它是否形成一个封闭的多边形（任何一个优秀的交易算法，以检查它是否是封闭的多边形？）

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

注：顶点应该由单一的直线只有和多边形连接不一定凸

而且，你可以安全地假设这些段总是形成多边形，因为我从一个多边形得到这些线段和我试着重新创建多边形

Answer 1

这里的东西可能工作：
- 使仅包含了打开点
（即只在一个边缘，即你的图中标记的那些点）一套 - 运行凸凹ll算法
- 使用凸包的边来完成具有现有边的多边形。 （即如果凸包包含A→B，但A和B已经通过预先存在的一组边中的相邻边间接连接，则丢弃凸包中的边A-→B）

编辑
我以前建议增加凸包算法，但是这种方法有缺点，包括点不会凸出的情况。

需要注意的是，根据自己的规定，有集，就不会有解决方案，如：
（这是不可能的，没有交叉线来完成成多边形这一点，使用开放之间只有单一的直线点）

Answer 2

我认为，在“表现良好”（小缺口，不太不规则的形状等）情况下，可能会采取以下方法。这个想法是假定解决方案（特定的输入线段的置换，然后假定用直线连接）使得到的MultiLineString的长度最小化，定义了感兴趣的多边形的边界。

要解决这个问题，下面的实现使用2-opt启发式来解决旅行商问题。它前进在以下步骤：

1. 顶点集被定义为所有输入的线段的端点的并集
2. 它试图这些点，以便下，以最小化得到的MULTILINESTRING的总长度连接属于相同输入线段的点总是连接的限制（即，，2-opt算法仅允许分割连接不同线段的边缘 - 这是由主双for -loop中额外的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) 

您的输入（近似），然后将结果确实：