0

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

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

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

我想到了使用 boost-graph 来处理图形并将其与 boost-geometry 结合起来。例如，请参阅 TrajGraph，它在 boost-graph 中使用捆绑属性：

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 geometry 的 model::linestring 并使用 boost-geometry 的最近邻查询来查找线段。但是 afaik boost-geometry 不允许像 boost-graph 那样将属性附加到线串。因此如何从线串中获取边缘？

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

4

2 回答 2

2

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

对于与 Boost.Graph 的关系，请参阅 Boost.Geometry: 07_a or 07_b中的示例之一，其中做了类似的事情。所做的是将 Boost.Geometry 线串与其他属性一起存储到 Boost.Graph 边缘（带有属性）中，因此这是另一种方法。

于 2013-08-19T18:51:09.107 回答
1

对于线，我会为每个线段使用 Hesse 范式计算距离并选择或丢弃该线。

黑森范式

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

为了概括它，考虑到您需要的不同属性（线、弧、...），您将有一个不同的类。

于 2013-08-19T17:31:52.720 回答