Berger-Rigoutsos clustering: tag grid -> small set of boxes covering the tagged cells. More...

#include <pops/amr/tagging/tag_box.hpp>
#include <pops/mesh/index/box2d.hpp>
#include <pops/mesh/layout/box_array.hpp>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>

Include dependency graph for cluster.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	pops::ClusterParams
	Berger-Rigoutsos clustering parameters (configuration object). More...

Namespaces
namespace	pops

namespace	pops::detail

Functions
Box2D	pops::detail::tag_bbox (const TagBox &tb, const Box2D &region)
	Bounding box of the tagged cells in region; empty box (hi < lo) if none is tagged.

long	pops::detail::count_in (const TagBox &tb, const Box2D &r)
	Number of tagged cells in box r.

std::vector< long >	pops::detail::signature (const TagBox &tb, const Box2D &r, int axis)
	Signature of r along axis: number of tagged cells per column (axis 0) or per row (axis 1).

int	pops::detail::best_hole (const std::vector< long > &s, int mb)
	Interior hole (zero signature) closest to the center, in [mb, len-mb]; -1 if none.

int	pops::detail::best_inflection (const std::vector< long > &s, int mb, long &score)
	Inflection: index of the max \|D[k] - D[k-1]\| with D the discrete Laplacian of the signature, in the valid range; -1 if none.

void	pops::detail::cluster_rec (const TagBox &tb, Box2D region, const ClusterParams &p, std::vector< Box2D > &out)
	Berger-Rigoutsos recursive core: trim, accept if efficient/not splittable, otherwise cut and recurse.

std::vector< Box2D >	pops::berger_rigoutsos (const TagBox &tags, const ClusterParams &p={})
	Cluster a TagBox into boxes covering the tagged cells (Berger-Rigoutsos), then final chop.

Detailed Description

Berger-Rigoutsos clustering: tag grid -> small set of boxes covering the tagged cells.

Layer: include/pops/amr (AMR geometric primitives). Role: cluster the tagged cells (TagBox) into a reduced number of boxes with good efficiency (fraction of tagged cells inside the boxes), to define the patches of a fine level. Contract: pure, sequential, no physics nor MPI; consumes an already gathered TagBox.

Recursion:

trim the region to the bounding box of the tags (trim);
if efficiency >= threshold, or region not splittable -> accept the box;
otherwise pick a cut: hole (empty column/row) first, otherwise inflection (max of the Laplacian change of the signature), otherwise midpoint;
recurse on the two halves. Then final chop according to max_box_size.

include/pops/amr/tagging/cluster.hpp File Reference¶

Classes

Namespaces

Functions

Detailed Description