Cos'è un buon algoritmo per tracciare attorno al bordo di una polilinea 2D

Se ho una polilinea composta da un numero qualsiasi di vertici, che cos'è un algoritmo efficiente per tracciare attorno al confine di questa polilinea?

Ci sono 4 situazioni da considerare:

1. La polilinea non si interseca e non ha bordi colineari.
2. La polilinea non si interseca ma ha un ciclo interno o esterno.
3. La polilinea ha auto intersezioni a forma di cravatta a farfalla.
4. La polilinea ha intersezioni automatiche che formano anelli interni.

Un esempio di ciascuno (tutti sono chiusi):

1. Lista vertici = (5,3) (10,3) (10,7) (5,7)
2. Lista vertici = (0,0) (3,0) (3,3) (1,3) (1,2) (2,2) (2,3) (0,3)
3. Lista vertici = (5,3) (10,7) (10,3) (5,7)
4. Lista vertici = (0,0) (3,0) (3,4) (1,4) (1,2) (2,2) (2,3) (0,3)

Visivamente:

Inquestocasounalgoritmodihullingconvessoinrealtànonèappropriato,perchédesideropreservarequalsiasiconcavitànellaforma.

Risultati:

Perchiarire,laformadelpapillonnondeveesserescavalcata,eunsemplicecalcolodell'areadovrebbeprodurreun'areaperquestaforma(cioèiduetriangolifinisconologicamenteavvoltinellastessadirezione).

Non solo questo algoritmo deve funzionare (che è la prima priorità) dovrebbe essere abbastanza veloce da essere eseguito su centinaia di migliaia di polilinee in pochi secondi.

Inoltre, l'algoritmo deve essere in grado di gestire qualsiasi combinazione dei quattro casi.