Найти все linesegments = ребра на определенном расстоянии до точки на графике, как объединить boost-graph с boost-geometry?

Question

У меня есть набор пользовательских путей (2 тускло) в настройке игры, которые моделируются как набор строк (дуги) и путевых точек = вершины. Весь набор путей можно рассматривать как график, где ребра являются отрезками линии, которые имеют дополнительные свойства, такие как длина, вероятность и т. Д.

Теперь я должен идентифицировать набор (прямых) отрезков линии = ребра в пределах определенного расстояние до текущей позиции пользователя, чтобы найти позицию пользователя на графике.

Как реализовать это как можно проще, не изобретая колесо? Как эффективно реализовать поиск?

Я думал об использовании ускорителя для обработки графика и объединения его с форсированной геометрией. . см 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; 

Теперь для того, чтобы сохранить отрезок в качестве собственности края можно было бы добавить модель :: LineString BOOST геометрии и использовать ближайший сосед запрос бустер-геометрии, чтобы найти сегментов линии. Но afaik boost-geometry не позволяет прикрепить свойства к linestrings, как это делает boost-graph. Следовательно, как получить край (ы) из linestring (s)?

Простым решением грубой силы может быть перемещение всего краевого списка графика и вычисление расстояния до каждого сегмента линии. См. here и here о том, как рассчитать расстояние до сегмента прямой линии.

Answer 1

Это, безусловно, можно прикрепить свойства к linestrings в Boost.Geometry, на самом деле Boost.Геометрия предназначена для таких целей. Вы можете просто извлечь из boost :: geometry :: model :: linestring или реализовать любую другую структуру на основе диапазона (например, std :: vector) и зарегистрировать ее как linestring. См. Пример c03.

Для связи с Boost.Graph см. Один из примеров в Boost.Geometry: 07_a или 07_b, где аналогичная вещь выполняется. Что сделано, там хранятся Boost.Geometry linestring в краю Boost.Graph (со свойством) вместе с другими свойствами, так что это еще один способ сделать это.

Answer 2

Для строк я использовал бы нормальную форму Гессе для каждого сегмента, рассчитывая расстояние и выбираю или отбрасывая эту линию.

Гессе нормальная форма

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

Чтобы обобщить его, вы бы другой класс, учитывая различные атрибуты, которые необходимо (линии, дуги, ...).