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

Question

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

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

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

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

Я подумал об использовании boost-graph для работы с графиком и объединения его с boost-геометрией.
Например. посмотрите 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 :: linestring и использовать запрос ближайшего соседа boost-geometry, чтобы найти сегменты линии. Но afaik boost-geometry не позволяет привязывать свойства к строкам линий, как это делает boost-graph. Следовательно, как получить ребро (я) из линейки (ей) линии?

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

0

boost-geometry boost-graph c++geometry

Решение

Другие решения

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

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

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

Чтобы обобщить это, у вас будет другой класс, учитывающий различные атрибуты, которые вам нужны (Line, Arc, …).

1

Источник

Accepted Answer

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

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

2