Давайте начнем с преобразования полосы треугольника в многоугольник.В качестве примера мы берем следующую полосу:
(Предоставлено Wikimedia Commons)
Ваше определение полосы будет выглядеть следующим образом:
A B C D E F
Преобразование этого в многоугольникэто очень просто.Просто пройдите по списку и используйте каждую вторую вершину.Когда вы в конце, вернитесь назад и используйте другие вершины.В этом случае:
A C E (reached the end, now return) F D B
Это можно сделать в O (N) , где N - количество вершин полосы.Будет ли это по часовой стрелке или против часовой стрелки, зависит от ориентации полосы.
Итак, мы можем превратить каждую полосу в многоугольник.Осталось только удалить общие ребра.Допустим, у нас есть два многоугольника
A C E F D B
W X E C Y Z
Обратите внимание, что любое общее ребро (в данном случае C E) будет появляться в противоположных направлениях (C E в первом многоугольнике, E C во второмодин).Чтобы найти контур области, нам просто нужно найти совпадающие ребра и объединить два многоугольника.
Чтобы найти совпадающие ребра, достаточно записать все ребра многоугольника в хеш-карту (сохраните, к какому многоугольнику они принадлежати где они находятся в многоугольнике).Это можно сделать в O (E) , где E - общее количество ребер многоугольника.
Чтобы окончательно объединить многоугольники, на самом деле проще создать новыйиз них.Модификация определенно возможна, но немного более тонкая.Для этого нам просто нужно пройтись по краям нашего многоугольника.Пока мы находимся на ребре, обратная сторона которого отсутствует в хэш-карте, тогда запишите это ребро в выходной многоугольник.Если это так, игнорируйте его и переходите к другому многоугольнику.Отметьте края, которые вы посетили, и остановитесь, как только вернетесь к краю, который вы посетили раньше.Делайте это до тех пор, пока не будут посещены все ребра (или оба направления находятся на хэш-карте).Весь этот процесс может быть выполнен в O (E) , где E - общее количество ребер многоугольника.
Вот как это будет выглядеть в нашем примере:
Start at polygon 1
Start at edge (A, C)
(A, C) is neither visited nor is its inverse in the hash map
Create new output area = [A, C]
the inverse of (C, E) is in the hash map, continue to polygon 2
(C, Y) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y]
(Y, Z) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z]
(Z, W) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W]
(W, X) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X]
(X, E) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E]
the inverse of (E, C) is in the hash map, continue to polygon 1
(E, F) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F]
(F, D) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D]
(D, B) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D, B]
(B, A) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D, B, A]
(A, C) is already visited
Close the area contour, continue to check other unvisited edges
Если вы хотите, вы можете также сгруппировать сгенерированные контуры по полигонам, из которых они были созданы, чтобы найти связанные области, которыеограничены несколькими контурами. несвязный набор над полигонами будет полезен для этой задачи.Если вам нужно, вы также можете попытаться классифицировать контуры на отверстия и внешние контуры.Но имейте в виду, что это понятие весьма неоднозначно для сферы (представьте себе сферу и область, которая является полосой вдоль экватора - какой из двух контуров является дырой, а какой снаружи?) Для сравнительно небольших областей вы могли бы использоватьобласть для этой классификации.