Еще раз у меня есть несколько вопросов относительно алгоритмов многоугольника.
Я попытаюсь объяснить мою проблему:
Я использую подмножество сторонней библиотеки под названием Geometric Tools (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, где ключом является целое число, представляющее индекс вершины.
Значение представляет, где в массиве ребер есть ребро с ключевым индексом в качестве начального индекса.
Пример макета:
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:
while ( current_placed_index = first_index_in_polygon ) {
int index_to_next_edge_to_be_traversed = edge_starts[ current_edge.second ];
}
Внутри этого цикла выполняется некоторая оптимизация, и индексы вершин добавляются в массив.
Каждый раз, когда многоугольник закрывается, я нахожу первый непересекающийся край и начинаю создавать другой многоугольник. Я продолжаю делать это до тех пор, пока в GTPolygon не останется больше непересекающихся ребер.
Таким образом, каждый GTPolygon может привести к нескольким (внутренним) объектам Polygon.
Недостаток этого алгоритма очевиден, когда два ребра разделяют одну и ту же вершину с начальной. Пример:
<1,2>
<1,3>
<1,5>
При прохождении моих ребер, как я узнаю, какой из этих ребер принадлежит многоугольнику, который я в настоящее время пересекаю? Я мог бы попытаться пересечь края НАЗАД, когда возникает такая дублирующая ситуация. Тогда проблемой будет возможность бесконечного обхода туда-сюда, если при движении задним ходом будет найден другой дубликат.
У меня вопрос, как я могу решить это? Это вообще разрешимо?
Могу ли я использовать дерево BSP для решения этой проблемы? Количество угловых шкафов немного устрашает.
Любая помощь очень ценится, так как от этой работы зависит 5 месяцев работы.
Редактировать:
Чтобы уточнить: я хочу преобразовать из индексированного представления многоугольника, с которым работает Geometry Tools, в наш внутренний формат многоугольника, который представляет собой просто серию связанных вершин в списке.