Найти закрытую (поверхность) область из набора линий - PullRequest
Новая
       59

Найти закрытую (поверхность) область из набора линий

0 голосов
/ 31 мая 2018

Я пытаюсь автоматически «заполнить» все области в моем коде, которые полностью заключены в строки (сегменты).

У меня есть сетка фиксированного размера (x, y) в 2D-пространстве и список линий, определяемых их начальной и конечной точками.Эти строки не обязательно заключают пробел.

Визуальный пример .

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

Как я могу алгоритмически находить эти области?

Ответы [ 2 ]

0 голосов
/ 31 мая 2018

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

Давайте предположим, что отрезки названы буквами (A, B, C, ...).

Я бы начал с создания таблицы, которая позволяет находить пересечения по отрезку линии. 

A -> B
A -> C
A -> D
B -> A
C -> A
C -> D
D -> A

(В этом примере ACD образует треугольную область, а B - просто отрезок прямой линииэто происходит при пересечении A.)

Выберите отрезок, скажем, A, и проверьте его первое пересечение, которое происходит с отрезком B. Теперь мы начинаем сканировать пересечения B.B соединяется обратно с A, что завершает контур, но было только два шага, так что это недопустимая область.

Поскольку B не имеет больше пересечений, мы возвращаемся назад и смотрим на следующее пересечение A, которое сПервое пересечение C. C с A, которое завершает схему, но это только два шага, поэтому это недопустимая область.Но следующее пересечение C - это D, а первое пересечение D - это A, которое завершает трехступенчатую схему, так что теперь у нас есть правильная область, в частности, треугольник.Площадь определяется точками пересечений, которые мы использовали в нашей схеме: Pac, Pcd, Pda.

Как только вы изучите все возможные пути из A, вы начнете снова с B. Обратите внимание, что выВы найдете области несколько раз, поэтому вы должны отфильтровать дубликаты.Но вы не можете вообще пропустить проверку B, потому что это может быть край другой области, которую вы еще не нашли.

0 голосов
/ 31 мая 2018

Существует нечто, называемое Теорема о шнурках. Если я так понимаю, вам нужна область в затененной области . Она определяет область простого многоугольника. Как только вы найдете пересечения, дающие вам точки, вы можете найти закрытую область.Кроме того, существуют следующие алгоритмы выпуклой оболочки. Это еще более эффективный. 

    # Area of Polygon using Shoelace formula
# http://en.wikipedia.org/wiki/Shoelace_formula
# FB - 20120218
# corners must be ordered in clockwise or counter-clockwise direction
def PolygonArea(corners):
    n = len(corners) # of corners
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += corners[i][0] * corners[j][1]
        area -= corners[j][0] * corners[i][1]
    area = abs(area) / 2.0
    return area

# examples
corners = [(2.0, 1.0), (4.0, 5.0), (7.0, 8.0)]
print PolygonArea(corners)
corners = [(3.0, 4.0), (5.0, 11.0), (12.0, 8.0), (9.0, 5.0), (5.0, 6.0)]
print PolygonArea(corners)


let N           = number of points
let points[N+1] = the array of points
swap points[1] with the point with the lowest y-coordinate
sort points by polar angle with points[1]

# We want points[0] to be a sentinel point that will stop the loop.
let points[0] = points[N]

# M will denote the number of points on the convex hull.
let M = 1
for i = 2 to N:
    # Find next valid point on convex hull.
    while ccw(points[M-1], points[M], points[i]) <= 0:
        if M > 1:
            M -= 1
            continue
        # All points are collinear
        else if i == N:
            break
        else
            i += 1

    # Update M and swap points[i] to the correct place.
    # This code is wrong as explained in the talk page. When M and i are the same, the algorithm ends up in an infinite loop.
    M += 1
    swap points[M] with points[i]
...