Determinare lo scafo non convesso della raccolta di segmenti di linea

Question

Ho un problema di geometria computazionale che ritengo dovrebbe avere una soluzione relativamente semplice, ma non riesco a capirlo.

Devo determinare il profilo non convesso di una regione definita da diversi segmenti di linea.

Sono a conoscenza di vari algoritmi di scafo non convesso (ad esempio forme alfa), ma non ho bisogno di un algoritmo completamente generale, in quanto i segmenti di linea definiscono una soluzione unica nella maggior parte dei casi.

---

Come ha sottolineato @ Jean-FrançoisCorbett, ci sono casi in cui ci sono più soluzioni. Ho chiaramente bisogno di pensare di più alla mia definizione.

Tuttavia, ciò che sto cercando di fare è di eseguire il reverse engineering e utilizzare un formato di file proprietario in modo da poter eseguire analisi di base sui dati raccolti da me stesso e da altri. Il formato del file è abbastanza semplice, ma determinare l'algoritmo che usano per definire il limite è considerevolmente più difficile.

Mettere in molti casi limite che si tradurrebbe in una soluzione non univoca fa sì che il software in questione si arresti senza preavviso o silenziosamente non riesca a leggere il file.

Pertanto, quando ci sono più soluzioni, sia la generazione di una delle soluzioni accettabili o la capacità di determinare che ci sono più soluzioni sarebbe accettabile.

---

Problema Definizione:

contorno del poligono non deve mai attraversare qualsiasi dei segmenti e dovrebbe essere formato da linee che uniscono tutti gli endpoint dei segmenti. Tutti i segmenti devono trovarsi interamente all'interno o lungo il confine del poligono. Nessun endpoint può essere utilizzato più di una volta nella struttura (ignorando "chiudendo" il poligono aggiungendo il primo punto alla fine per le librerie software che richiedono la chiusura di poligoni).

Nei casi in cui ci sono più soluzioni che soddisfano questi criteri, una di queste soluzioni sarebbe accettabile. (Sarebbe bello essere in grado di determinare quando la soluzione è non univoco, ma questo non è strettamente necessario.)

---

Esempi:

Per fare un esempio, ho qualcosa in questo senso :

E mi piacerebbe per delineare il seguente zona:

inoltre dovrebbe funzionare per segmenti non si intersecano. Per esempio.

credo (?) C'è una soluzione unica in entrambi i casi, in base ai criteri contorno in precedenza. (Modifica: Non c'è una soluzione unica in generale, come ha sottolineato @ Jean-FrançoisCorbett.Tuttavia, sono comunque interessato a un algoritmo che possa generare una delle soluzioni accettabili.)

Test Cases

Per un banco di prova, ecco il codice per generare le cifre di cui sopra. Sto usando Python qui, ma la domanda è indipendente dalla lingua.

import matplotlib.pyplot as plt 

def main(): 
    test1() 
    test2() 
    plt.show() 

def test1(): 
    """Intersecting segments.""" 
    segments = [[(1, 1), (1, 3)], 
       [(3.7, 1), (2, 4)], 
       [(2, 0), (3.7, 3)], 
       [(4, 0), (4, 4)], 
       [(4.3, 1), (4.3, 3)], 
       [(0, 2), (6, 3)]] 

    desired_outline = [segments[0][0], segments[5][0], segments[0][1], 
         segments[1][1], segments[2][1], segments[3][1], 
         segments[4][1], segments[5][1], segments[4][0], 
         segments[3][0], segments[1][0], segments[2][0], 
         segments[0][0]] 

    plot(segments, desired_outline) 

def test2(): 
    """Non-intersecting segments.""" 
    segments = [[(0, 1), (0, 3)], 
       [(1, 0), (1, 4)], 
       [(2, 1), (2, 3)], 
       [(3, 0), (3, 4)]] 

    desired_outline = [segments[0][0], segments[0][1], segments[1][1], 
         segments[2][1], segments[3][1], segments[3][0], 
         segments[2][0], segments[1][0], segments[0][0]] 

    plot(segments, desired_outline) 


def plot(segments, desired_outline): 
    fig, ax = plt.subplots() 
    plot_segments(ax, segments) 
    ax.set_title('Segments') 

    fig, ax = plt.subplots() 
    ax.fill(*zip(*desired_outline), facecolor='gray') 
    plot_segments(ax, segments) 
    ax.set_title('Desired Outline') 

def plot_segments(ax, segments): 
    for segment in segments: 
     ax.plot(*zip(*segment), marker='o', linestyle='-') 
    xmin, xmax, ymin, ymax = ax.axis() 
    ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5]) 

