Znaleźć najmniejszy wielokąt obejmujący zbiór punktów w siatce

Question

Po pierwsze, nie proszę o kod, chcę tylko wyjaśnić moje podejście.

Po drugie, jeśli nie jest to całkowicie związane z SO, przeniesię to pytanie do najbardziej odpowiedniej witryny wymiany stosu. Jestem prawie pewien, że jest to problem związany z teorią grafów.

więc mieć nieskończenie dużą siatkę z określonym punktem (0,0)

każdym skrzyżowaniu pomiędzy liniami poziomymi/pionowo w sieci wyznacza inny punkt (zadanego numeru linii od punktu początkowego).

Biorąc pod uwagę zestaw punktów (x,y), gdzie każdy x,y jest liczbą całkowitą: zwróć obwód najmniejszego wielokąta otaczającego punkty.

Ograniczenia:

• liczba punktów jest mniejsza niż 100.000
• Punkty nie mogą leżeć na obwodzie wielokąta.
• Boki wielokąta mogą odpowiadać tylko pionowym/poziomym liniom w siatce lub przekątnej na pojedynczym kwadracie.

Zgaduję, że jest to problem związany z teorią wykresów. Podobnie jak podróżujący sprzedawca, najpierw muszę znaleźć najkrótszą ścieżkę pomiędzy wszystkimi punktami, używając algorytmu, który daje optymalne rozwiązanie. Następnie muszę wykonać ten sam algorytm między każdym punktem, aby znaleźć optymalną ścieżkę wzdłuż siatki między punktami.

Napisałem algorytm dla podróżującego sprzedawcy z 80 miast.

W tym pytaniu może być 100 000 punktów. Dlatego zastanawiam się, czy istnieje możliwy algorytm do rozwiązania tak dużej liczby węzłów.

Czy istnieje inne podejście. Czy myślę o tym w niewłaściwy sposób?

Dzięki za pomoc!

Answer 1

Urządzenie Convex hull nie jest faktycznie konieczne do rozwiązania tego problemu.

Najwięcej czasu wydajny algorytm convex hull jest O(nlogh), gdzie n jest całkowita liczba punktów, a h jest liczba punktów na kadłubie.

Przeglądając powyższe komentarze, m69 przybił to! Opisany przez niego algorytm (z dodatkowym dodatkiem) można uzyskać w czasie O(n). Złom na pomysł Convex Hull !!

• Narysuj minimalny kwadrat, tak aby otoczył wszystkie podane punkty. Odbywa się to za pomocą maks. & min na liście punktów:
• Dla każdego rogu kwadratu narysuj dozwoloną linię ukośną, która jest najbliższa najbardziej zewnętrznemu punktowi. Odbywa się to poprzez zapętlenie punktów i użycie euklidesowej prostopadłej formuły odległości.To jest O(n)
• Posługując się przecięciami między oryginalnym kwadratem a liniami ukośnymi, obliczyć ogólny obwód wielokąta.

Oto moja wersja algorytmu (napisana w pythonie). Ludzie mogą komentować lub optymalizować je, jeśli chcą. To był zabawny problem do rozwiązania.

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)