Trovare un punto INTERIOR rappresentativo per un poligono non convesso

Question

Sto cercando di risolvere un problema di commesso viaggiatore in C++, ma devo percorrere la distanza più breve tra un insieme di poiligoni invece di un insieme di punti. Per fare ciò, sto provando a rappresentare ciascun poligono con un punto interiore "medio" rappresentativo in modo da poter fare un TSP su questi punti interni medi.

È facile per me trovare un punto interno medio in un poligono convesso perché è semplicemente il punto medio aritmetico (e sarà sempre all'interno di un poligono convesso), ma questo approccio non funzionerà per un poligono concavo perché non sarà necessariamente interno al poligono.

Aiuto su questo? Grazie. :-)

Answer 1

ne dite:

1. Triangola poligono (log ordine N (N)) triangolo
2. pescaggio con la più grande area di (diciamo) (ordine N)
3. Scegli il tuo punto al baricentro di quel triangolo . (Const)

Poiché il vero baricentro dell'intero poligono non convesso è (potenzialmente) fuori dal poligono non credo c'è un'altra definizione di un punto "rappresentante" che rende più senso per me che questo .

Answer 2

Un'idea è quella di costruire lo scafo convesso di ciascun poligono e quindi utilizzare il centro dello scafo convesso. Per capire l'idea è come se si avvolgesse qualsiasi poligono con un elastico, questo ti dà una busta che puoi usare per trovare il punto di interesse. Credo che dovresti essere in grado di calcolare quello usando CGAL. Ma se lo fai per ogni poligono non sarà molto veloce. Se si costruisce una triangolazione, è possibile individuare in modo efficiente il punto interno più vicino del poligono originale al punto centrale del suo scafo convesso come passo aggiuntivo.

btw Penso che il modo corretto per trovare il centro del punto di un poligono convesso è di trovare il centro di Chebyshev e questo corrisponde alla soluzione di un sistema lineare che è possibile utilizzare anche con CGAL. Il problema di programmazione lineare per la ricerca del centro Chebyshev di un poligono convesso è ben definito nel Boyd book.