Outline tramando algoritmo

Question

mi è stato dato questo compito da mia moglie, quindi è la massima priorità :-)

Ho una collezione di punti (in realtà Northings & Eastings, ma non importa). Voglio prendere quei punti e creare una serie di vettori che rappresentano il contorno, in modo da poter tracciare su Google Earth.

Quindi, qualcosa di simile:

#      # 
      #    #  # 
#    # # 
     # # 

      # 

darebbe:

#-----------------------#-- 
/       \ --# 
#     #------------/ 
\-----#  /
     \ /
      # 

Una possibile soluzione mi è venuta, è quello di calcolare i vettori tra ogni punto, e scartare ogni vettore che si sovrappone un altro vettore. Non l'ho ancora implementato (non proprio sicuro di come), ma mi sono chiesto se ci sono altri modi.

L'algoritmo deve solo essere eseguito un paio di volte, quindi se ci vuole un'ora per corsa e concerti di RAM non è un problema.

Answer 1

Formulazione di poligoni candidati

Sembra che quello che stai cercando per un poligono tale che

• tutti i suoi vertici sono nel vostro set point
• contiene ogni punto nel vostro punto set

Definisce un insieme ammissibile di poligoni candidati rispetto al set di punti.

Scafo convesso?

Una funzione obiettivo potrebbe essere "Tra questi poligoni, scegliere quello con il numero minimo di vertici". Quello sarebbe lo scafo convesso del set di punti. Altre risposte affrontano questo approccio, quindi non dirò altro.

Qualcosa di più ...

Ma questa non è l'unica funzione obiettivo si poteva scegliere. Ad esempio, potresti invece avere un compromesso tra avere meno vertici, avere meno spazio totale e avere angoli meno nitidi ai vertici. Non conosco alcun algoritmo con nome esistente per quel problema, ma è sicuramente interessante.

Un approccio potrebbe essere quello di iniziare trovando lo scafo convesso, quindi "tira dentro" i bordi ai vertici interni nelle posizioni in cui il costo del vertice extra è superato dal vantaggio di avere meno area totale.

Ad esempio, questo:

diventerebbe questo, tirando nel bordo lungo la parte superiore:

Questo secondo poligono potrebbe essere più "naturale" adatto per il set di punti, anche se è non lo scafo convesso del set di punti.

Answer 2

Probabilmente stai cercando lo scafo convesso dei punti; ci sono uno variety of algorithms per averlo trovato.

Answer 3

Here è una libreria per scoprire convesso da code.google.com

Here è una libreria github per la stessa cosa, ma utilizzando Partita Convex Hull Algoritmo di Jarvis.

Spero che aiutano!