Преобразование индексированных многоугольников в неиндексированные. Возникло несколько проблем

Question

Еще раз у меня есть некоторые вопросы, касающиеся алгоритмов многоугольника.

Я попытаюсь объяснить мою проблему:

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

Наш внутренний многоугольный формат состоит из массива вершин, а многоугольник GT состоит из индексированного массива вершин, где каждое ребро представлено парой индексов.

Пример квадрата для осветления:

Внутренний формат:

vertices[0] = Vertex2D(1,0) -> start 
vertices[1] = Vertex2D(1,1) 
vertices[2] = Vertex2D(0,1) 
vertices[3] = Vertex2D(0,0) 
vertices[4] = Vertex2D(1,0) -> end 

Внешний формат:

vertices[0] = Vertex2D(1,0) 
vertices[1] = Vertex2D(1,1) 
vertices[2] = Vertex2D(0,1) 
vertices[3] = Vertex2D(0,0) 

edges[0] = std::pair<int,int>(0,1) 
edges[1] = std::pair<int,int>(1,2) 
edges[2] = std::pair<int,int>(2,3) 
edges[3] = std::pair<int,int>(3,0) 

//There is also a BSP tree of the polygon which I don't care to depict here. 

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

Сделать std :: map, где ключ представляет собой целое число, представляющее индекс вершины. Значение представляет, где в реберном массиве есть край с ключевым индексом в качестве начального индекса.

Mockup пример:

std::vector< std::pair< int, int > > edge_array; 

edge_array.push_back(std::pair< int, int >(0, 1)); 
edge_array.push_back(std::pair< int, int >(2, 3)); 
edge_array.push_back(std::pair< int, int >(1, 2)); 
edge_array.push_back(std::pair< int, int >(3, 0)); 

std::map< int, int > edge_starts; 
for (int i = 0 ; i < edge_array.size(); ++i) { 
    edge_starts[ edge_array[i].first ] = i; 
} 

Чтобы перейти от правильного края, чтобы исправить края я могу теперь просто сделать следующее внутри время цикла:

while (current_placed_index = first_index_in_polygon) { 
    int index_to_next_edge_to_be_traversed = edge_starts[ current_edge.second ]; 
} 

Внутри этого цикла есть сделать некоторые оптимизации, и индексы вершин добавляются в массив.

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

Таким образом, каждый GTPolygon может приводить к нескольким многоугольным (внутренним) объектам.

Ошибка в этом алгоритме очевидна, когда существуют два ребра, разделяющие ту же вершину, что и начальная вершина. Пример:

<1,2> 
<1,3> 
<1,5> 

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

Вопрос в том, как я могу это решить? Разрешено ли это вообще? Могу ли я использовать дерево BSP, чтобы каким-то образом решить эту проблему? Количество угловых случаев немного сложнее.

Любая помощь очень ценится, так как 5 месяцев работы зависит от этой работы.

Edit:

Для уточнения: я хочу, чтобы преобразовать из индексированного представления многоугольника Геометрии Инструменты работает с нашим внутренним форматом полигон, который является только рядом соединенных вершин в списке.

Answer 1

Вы эффективно пытаетесь найти все cycles в undirectedgraph, где каждый цикл представляет собой края уникального многоугольника. This paper предлагает решение depth-first search (DFS).

Answer 2

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

Answer 3

Ха-ха, хорошо, ребята. Кажется, что весь хубуб был ни за что. Я обнаружил, что у Geometry Tools есть собственный класс для решения таких проблем.

Пример: here.