CODEWITHSUNDEEP
algorithmgeometry
David Rutten
David Rutten

Reputation: 4806

Joining unordered line segments

My algorithm produces a list of (usually) several thousand line segments (all 2D) which I need to join up into large polylines. These resulting polylines might be closed or open, but they are never self-intersecting. The line segments are not directed, i.e. it might be needed to flip a line segment before it can be joined to its neighbour.

What would be an extremely fast way of finding these polylines? I have to do this in real-time, so anything that takes longer than -say- 10ms is not a solution.

I'm doing this in C#, but I'm looking for ideas, not source.

Upvotes: 11

Views: 5623

Answers (3)

Graham Asher
Graham Asher

Reputation: 1780

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;
    };

Upvotes: 0

Munther Hindi
Munther Hindi

Reputation: 1

A slight variation that would work for lines that need to be joined if they are close enough, say the ends closer than some distance dclose, is to create a grid of cell size less than dclose, and then hash the cell number (x,y,z), all integers, of each end. In Python this is a dictionary of (x, y,z) as keys and a reference to the line as value. In C++, this is a map. Dclose should be made smaller than the shortest line segment, so no single line has the same cell for both ends.

Upvotes: -1

DigitalRoss
DigitalRoss

Reputation: 146043

Would a hash of endpoints work?

If the endpoints match exactly then you can just store each object twice in a hash, once by each endpoint. Then, for each object, look up both its end points. You will get any other objects that need to be joined.

If the endpoints have any kind of imprecision, then you will need a spatial index, and probably one that uses an R-tree. You can get a similar effect by just making a 2d hash grid. The hash grid contains buckets of nearby endpoints. You will need to check neighboring cells.

Upvotes: 13

Related Questions