查找所有linesegments =在图形中某个点的特定距离内的边，如何将boost-graph和boost-geometry结合起来？ [英] Find all linesegments=edges within a certain distance to a point in a graph, how to combine boost-graph with boost-geometry?

问题描述

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

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

如何实现这一点没有重新发明轮子可能吗？如何有效地实现搜索？

我想过使用boost-graph来处理图形并将其与boost-geometry相结合。
例如

  struct Tvertex 
 {
 float x，y ; // vertex = waypoint position 
}; 
 
 struct Tarc_segment 
 {
 float len，curvature，prob; //线段=边缘属性
}; 
 
 typedef adjacency_list< vecS，vecS，directedS，Tvertex，Tarc_segment> TrajGraph; 
  

现在为了将线段存储为边缘属性，可以添加助推几何的model :: linestring并使用助推几何的最近邻居查询来查找线段。但是，afaik boost-geometry不允许将属性附加到linestrings，就像boost-graph一样。因此如何从linestring（s）中获得边缘？

一个简单的蛮力解决方案可能是遍历图的整个边界列表，计算每条线段的距离。请参阅此处和这里如何计算到一条直线段的距离。

解决方案

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

有关与Boost.Graph的关系，请参阅Boost.Geometry中的一个示例： 07_a 或 07_b 类似的事情已经完成。这里做的是将Boost.Geometry线串与其他属性一起存储到Boost.Graph边缘（带有属性），这是另一种方式。

I have a set of user paths (2 dim) in a game setup that are modelled as a set of lines (arcs) and waypoints = vertices. The whole set of paths can be seen as a graph where the edges are line segments that have additional properties like length, probability, etc.

Now I have to identify the set of (straight) line segments = edges within a certain distance to the user's current position in order to find the user's position in the graph.

How to implement this as simply as possible without reinventing the wheel? How to implement the search efficiently?

I thought of using boost-graph for handling the graph and to combine it with boost-geometry. E.g. see TrajGraph which uses bundled properties in 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;

Now in order to store the line segment as an edge property one could add boost geometry's model::linestring and use boost-geometry's nearest neighbour query to find the line segments. But afaik boost-geometry does not allow to attach properties to linestrings as boost-graph does. Hence how to get the edge(s) from the linestring(s)?

A simple brute-force solution might be to traverse the whole edge-list of the graph and calculate the distance to each line segment. See here and here for how to calculate the distance to a straight line segment.

解决方案

It is certainly possible to attach properties to linestrings in Boost.Geometry, actually Boost.Geometry is made for doing such things. You can just derive from boost::geometry::model::linestring, or implement any other range-based structure (e.g. std::vector) and register that as a linestring. See the c03 example.

For the relation with Boost.Graph, see one of the examples in Boost.Geometry: 07_a or 07_b where a similar thing is done. What is done there is storing a Boost.Geometry linestring into the Boost.Graph edge (with a property), together with other properties, so that is another way of doing this.

这篇关于查找所有linesegments =在图形中某个点的特定距离内的边，如何将boost-graph和boost-geometry结合起来？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！