Как исправить мой алгоритм построения графа видимости? - PullRequest
Новая
       8

Как исправить мой алгоритм построения графа видимости?

0 голосов
/ 09 января 2019

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

Вот тип псевдопифонного кода для моего алгоритма: 

Intersect(wall, P, Q):
    returns True if wall segment intersects with PQ segment

Cross(wall, P, Q):
    returns True if wall segment crosses PQ segment

for i in range(len(nodes)):
    for j in range(i + 1, len(nodes)):
        flag = True
        for wall in walls:
            if (Cross(wall, nodes[i].pos, nodes[j].pos)):
                flag = False
        if (flag):
            nodes[i].adj.append(nodes[j])
            nodes[j].adj.append(nodes[i])

Как я могу исправить свой алгоритм?

Вот один из тестов, где он терпит неудачу:

Стены: 

w1 -> (1, 0),(2, 1)
w2 -> (2, 1),(3, 2)

Проверяемые узлы: 

node1 -> (0, 2)
node2 -> (4, 0)

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

Для пояснения, Cross означает, что два сегмента пересекаются (разделяют точку), но они не разделяют ни одну точку, которая является ни началом, ни концом любого из двух сегментов.

Ответы [ 2 ]

0 голосов
/ 17 января 2019

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

def LeftIntersect(wall, P, Q):
    if Cross(wall, P, Q):
        return False
    if not Intersect(wall, P, Q):
        return False
    if magnitude(cross_product(PQ, wall_midpoint)) <= 0:
        return False
    return True

def RightIntersect(wall, P, Q):
    if Cross(wall, P, Q):
        return False
    if not Intersect(wall, P, Q):
        return False
    if magnitude(cross_product(PQ, wall_midpoint)) >= 0:
        return False 
    return True

for i in range(len(nodes)):
    for j in range(i + 1, len(nodes)):
        crossCount = 0
        leftIntersectCount = 0
        rightIntersectCount = 0
        for wall in walls:
            if (Cross(wall, nodes[i].pos, nodes[j].pos)):
                crossCount += 1
            if (LeftIntersect(wall, nodes[i].pos, nodes[j].pos)):
                leftIntersectCount += 1
            if (RightIntersect(wall, nodes[i].pos, nodes[j].pos)):
                rightIntersectCount += 1
        visible = True
        if (crossCount > 0)
            visible = False
        if (leftIntersect > 0 && rightIntersect > 0)
            visible = False        
        if (visible):
            nodes[i].adj.append(nodes[j])
            nodes[j].adj.append(nodes[i])
0 голосов
/ 11 января 2019

Первый способ, который мне приходит в голову, - это проверить каждую пару из трех из [node_a, node_b, wall_start, wall_end] и посмотреть, проходит ли третья точка вдоль отрезка между двумя другими. Быстрый и точный способ сделать это - сначала создать вектор между каждой из точек и взять два точечных произведения, чтобы убедиться, что «средняя» точка действительно лежит в середине. Кроме того, необходимо также проверить направление векторов, чтобы убедиться, что они параллельны, что одинаково быстро. Если оба пройдут, то третья точка лежит вдоль отрезка между двумя другими.

В питоне 

def intersect(a, b, c):
    (ax, ay), (bx, by), (cx, cy) = a, b, c
    bax, bay = bx-ax, by-ay
    bcx, bcy = bx-cx, by-cy
    acx, acy = ax-cx, ay-cy
    if bax*bcx + bay*bcy < 0: return False
    if bax*acx + bay*acy > 0: return False
    return bax*bcy == bay*bcx

На практике, возможно, лучше сначала проверить bax*bcy == bay*bcx, поскольку он такой же быстрый, но, скорее всего, скорее всего потерпит неудачу (и рано сломается) для непересекающихся точек.

Чтобы затем проверить, пересекаются ли какие-либо две точки с данной стеной- 

def wall_hit(node1, node2, wall_start, wall_end):
    return intersect(node1, node2, wall_start) or \
    intersect(node1, node2, wall_end) or \
    intersect(wall_start, wall_end, node1) or \
    intersect(wall_start, wall_end, node2)

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

Если вам нужно оптимизировать его, вы всегда можете вычислить + повторно использовать вычисления bax, bay = bx-ax, by-ay; ..., либо вставляя все вызовы функций и переупорядочивая их, либо вычисляя их в отдельной функции, а затем кэшируя с помощью декоратора lru_cache из functools. Кроме того, если вы используете метод встраивания, вы, вероятно, можете изменить порядок условных выражений и bax, bay = ... вычислений, чтобы лениво оценивать их, так что вам может не понадобиться вычислять все промежуточные значения для утверждения hit / no_hit.

...