I want to create a boost graph from a GeoJSON file containg a network of linestrings. Some linestrings have common nodes. In other words: everything is somehow connected. the file looks like this: (here only 3 linestrings: in reality more than 8000).
{"type": "Feature", "properties": {"id": 1}, "geometry": { "type": "LineString", "coordinates": [ [ 147.0, -4.8 ], [ 141.0, -2.0 ] ]}},
{"type": "Feature", "properties": {"id": 2}, "geometry": { "type": "LineString", "coordinates": [ [ 152.6, -5.2 ], [ 152.05, -3.8 ], [ 147.0, -4.8 ] ] } },
{"type": "Feature", "properties": {"id": 3}, "geometry": { "type": "LineString", "coordinates": [ [ 147.0, -4.8 ], [ 144.73, 0.0 ] ] } },
You see that the coordinate [147.0, -4.8] is part of all 3 linestrings.
I iterate over this file and save these information in a vector linestrings containing struct variables called linestring:
struct linestring //data of one linestring
{
int id;
std::vector<std::vector<double>> pos; //2D vector conatining x and y positions
};
std::vector <linestring> linestrings; //containing the inforamtion of all linestrings
Now I want to use this to build a boost graph:
struct Nodes
{
double x;
double y;
};
struct Legs
{
int id;
double distance; //edge weight calculated with distance=sqrt((x2-x1)^2 (y2-y1)^2) euclidean distance
};
typedef adjacency_list<listS, vecS, undirectedS, Nodes, Legs> graph_t;
graph_t LinestringGraph;
Which commands are recommended for such a job?
I don't want to add all vertexes and check for redundancy by iterating or other time consuming stuff.
Is there a possibility to add an edge with the custom id and the calculated edge weight together with the vertexes containing the custom property of xy-coordinate.
I want to do something like this: PSEUDOCODE:
iterate over the vector linestrings
count the number of waypoints in the linestring
//e.g. in id=2 are "coordinates":
// [ [ 152.6, -5.2 ], [ 152.05, -3.8 ], [ 147.0, -4.8 ] ]
//edge from [ 152.6, -5.2 ] to [ 152.05, -3.8 ]
// and from [ 152.05, -3.8 ] to [ 147.0, -4.8 ]
add counted edges to the boost graph
and weight with euclidean distance of start and end coordinate of
the current (part)linestring.
if one vertex already exists (e.g. [ 147.0, -4.8 ])
do not create a new vertex --> use the existing
CodePudding user response：
I don't want to add all vertexes and check for redundancy by iterating or other time consuming stuff.
Iterating is how computers accomplish stuff. The STL containers help you do it fast and efficiently, with very few lines of code. Like this:
Create a std::map keyed by whatever it is that makes a vertex redundant
LOOP V over vertices
Insert V into the map( which will reject redundant vertices )
LOOP V over the completed map
Insert the non redundant vertices into boost:graph
CodePudding user response：
To make @ravenspoint's suggestion concrete, I'd flip it around a bit:
LOOP over waypoints, creating vertices for each unseen coordinate, storing a mapping point→vertex_descriptor.
LOOP over linestrings, looking up the previously mapped vertices
#include <boost/json/src.hpp>
#include <iostream>
namespace json = boost::json;
using json::value_from;
using coord = double;
struct point {
coord x, y;
auto operator<=>(point const&) const = default;
friend std::ostream& operator<<(std::ostream& os, point const& p) {
return os << "(" << p.x << "," << p.y << ")";
}
friend void tag_invoke(json::value_from_tag, json::value& jv, point const& p) {
jv = {value_from(p.x), value_from(p.y)};
}
friend point tag_invoke(json::value_to_tag<point>, json::value const& jv) {
auto& arr = jv.as_array();
return {arr[0].as_double(), arr[1].as_double()};
}
};
using linestring = std::vector<point>;
struct feature {
intmax_t id;
linestring geom;
friend void tag_invoke(json::value_from_tag, json::value& jv, feature const& f) {
jv = {{"type", "Feature"},
{"properties", {"id", f.id}},
{
"geometry",
{
{"type", "LineString"},
{"coordinates", value_from(f.geom)},
},
}};
}
friend feature tag_invoke(json::value_to_tag<feature>, json::value const& jv) {
assert(jv.at("type") == "Feature");
auto& props = jv.at("properties").as_object();
auto& geom = jv.at("geometry").as_object();
assert(geom.at("type") == "LineString");
return {
props.at("id").as_int64(),
json::value_to<linestring>(geom.at("coordinates")),
};
}
};
using features = std::vector<feature>;
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
struct Legs {
int id;
double distance;
};
using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
point, Legs>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
int main() {
auto ff = value_to<features>(json::parse(R"([
{"type": "Feature", "properties": {"id": 1}, "geometry": { "type": "LineString", "coordinates": [ [ 147.0, -4.8 ], [ 141.0, -2.0 ] ]}},
{"type": "Feature", "properties": {"id": 2}, "geometry": { "type": "LineString", "coordinates": [ [ 152.6, -5.2 ], [ 152.05, -3.8 ], [ 147.0, -4.8 ] ] } },
{"type": "Feature", "properties": {"id": 3}, "geometry": { "type": "LineString", "coordinates": [ [ 147.0, -4.8 ], [ 144.73, 0.0 ] ] } }
])"));
G g;
std::map<point, V> mapping;
// create a mapping for all vertices
for (auto& f : ff)
for (auto& p : f.geom)
if (auto it = mapping.find(p); it == mapping.end())
mapping.emplace(p, add_vertex(p, g));
int next_edge_id = 0;
for (auto& f : ff) {
auto waypoints = boost::make_iterator_range(f.geom);
if (waypoints.empty())
continue;
V s = mapping.at(waypoints.front()), t;
for (; waypoints.pop_front(), !waypoints.empty(); s = t) {
t = mapping.at(waypoints.front());
auto dx = g[t].x- g[s].x;
auto dy = g[t].y- g[s].x;
add_edge(s, t, Legs{next_edge_id , sqrt(dx * dx dy * dy)}, g);
}
}
print_graph(g, get(boost::vertex_bundle, g));
}
Prints
(147,-4.8) <--> (141,-2) (152.05,-3.8) (144.73,0)
(141,-2) <--> (147,-4.8)
(152.6,-5.2) <--> (152.05,-3.8)
(152.05,-3.8) <--> (152.6,-5.2) (147,-4.8)
(144.73,0) <--> (147,-4.8)
CAVEAT
Keep in mind floating point inexactness. You might want to implement operator< differently for point so that Very Close Points(TM) may be treated as identical.