连接无序线段

Question

我的算法会生成（通常）数千条线段（全是二维）的列表，我需要将它们连接成大型折线。这些生成的折线可能是闭合的或开放的，但它们永远不会自相交。线段没有方向，即可能需要翻转线段才能将其连接到相邻线段。

找到这些折线的极快方法是什么？我必须实时执行此操作，因此任何需要超过 10 毫秒的时间都不是解决方案。

我正在用 C# 执行此操作，但我正在寻找想法，而不是源代码。

Answer 1

端点哈希有效吗？

如果端点完全匹配，那么您只需将每个对象存储在哈希中两次，每个端点一次。然后，对于每个对象，查找其两个端点。您将获得需要连接的任何其他对象。

如果端点有任何类型的不精确性，那么您将需要一个空间索引，并且可能需要一个使用 R 树。只需制作一个 2d 哈希网格即可获得类似的效果。哈希网格包含附近端点的存储桶。您需要检查邻近的小区。

Answer 2

对于需要连接的线来说，如果它们足够近，比如末端比某个距离 dclose 更近，则可以使用一个细微的变化，即创建一个单元格大小小于 dclose 的网格，然后对单元格编号 (x, y,z)，每一端的所有整数。在 Python 中，这是一个以 (x, y,z) 作为键和对行的引用作为值的字典。在 C++ 中，这是一个映射。 Dclose 应小于最短线段，因此没有一条线两端具有相同的单元格。

Answer 3

这里有一些有效的 C++ 代码，用于连接具有相同端点的向量，并根据需要反转序列。我已经在我的地图库包 CartoType 中对代表道路和其他线性要素的数千条折线进行了测试，作为减少 GPU 渲染的单独线条数量的一种方法。毫无疑问，它可以改进，但是这段代码正在运行并经过测试。

您一一提供向量（可以表示折线或其他任何内容），该算法基于从向量端点到向量的映射的思想。在任何时刻，每个端点都与一个向量相关联；这是一个不变量。如果提供的向量重复一个或两个现有端点，则将其连接到现有向量，保留不变量，然后将其清除。

运行连接器后，通过在每个向量上重复调用 VectorJoiner::Join，您可以丢弃任何大小为零的向量。

如果在折线向量上使用连接器，那么在元素上调用 VectorJoiner::Join 之前创建该向量至关重要，以便存储在 std::map 中的元素地址稳定。毫无疑问，使用数组索引创建一个不受该限制的版本相对简单。 虽然此代码是 CartoType 的一部分，但特此根据 MIT 许可证发布。

/*
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())
                iter = m_end_map.find(cur_vector->back());
            if (iter == m_end_map.end())
                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;
    };