algorithme pour fermer un polygone

Question

J'ai une partie de périmètre d'un polygone et la nécessité de fermer it.please référer cette image

Comme je vois qu'il n'y a qu'une seule façon unique de fermer le polygone sans diviser le polygone et sans que les bords se croisent.

Et les bords de fermeture seraient b-> c, d-> e, F-> g, h-> a

Y at-il algo pour y parvenir?

Je ne peux penser à une seule méthode de la force brute, essayez toutes les combinaisons possibles et vérifier si elle forme un polygone fermé (Tout bon algos pour vérifier si elle est un polygone fermé?)

est-il un moyen plus ou algorithme connu?

Note: Les sommets doivent être reliés par lignes droites simples seulement et polygone est pas nécessairement convexe

Vous pouvez également supposer sans risque que ces segments forment toujours un polygone parce que je reçois ces segments de ligne à partir d'un polygone et Im essayant de recréer le polygone

Answer 1

Voici quelque chose qui pourrait fonctionner:
- Faire un ensemble contenant uniquement les points ouverts (points qui ne sont sur un bord, à savoir ceux étiquetés dans votre diagramme)
- Run un humain convexe ll algorithme sur cet ensemble
- Utilisez les bords de la coque convexe pour compléter le polygone avec les arêtes existantes. (Par exemple, si la coque convexe contient A-> B, mais A et B sont déjà connectés indirectement par des arêtes adjacentes dans votre jeu d'arêtes préexistant, jetez le bord A-> B dans la coque convexe)

EDIT
J'avais précédemment suggéré de co-opter des algorithmes de coque convexe mais cette approche présente des inconvénients, y compris le cas où les points ne formeraient pas une forme convexe.

Notez que, selon vos dispositions, il y a des ensembles qui n'auraient pas des solutions, telles que:
(il est impossible de remplir ce dans un polygone sans lignes de croisement, en utilisant uniquement des lignes droites simples entre ouvert points)

Answer 2

Je pense que dans les cas "bien comportés" (petits trous, forme pas trop irrégulière, etc.), on pourrait s'en tirer avec l'approche suivante. L'idée est de supposer que la solution (permutation particulière des segments de ligne d'entrée qui sont alors supposés être reliés à des lignes droites) minimise la longueur de la MultiLineString résultante définissant la frontière du polygone d'intérêt.

Pour résoudre ce problème, l'implémentation ci-dessous utilise l'heuristique 2-opt pour le problème du vendeur itinérant. Elle procède comme suit:

1. l'ensemble des sommets est défini comme l'union des extrémités de tous les segments de ligne d'entrée
2. essaie de se connecter ces points afin de minimiser la longueur totale du MultiLineString résultant sous la contrainte que les points appartenant au même segment de ligne d'entrée sont toujours connectés, l'algorithme 2-opt est autorisé à diviser uniquement les arêtes reliant différents segments de ligne - ceci est géré par la condition supplémentaire if dans le double for principal -loop principal.

Le résultat est alors:

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) 

Pour votre entrée (approchées), le résultat est alors en effet: