Вычислить область, указанную в списке направлений

Скажем, вам предоставлен список направлений:

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

Если следовать указаниям, вы всегда вернетесь в исходное местоположение. Вычислите область созданной вами формы.

Форма, образованная указанными выше направлениями, будет выглядеть примерно так:

 ___
|   |___
|_______|

Ясно, что из рисунка видно, что область 3.

Я попытался использовать матрицу 2d для отслеживания направлений, но не знаю, как получить область от этого...

Например, в моем 2d массиве:

O  O
O  O  O
O  O  O

Это, вероятно, не лучший способ справиться с этим, любые идеи?

Ответ 1

Так как созданный многоугольник имеет только ориентированные по оси края, вы можете рассчитать общую площадь от вертикальных плит.

Скажем, нам дан список вершин V. Я предполагаю, что у нас есть упаковка в этом списке, поэтому мы можем запросить V.next(v) для каждой вершины v in V. Для последнего результат - первый.

Сначала попробуйте найти самую левую и самую правую точку и вершину, где достигается самая левая точка (в линейном времени).

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)

Теперь мы создаем простую структуру данных: для каждой вертикальной плиты мы сохраняем максимальную кучу (отсортированный список тоже хорош, но нам нужно только повторить выбор максимального элемента в конце).

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

Теперь мы начинаем трассировку фигуры из вершины leftVertex (крайняя левая вершина, найденная на первом шаге). Выберем теперь, что эта вершина имеет x/y-позицию (0, 0), просто потому, что она удобна.

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

Вы можете построить эту структуру в O(n log n) времени, потому что добавление в кучу логарифмического времени затрат.

Наконец, нам нужно вычислить область из кучи. Для корректного ввода нам нужно получить два смежных y-значения из кучи и вычесть их.

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

return area

Снова это занимает время O(n log n).

Я поместил алгоритм в реализацию Java (см. Ideone). Два прогона пробега:

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));
}

Возвращает (как и ожидалось):

3
2

Ответ 2

Предполагая некоторую отправную точку (скажем, (0,0)) и направление y положительно вверх:

left добавляет (-1,0) к последней точке.
right добавляет (+1,0) в последнюю точку.
up добавляет (0, + 1) к последней точке.
down добавляет (0, -1) к последней точке.

Последовательность направлений затем создаст список (x, y) вершинных координат, из которых область полученного (подразумеваемого замкнутого) многоугольника может быть найдена из Как сделать Я вычислил площадь поверхности 2-го многоугольника?

ИЗМЕНИТЬ

Вот реализация и тест в Python. Первые две функции связаны с ответом, указанным выше:

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])))

Вывод:

3.0
0.0

Обратите внимание, что этот подход не подходит для полигонов, которые содержат пересекающиеся линии, как во втором примере.

Ответ 3

Я предполагаю, что должны быть некоторые ограничения на фигуры, которые вы рисуете (выравнивание по оси, полигональный граф, закрытые, не пересекающиеся линии), чтобы иметь возможность рассчитать площадь.

Представляем форму с использованием сегментов, каждый сегмент состоит из двух точек, каждая из которых имеет две координаты: x и y.

Принимая во внимание эти предположения, можно сказать, что любой горизонтальный сегмент имеет один параллельный сегмент, который имеет одинаковые размеры x для своих двух точек, но разные га размерности.

Площадь поверхности между этими двумя сегментами равна разнице в высоте между ними. Суммирование области для всех горизонтальных сегментов дает вам общую площадь поверхности фигуры.