查找到图中某一点一定距离内的所有线段=边，以及如何将增强图与增强几何体相结合

Question

我在游戏设置中有一组用户路径（2 dim），它们被建模为一组线（弧）和路点=顶点。整个路径集可以看作是一个图，其中的边是具有额外属性的线段，如长度、概率等。

现在，我必须识别一组（直线）线段=距离用户当前位置一定距离内的边，以便在图中找到用户的位置。

如何在不重新发明轮子的情况下尽可能简单地实现这一点？如何有效地实现搜索？

我想到了使用boost图来处理该图，并将其与boost几何体相结合。例如，请参阅TrajGraph，它在提升图中使用捆绑属性：

struct Tvertex
{
    float x, y; //vertex=waypoint position
};
struct Tarc_segment
{
    float len, curvature, prob; //line segment=edge properties
};
typedef adjacency_list<vecS, vecS, directedS, Tvertex, Tarc_segment> TrajGraph;

现在，为了将线段存储为边属性，可以添加boost几何体的模型：linestring，并使用boost几何的最近邻居查询来查找线段。但是afaik-boost几何体不允许像boost图那样将属性附加到字符串。因此，如何从线串中获得边缘？

一个简单的暴力解决方案可能是遍历图的整个边列表，并计算到每个线段的距离。有关如何计算到直线段的距离，请参见此处和此处。

Answer 1

在Boost.Geometry中，当然可以将属性附加到行字符串。实际上，Boost.Giometry就是为做这些事情而设计的。您可以从boost:：geometry:：model:：linestring派生，或者实现任何其他基于范围的结构（例如std:：vector）并将其注册为linestring。请参见c03示例。

有关与Boost.Graph的关系，请参见Boost.Geometry:07_a或07_b中的一个示例，其中执行了类似的操作。这里所做的是将Boost.Geometry行字符串存储到Boost.Graph边（带有一个属性）以及其他属性中，所以这是另一种方法。

Answer 2

对于直线，我会对每个线段使用Hesse Normal Form来计算距离并选择或放弃该直线。

黑塞范式

/// Hesse Normal Form
/// NOTE: Since negative distances from the origin are accepted, it is almost
///        a Hesse Normal Form, only)
template<class ScalarType>
class HesseNormalForm2D
{
    public:
    typedef ScalarType Scalar;
    typedef Normal2D<Scalar> Normal;
    typedef Vector2D<Scalar> Vector;
    typedef Point2D<Scalar> Point;
    typedef Line2D<Scalar> Line;
    public:
    /// An invalid line initialized with NaN.
    static HesseNormalForm2D nan() { return HesseNormalForm2D(Normal::nan(), Scalar::nan()); }
    /// An undefined line.
    HesseNormalForm2D() {}
    /// A line defined by a normal and a distance form the origin.
    explicit HesseNormalForm2D(const Normal& n, const Scalar& d)
    :   m_n(n), m_d(d)
    {}
    /// The Hesse Normal Form of a line.
    /// ATTENTION The scalar value d of the line may be negative.
    explicit HesseNormalForm2D(const Point& p, const Vector& v) {
        m_n = -orthonormal(v);
        m_d = scalar_product(m_n, Vector(p));
    }
    /// The Hesse Normal Form of a line.
    /// ATTENTION The scalar value d of the line may be negative.
    explicit HesseNormalForm2D(const Point& p0, const Point& p1) {
        m_n = -orthonormal(p1 - p0);
        m_d = scalar_product(m_n, Vector(p0));
    }
    /// The Hesse Normal Form of a line.
    /// ATTENTION The scalar value d of the line may be negative.
    explicit HesseNormalForm2D(const Line&);
    /// The normal.
    const Normal& n() const { return m_n; }
    /// The normal.
    Normal& n() { return m_n; }
    /// The distance from the origin.
    const Scalar& d() const { return m_d; }
    /// The distance from the origin.
    Scalar& d() { return m_d; }
    /// The distance of a point to the line.
    /// NOTE The point x on the line L with the smallest distance to p is:
    ///       x = p - L(p) * L.n()
    Scalar operator () (const Point& p) const {
        return scalar_product(Vector(p), n()) - d();
    }
    private:
    Normal m_n;
    Scalar m_d;
};

为了推广它，您将有一个不同的类，考虑到您需要的不同属性（直线、圆弧…）。