Я пытаюсь автоматически «заполнить» все области моего кода, которые полностью заключены в строки (сегменты).
У меня есть сетка фиксированного размера (x, y) в 2D-пространстве и список линий, определяемых их начальной и конечной точками. Эти строки не обязательно заключают пробел.
То, что я ищу, это области, затененные разными цветами синего здесь (в частности, их ограничивающие точки, поскольку я пытаюсь создать сетки для этих областей)
Как я могу алгоритмически найти эти области?
Хитрость заключается в том, чтобы найти полные схемы пересекающихся отрезков, которые определяют каждую область (многоугольник).
Предположим, что отрезки линии названы буквами (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, потому что это может быть край другой области, которую вы еще не нашли.
Существует так называемая теорема о шнурках. Насколько я понимаю, вам нужна область в заштрихованная область. определяет площадь простого polygon. Как только вы найдете пересечения, дающие вам точки, вы можете найти вложенные область. Кроме того, есть эти алгоритмы выпуклой оболочки. Это еще больше эффективен.
# 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]
