Here is some working C++ code for joining vectors (i.e., sequences) of values, joining those with identical end values, reversing the sequences as necessary. I have tested it on thousands of polylines representing roads and other linear features in my map library package, CartoType, as a way of reducing the number of separate lines rendered by the GPU. It can be improved, no doubt, but this code is working and tested.
The performance is, as far as I can see, O(N log(N)); that is, far better than quadratic. The code searches the std::map once or twice per vector, and inserts the new vector's end points. The std::map::find and insert functions are logarithmic in the size of the container.
You supply vectors (which can represent polylines or anything else) one by one, and the algorithm is based on the idea of a map from vector end points to vectors. At any time, each end point is associated with one vector; that is an invariant. If a vector is supplied that duplicates one or two existing end points, it is joined to existing vectors, preserving the invariant, and it is cleared.
After running the joiner by calling VectorJoiner::Join on every vector, you can discard any vectors which have a size of zero.
If using the joiner on a vector of polylines, it's vital to create that vector before calling VectorJoiner::Join on the elements, so that element addresses, which are stored in the std::map, are stable. It is no doubt relatively simple to create a version using array indexes which doesn't suffer from that limitation.
Although this code is part of CartoType it is hereby released under the MIT license.
/*
cartotype_vector_joiner.h
Copyright (C) 2023 CartoType Ltd.
See www.cartotype.com for more information.
*/
#pragma once
#include <vector>
#include <map>
/**
Joins two vectors that share start or end members.
Joins aSource to this aDest by joining it at one end or other if possible and adding the members of aSource to aDest.
Reverses the added members if necessary. Returns true if the join was possible.
Does nothing if either vector is empty.
*/
template<typename T> bool JoinVectors(std::vector<T>& aDest,const std::vector<T>& aSource)
{
if (aDest.empty() || aSource.empty() || &aDest == &aSource)
return false;
if (aDest.back() == aSource.front())
{
aDest.insert(aDest.end(),aSource.begin() + 1,aSource.end());
return true;
}
if (aDest.back() == aSource.back())
{
aDest.insert(aDest.end(),aSource.rbegin() + 1,aSource.rend());
return true;
}
if (aDest.front() == aSource.back())
{
aDest.insert(aDest.begin(),aSource.begin(),aSource.end() - 1);
return true;
}
if (aDest.front() == aSource.front())
{
aDest.insert(aDest.begin(),aSource.rbegin(),aSource.rend() - 1);
return true;
}
return false;
}
/**
A class to join two vectors that share start or end members.
Use it by creating all the vectors, then calling Join once on each vector.
After that, use only those vectors which are not empty.
*/
template<typename T> class VectorJoiner
{
public:
void Join(std::vector<T>& aVector)
{
if (aVector.empty())
return;
std::vector<T>* cur_vector = &aVector;
for (int pass = 0; pass < 2; pass++)
{
auto iter = m_end_map.find(cur_vector->front());
if (iter == m_end_map.end()) // not found
iter = m_end_map.find(cur_vector->back());
if (iter == m_end_map.end()) // not found
break;
auto found_vector = iter->second;
m_end_map.erase(found_vector->front());
m_end_map.erase(found_vector->back());
JoinVectors(*found_vector,*cur_vector);
cur_vector->clear();
cur_vector = found_vector;
}
m_end_map[cur_vector->front()] = cur_vector;
m_end_map[cur_vector->back()] = cur_vector;
}
private:
std::map<T,std::vector<T>*> m_end_map;
};
