Trovare il poligono più piccolo che copre un insieme di punti in una griglia

Question

In primo luogo, non sto chiedendo il codice, voglio solo un chiarimento sul mio approccio.

In secondo luogo, se questo non è totalmente correlato a SO, sposterò la domanda sul sito di Scambio Stack più rilevante. Sono abbastanza sicuro che questo è un problema correlato alla teoria dei grafi.

Quindi Ho un infinitamente grande griglia con un punto definito (0,0)

Ogni intersezione tra linee orizzontali/verticali nella griglia definisce un altro punto (dato dal numero di righe dall'origine).

Dato un set di punti (x,y) dove ogni x,y è un numero intero: restituire il perimetro del poligono più piccolo che circonda i punti.

Vincoli:

• Il numero di punti è inferiore a 100.000
• I punti non possono giacere sul perimetro del poligono.
• I lati del poligono possono corrispondere solo a linee verticali/orizzontali nella griglia o a una linea diagonale in un singolo quadrato.

Suppongo che sia un problema correlato alla teoria dei grafi. Proprio come il venditore ambulante, ho prima bisogno di trovare il percorso più breve tra tutti i punti utilizzando un algoritmo che fornisce una soluzione ottimale. Quindi ho bisogno di eseguire lo stesso algoritmo tra ogni punto per trovare il percorso ottimale lungo la griglia tra i punti.

Ho scritto un algoritmo per il commesso viaggiatore con 80 città.

In questa domanda ci possono essere 100.000 punti. Quindi mi chiedo se esiste un possibile algoritmo per risolvere un numero così grande di nodi.

C'è un altro approccio. Sto pensando a questo nel modo sbagliato?

Grazie per qualsiasi aiuto!

Answer 1

Il Convex hull non è effettivamente necessario per risolvere questo problema.

La maggior parte del tempo efficiente convex hull algoritmo è O(nlogh), dove n è il numero di punti complessivi, e h è il numero di punti sullo scafo.

Guardando attraverso i commenti sopra, m69 inchiodato! L'algoritmo che descrive (con un po 'di più in alto) può essere raggiunto nel tempo O(n). Rottami l'idea Convex Hull !!

• Disegna il quadrato minimo in modo che circonda tutti i punti indicati. Questo viene fatto utilizzando max & min nell'elenco dei punti
• Per ciascun angolo del riquadro, tracciare la linea diagonale consentita più vicina al punto più esterno. Questo viene fatto scorrendo attraverso i punti e usando la formula della distanza perpendicolare euclidea.Questo è O(n)
• Utilizzando le intersezioni tra il quadrato originale e le linee diagonali, calcolare il perimetro generale del poligono.

Ecco la mia versione dell'algoritmo (scritto in python). Le persone sono libere di commentarle o ottimizzarle se lo desiderano. È stato un problema divertente da risolvere.

from math import * 
N = int(raw_input()) 
pts = [] 

for i in xrange(N): 
    p1,p2 = map(int, raw_input().split(' ')) 
    pts.append((p1,p2)) 

def isBetween(a, b, c): 
    ab = sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) 
    ac = sqrt((a[0]-c[0])**2 + (a[1]-c[1])**2) 
    bc = sqrt((b[0]-c[0])**2 + (b[1]-c[1])**2) 
    return abs(ac + bc - ab) < 0.01 # epsilon precision, needs < 1 in grid case 

def getPoints(c): 

    lines = [(-1, c[0][1]+c[0][0]),(1, c[1][1]-c[1][0]),(-1,c[2][1]+c[2][0]),(1,c[3][1]-c[3][0])] 
    maxes = [[0,0],[0,0],[0,0],[0,0]] 

    for count, line in enumerate(lines): 

     pdist = (abs(line[0]*CH[0][0] - CH[0][1] + line[1]))/(sqrt((line[0]*line[0]) + 1)) 
     maxes[count][0] = pdist 
     maxes[count][1] = CH[0] 

    for elem in CH[1:]: 

     for count, line in enumerate(lines): 

      pdist = (abs(line[0]*elem[0] - elem[1] + line[1]))/(sqrt((line[0]*line[0]) + 1)) 
      if pdist < maxes[count][0]: 
       maxes[count][0] = pdist 
       maxes[count][1] = elem 

    for greg in range(4): 
     maxes[greg][1] = list(maxes[greg][1]) 

    maxes[0][1][0] -=1 
    maxes[1][1][0] +=1 
    maxes[2][1][0] +=1 
    maxes[3][1][0] -=1 

    gregarr = [] 

    for i in range(4): 

     y = lines[i][0]*(c[i][0]-maxes[i][1][0]) + maxes[i][1][1] 
     cornerdist = abs(c[i][1] - y) 

     if i == 0: 
      gregarr.append((c[i][0], c[i][1]+cornerdist)) 
      gregarr.append((c[i][0]+cornerdist, c[i][1])) 
     elif i == 1: 
      gregarr.append((c[i][0]-cornerdist, c[i][1])) 
      gregarr.append((c[i][0], c[i][1]+cornerdist)) 
     elif i == 2: 
      gregarr.append((c[i][0], c[i][1]-cornerdist)) 
      gregarr.append((c[i][0]-cornerdist, c[i][1])) 
     else: 
      gregarr.append((c[i][0]+cornerdist, c[i][1])) 
      gregarr.append((c[i][0], c[i][1]-cornerdist)) 

    return gregarr 

def distance(p0, p1): 

    return ((p0[0] - p1[0])*(p0[0] - p1[0]) + (p0[1] - p1[1])*(p0[1] - p1[1]))**(0.5) 

def f7(seq): 
    seen = set() 
    seen_add = seen.add 
    return [ x for x in seq if not (x in seen or seen_add(x))] 

CH = pts 
H = len(CH) 

if H == 0: 
    print('0.000') 
elif H == 1: 
    print('5.656') 
else: 
    per = 0 
    minx = min(CH, key = lambda x: x[0])[0]-1 
    miny = min(CH, key = lambda x: x[1])[1]-1 
    maxx = max(CH, key = lambda x: x[0])[0]+1 
    maxy = max(CH, key = lambda x: x[1])[1]+1 
    corners = [(minx,miny),(maxx, miny),(maxx,maxy),(minx,maxy)] 
    arr = getPoints(corners) 
    arr = f7(arr) 
    arr.append(arr[0]) 
    T = len(arr) 

    for i in range(1,T): 

     per += distance(arr[i-1], arr[i]) 

    print(per)