Struct MultiJagged 

pub struct MultiJagged {
    pub part_count: usize,
    pub max_iter: usize,
}

Multi-Jagged algorithm

This algorithm is inspired by Multi-Jagged: A Scalable Parallel Spatial Partitioning Algorithm“ by Mehmet Deveci, Sivasankaran Rajamanickam, Karen D. Devine, Umit V. Catalyurek.

It improves over RCB by following the same idea but by creating more than two subparts in each iteration which leads to decreasing recursion depth. It also allows to generate a partition of any number of parts.

More precisely, given a number of parts, the algorithm will generate a “partition scheme”, which describes how to perform splits at each iteration, such that the total number of iteration is less than max_iter.

More iteration does not necessarily result in a better partition.

Example

use coupe::Partition as _;
use coupe::Point2D;

let points = vec![
    Point2D::new(0., 0.),
    Point2D::new(1., 0.),
    Point2D::new(2., 0.),   
    Point2D::new(0., 1.),
    Point2D::new(1., 1.),
    Point2D::new(2., 1.),
    Point2D::new(0., 2.),
    Point2D::new(1., 2.),
    Point2D::new(2., 2.),
];
let weights = [4.2; 9];
let mut partition = [0; 9];

// generate a partition of 4 parts
coupe::MultiJagged { part_count: 9, max_iter: 4 }
    .partition(&mut partition, (&points, &weights))
    .unwrap();

for i in 0..9 {
    for j in 0..9 {
        if j == i {
            continue    
        }
        assert_ne!(partition[i], partition[j])
    }
}

Fields

part_count: usize

max_iter: usize

Trait Implementations

impl<'a, const D: usize> Partition<(&'a [Matrix<f64, Const<D>, Const<1>, ArrayStorage<f64, D, 1>>], &'a [f64])> for MultiJagged

type Metadata = ()

Diagnostic data returned for a specific run of the algorithm.

type Error = Infallible

Error details, should the algorithm fail to run.

fn partition( &mut self, part_ids: &mut [usize], (points, weights): (&'a [PointND<D>], &'a [f64]), ) -> Result<Self::Metadata, Self::Error>

Partition the given data and output the part ID of each element in part_ids.