if __name__ == '__main__': 
    main() 

Qualche idea?

Sto cominciando a sospettare che il software i cui risultati che sto cercando di riprodurre utilizza un algoritmo radiale-sweep in una sorta di "interno" sistema di coordinate (ad esempio un sistema di coordinate con x-prime e y-prime scalata e ruotata lungo la assi principali definiti dalla diffusione dei punti, il che rende il problema più "circolare"). Tuttavia, questo produce soluzioni in cui il contorno interseca segmenti di linea in molti casi. È abbastanza facile rilevare questo e forza bruta da lì, ma sicuramente c'è un modo migliore?

Answer 1

1. Scegliere un punto di partenza sicuro. Può essere ad es. il punto finale con x massimo.
2. Marzo lungo il segmento di linea.
3. All'incrocio con qualsiasi incrocio, girare sempre a sinistra e marciare lungo questo nuovo segmento.
4. Quando si incontra un endpoint, registrarlo. Goto 2.
5. Interrompi quando sei tornato al punto di partenza. L'elenco degli endpoint registrati ora costituisce l'elenco ordinato dei vertici del tuo scafo concavo.

NB: Ciò non riuscirà se è presente un segmento di linea esterna "flottante" che non interseca alcun altro segmento di linea. Tuttavia, si specifica che "le barre definiscono in modo univoco una soluzione", che esclude questa condizione di errore. (Segmenti periferiche rendono possibili due soluzioni uniche.)

EDIT ... o meglio, segmenti periferici può fare due soluzioni uniche possibile - a seconda del layout esatto. Dimostrazione: di seguito è riportato un esempio in cui il segmento giallo che ho aggiunto rende possibili due soluzioni (linee blu e grigie orribilmente disegnate a mano). Se il segmento giallo fosse orientato perpendicolarmente al modo in cui è disegnato ora, sarebbe possibile una sola soluzione. Sembra che il tuo problema sia poco definito.

EDIT In realtà questo può anche fallire se la vostra collezione segmento è "molto concava", vale a dire se ci sono gli endpoint nascosto in angoli recluse della tua pila di segmenti. Nella figura seguente ho aggiunto un segmento nero. Il mio algoritmo sarebbe entrato illegalmente nel suo endpoint in un altro endpoint (linea grigia tratteggiata). Lascerò la mia risposta nel caso in cui gli altri siano inclini a basarsi su di essa.

EDIT dopo aver dato questo un po 'di pensiero: Anche nel caso "molto concava", questa soluzione sicuramente vi darà tutte dei punti di scafo concava nel giusto ordine, ma possono essere intervallati da punti extra, inappropriati come quello nero. Quindi potrebbero esserci troppi punti.

La risposta è, ovviamente, per fare un po 'di potatura. Sarebbe una potatura abbastanza complicata soprattutto se si possono avere "punti di reclusione" multipli e consecutivi come quello nero, quindi non ho in mente un algoritmo intelligente.Ma anche la forza cieca e bruta potrebbe essere fattibile. Ogni punto può essere accettato o respinto (booleano), quindi se hai N punti candidati correttamente ordinati nello scafo concavo, allora ci sono solo 2^N possibilità di controllo. Questo è il modo, modo meno possibilità di forza bruta per il tuo problema originale di permutazioni, che avrebbe SUM of (n!/(n-k)!) for k=1:(n-1) possibilità (scusami la mia notazione). Quindi questo algoritmo riduce significativamente il tuo problema.

Penso che questa sia la strada da percorrere.

Answer 2

Non un'idea completamente polpa-out, ma in ogni caso: supponiamo hai iniziato w/l'algoritmo circolare-sweep per un convesso scafo (dove è sorta, e poi processo, i punti di loro angolo da un punto centrale). Se tutti i punti finiscono in questo scafo, hai finito. Altrimenti, devi "stringere" lo scafo per includere questi punti. Ognuno di questi punti era allo stesso tempo candidato per lo scafo convesso, ed è stato rimosso perché hanno rotto la convessità. A volte (come nel punto viola superiore nel primo esempio), possiamo semplicemente lasciarli dentro. Dove non possiamo, perché il nuovo segmento dello scafo attraversa un segmento (come andare dal verde inferiore al viola inferiore nel il primo esempio, supponendo che il punto aqua inferiore sia stato elaborato prima di quello verde), la correzione è un po 'più complicata (e la parte che non ho arricchito, ed è la parte più indicata nell'ultima modifica della domanda).