查找所有linesegments =與圖表中某點的距離在一定範圍內，如何將助推圖與助推幾何結合起來？

Question

我有一組用戶路徑（2個暗淡）在遊戲設置中被建模爲一組線（弧）和路點=頂點。整組路徑可以看作是一個圖形，其中邊緣是具有附加屬性（如長度，概率等）的線段。

現在我必須確定一組（直線）線段=與用戶當前位置的距離，以便查找用戶在圖形中的位置。

如何在不重新發明輪子的情況下儘可能簡單實現？如何有效地實現搜索？

我想過使用boost-graph來處理圖形並將其與boost-geometry相結合。 例如看到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; 

爲了存儲線段爲邊屬性還可以加上升壓幾何模型::線串，並使用升壓幾何形狀的近鄰查詢找到

現在線段。但是，afaik boost-geometry不允許將屬性附加到linestrings，就像boost-graph一樣。因此如何從線串（s）中獲得邊緣？

一個簡單的蠻力解決方案可能是遍歷圖的整個邊界列表並計算到每個線段的距離。有關如何計算到直線段的距離，請參見here和here。

Answer 1

當然可以將屬性附加到Boost.Geometry中的linestrings，實際上Boost.Geometry是用來做這種事情的。你可以從boost :: geometry :: model :: linestring派生，或者實現任何其他基於範圍的結構（例如std :: vector）並將其註冊爲一個線串。請參閱c03示例。

對於與Boost.Graph的關係，請參閱Boost.Geometry中的一個示例：07_a或07_b，其中類似的事情已完成。這裏所做的是將Boost.Geometry線串與其他屬性一起存儲到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; 
}; 

要推廣它，你將有一個不同的類考慮你需要（線，弧，...）不同的屬性。