Oblicz obszar podana lista kierunków

Question

Powiedzmy dostaniemy listę kierunków:

up, up, right, down, right, down, left, left 

Jeśli postępuj zgodnie ze wskazówkami, można zawsze powrócić do położenia wyjściowego. Oblicz obszar kształtu, który właśnie utworzyłeś.

kształt utworzony przez wyżej kierunkach będzie wyglądać następująco:

___ 
| |___ 
|_______| 

Najwyraźniej z obrazka, można zobaczyć, że obszar ten jest 3.

Próbowałem użyć do 2d matrycy prześledzić drogę, ale nie wiedzą jak dostać się obszar od które ...

na przykład w moim 2d tablicy:

O O 
O O O 
O O O 

To chyba nie jest dobry sposób na poradzenie sobie z tym pomysłem?

Answer 1

Ponieważ tworzony wielokąt ma tylko krawędzie wyrównane względem osi, można obliczyć całkowity obszar z pionowych płyt.

Załóżmy, że dostaliśmy listę wierzchołków V. Zakładam, że mamy zawijanie na tej liście, więc możemy wysłać zapytanie V.next(v) dla każdego wierzchołka v in V. Dla ostatniego wynik jest pierwszy.

Najpierw spróbuj znaleźć lewy i prawy punkt oraz wierzchołek, w którym znajduje się lewy skrajny punkt (w czasie liniowym).

x = 0      // current x-position 
xMin = inf, xMax = -inf  // leftmost and rightmost point 
leftVertex = null   // leftmost vertex 
foreach v in V 
    x = x + (v is left ? -1 : v is right ? 1 : 0) 
    xMax = max(x, xMax) 
    if x < xMin 
     xMin = x 
     leftVertex = V.next(v) 

Teraz możemy stworzyć prostą strukturę danych: dla każdej pionowej płyty trzymamy sterty max (lista posortowana jest w porządku, jak również, ale musimy tylko powtarzalnie przynieść maksymalny element w końcu).

width = xMax - xMin 
heaps = new MaxHeap[width] 

Zaczynamy śledzenie kształt z wierzchołkiem leftVertex NOW (skrajny lewy wierzchołek znaleźliśmy w pierwszym etapie). Teraz wybieramy, że ten wierzchołek ma pozycję x/y (0, 0), tylko dlatego, że jest wygodny.

x = 0, y = 0 
v = leftVertex 
do 
    if v is left 
     x = x-1   // use left endpoint for index 
     heaps[x].Add(y) // first dec, then store 
    if v is right 
     heaps[x].Add(y) // use left endpoint for index 
     x = x+1   // first store, then inc 
    if v is up 
     y = y+1 
    if v is down 
     y = y-1 

    v = V.next(v) 
until v = leftVertex 

Można zbudować tę strukturę w O(n log n) czasie, ponieważ dodanie do kosztów kupa czasu logarytmicznej.

Wreszcie, musimy obliczyć obszar ze sterty. Aby uzyskać dobrze uformowane dane wejściowe, musimy pobrać dwie sąsiadujące wartości y ze sterty i odjąć je.

area = 0 
foreach heap in heaps 
    while heap not empty 
     area = heap.PopMax() - heap.PopMax() 

return area 

Ponownie, zajmuje to godzinę O(n log n).

---

Przeportowałem algorytm do implementacji java (patrz Ideone). Dwa przykładowe przebiegi:

public static void main (String[] args) { 
    // _ 
    // | |_ 
    // |_ _ | 
    Direction[] input = { Direction.Up, Direction.Up, 
          Direction.Right, Direction.Down, 
          Direction.Right, Direction.Down, 
          Direction.Left, Direction.Left }; 

    System.out.println(computeArea(input)); 

    // _ 
    // |_|_ 
    // |_| 
    Direction[] input2 = { Direction.Up, Direction.Right, 
          Direction.Down, Direction.Down, 
          Direction.Right, Direction.Up, 
          Direction.Left, Direction.Left }; 

    System.out.println(computeArea(input2)); 
} 

Returns (zgodnie z oczekiwaniami):

3 
2 

Answer 2

Zakładając jakiś punkt wyjścia (powiedzmy, (0,0)) i kierunek y jest dodatni w górę:

• lewej dodaje (-1,0) do ostatniego punktu.
• prawy dodaje (+1,0) do ostatniego punktu.
• do góry dodaje (0, + 1) do ostatniego punktu.
• dół dodaje (0, -1) do ostatniego punktu.

Sekwencja kierunkach będzie wtedy utworzyć listę (x, y) wierzchołków współrzędnych, z których obszar uzyskanej (domniemana zamkniętym) wielokąta mogą być znalezione w How do I calculate the surface area of a 2d polygon?

EDIT

Oto implementacja i test w Pythonie. Pierwsze dwie funkcje są z odpowiedzi połączonego powyżej:

def segments(p): 
    return zip(p, p[1:] + [p[0]]) 

def area(p): 
    return 0.5 * abs(sum(x0*y1 - x1*y0 
         for ((x0, y0), (x1, y1)) in segments(p))) 

def mkvertices(pth): 
    vert = [(0,0)] 
    for (dx,dy) in pth: 
     vert.append((vert[-1][0]+dx,vert[-1][1]+dy)) 
    return vert 

left = (-1,0) 
right = (+1,0) 
up = (0,+1) 
down = (0,-1) 

# _ 
# | |_ 
# |__| 
print (area(mkvertices([up, up, right, down, right, down, left, left]))) 
# _ 
# |_|_ 
# |_| 
print (area(mkvertices([up, right, down, down, right, up, left, left]))) 

wyjściowa:

3.0 
0.0 

Należy zauważyć, że podejście to nie dla wielokątów, które zawierają przecinających się linii, jak w drugim przykładzie.

Answer 3

zakładam powinny istnieć pewne ograniczenia dotyczące kształtów rysowania (oś wyrównany, wielokąta wykresie, zamknięte, non przecinających się linii) aby móc obliczyć obszar.

Reprezentują kształt za pomocą segmentów, każdy segment składa się z dwóch punktów, z których każdy ma dwie współrzędne: x i y.

Biorąc pod uwagę te założenia, można powiedzieć, że każdy segment poziomy ma jeden segment równoległy, który ma te same wymiary x dla dwóch punktów, ale różnych wymiarów y.

Powierzchnia pomiędzy tymi dwoma segmentami jest równa różnicy wysokości między nimi. Obwiązywanie obszaru dla wszystkich segmentów poziomych daje całkowitą powierzchnię kształtu.