算法，收多邊形

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) 

您的輸入（近似），然後將結果確實：