Quale algoritmo trovare il percorso più breve (numero di nodi) che comprende tutti i poligoni all'interno di un poligono più grande?

Question

Quale algoritmo trovare il percorso più breve (numero di nodi) che comprende tutti i poligoni all'interno di un poligono più grande?

#1 da (2 voti)

2

All'interno di un grande poligono (diciamo i confini USA) ho bisogno di trovare il percorso più breve che comprenda i poligoni più piccoli
(dire le seguenti città: Kansas City, St Louis, Memphis, Oklahoma City)

Per brevissimo intendo con meno nodi possibile. (quindi sarà la più piccola superficie interna)

Un risultato 'non-così-cattivo' sarà il rettangolo di delimitazione che comprende le 4 città
Uno migliore sarà un triangolo (3 nodi < 4) New York, San Antonio, Seattle
Ancor meglio sarebbe il triangolo Minneapolis, Louisville, El Paso perché la superficie è inferiore alla precedente

Esempio per non Stati Uniti

immagina un grande rettangolo 0,0 = > 1000,1000
all'interno di 4 punti 490,490; 490.510; 510,510; 510,490
un buon risultato: rettangolo 490,490 = > 510,510
un risultato migliore: grande triangolo 490,0 490,490 1000,490
ancora meglio: piccolo triangolo 490,490; 530,490 490,530

Esiste un algoritmo ben noto per questo?

algorithms geometry

posta frenchone 03.07.2015 - 00:00

fonte

1 risposta

Leggi altre domande sui tag algorithms geometry

Caching dichiarativo sulle raccolte Concetto di GUI per un editor grafico reattivo asincrono

score 2 · Answer 1

Dici, "racchiudi poligoni più piccoli", ma poi sembra che trattino questi poligoni come punti. Se effettivamente sono effettivamente punti, al contrario di poligoni estesi, allora stai cercando di risolvere il problema del venditore ambulante o TSP , il quale è un problema molto studiato (e difficile).

La tua istanza non è un TSP puro, perché hai un poligono vincolante e vincolante. Questa versione è noto in letteratura come scafo convesso geodetico all'interno di un poligono. C'è un documento di Toussaint su questo argomento che non posso identificare al momento, ma forse questi termini potrebbero aiutare la tua ricerca.