geos::operation::spanning::SpanningTree Class Reference

Constructs a Minimum Spanning Tree (MST) from a set of Curves. More...

#include <SpanningTree.h>

Static Public Member Functions
static void	mst (const std::vector< const geom::Curve * > &curves, std::vector< std::size_t > &result)
	Computes the Minimum Spanning Tree of the given Curves.

Detailed Description

Constructs a Minimum Spanning Tree (MST) from a set of Curves.

The input is a vector of Curves (LineString, CircularString, CompoundCurve) which form the edges of a graph. The nodes of the graph are the endpoints of the Curves. Coincident endpoints are treated as the same node.

The algorithm uses Kruskal's algorithm to find the MST.

Member Function Documentation

mst()

static void geos::operation::spanning::SpanningTree::mst ( const std::vector< const geom::Curve * > &  curves, std::vector< std::size_t > &  result  )

static

Computes the Minimum Spanning Tree of the given Curves.

Parameters

curves	Input vector of Curves.
result	Output vector of size_t. 0 if the edge is not in the MST. Values > 0 indicate the component ID of the subtree the edge belongs to. The vector will be resized to match the input size.

---

The documentation for this class was generated from the following file:

• SpanningTree.h