packing_metrics.hpp File Reference

Metrics for Bin Packing with Overlapping Items (Pagination problem). More...

#include <cstddef>
#include <map>
#include <vector>
#include "porytiles/domain/models/color_set.hpp"
#include "porytiles/domain/packing/models/packable_tile.hpp"
#include "porytiles/domain/packing/models/packed_palette.hpp"

Include dependency graph for packing_metrics.hpp:

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

Go to the source code of this file.

Namespaces
namespace	porytiles

Functions
std::map< std::size_t, std::size_t >	porytiles::build_global_multiplicity_map (const std::vector< PackableTile > &tiles, const std::vector< PackableTile > &hints)
	Builds a GLOBAL multiplicity map from all input tiles.
double	porytiles::compute_average_multiplicity (const std::vector< PackableTile > &tiles, const std::vector< PackableTile > &hints)
	Computes the average multiplicity of the input tiles (problem difficulty metric).
std::map< std::size_t, std::size_t >	porytiles::build_palette_local_multiplicity (const PackedPalette &palette, const std::map< PackableTile::Id, ColorSet > &tile_colors_map)
	Builds a PALETTE-LOCAL multiplicity map for a specific palette.
double	porytiles::compute_weighted_cost_in_palette (const ColorSet &tile_colors, const PackedPalette &palette, const std::map< PackableTile::Id, ColorSet > &tile_colors_map)
	Computes the weighted cost of placing a tile in a specific palette.
double	porytiles::compute_palette_local_efficiency (const ColorSet &tile_colors, const std::map< std::size_t, std::size_t > &local_mult)
	Computes the palette-local efficiency of a tile within its palette.
double	porytiles::compute_weighted_cost_in_palette_fast (const ColorSet &tile_colors, const PackedPalette &palette)
	Computes the weighted cost of placing a tile in a palette using cached counts.
double	porytiles::compute_palette_local_efficiency_fast (const ColorSet &tile_colors, const PackedPalette &palette)
	Computes the palette-local efficiency of a tile using cached counts.

Detailed Description

Metrics for Bin Packing with Overlapping Items (Pagination problem).

This module provides metrics for the "Bin Packing with Overlapping Items" problem (also called the "Pagination" problem), as described in:

‍Grange, Kacem, Martin. "Algorithms for the Bin Packing Problem with Overlapping Items" (2017) - https://arxiv.org/abs/1605.00558

CRITICAL DISTINCTION: Global vs Palette-Local Multiplicity

1. GLOBAL MULTIPLICITY (build_global_multiplicity_map, compute_average_multiplicity)

• Counts how many tiles across ALL INPUT TILES contain each color
• Computed ONCE at the start of packing
• DOES NOT vary per palette
• Use cases:
  • Problem difficulty estimation: Average multiplicity (Card(T)/|A|) correlates strongly (r=0.784) with problem difficulty per Section 4.3 of Grange et al.
  • Algorithm selection: Different algorithms perform better at different multiplicity ranges (Section 4.4.2):
    • Low multiplicity (<15): Overload-and-Remove competitive with genetic algorithms
    • Medium multiplicity (15-35): Overload-and-Remove decent, genetic algorithms better
    • High multiplicity (35-40): Greedy algorithms become competitive
    • Very high multiplicity (>40): Best Fusion optimal for speed/quality tradeoff

2. PALETTE-LOCAL MULTIPLICITY (build_palette_local_multiplicity)

• Counts how many tiles within a SPECIFIC PALETTE contain each color
• Computed PER-PALETTE, dynamically as tiles are added/removed
• VARIES per palette (each palette has different tiles assigned)
• Use case: Measuring color overlap when placing a tile in a palette

Warning

The Best Fusion and Overload-and-Remove algorithms require PALETTE-LOCAL multiplicity to make placement decisions. Using global multiplicity would cause all palettes to appear equally good, defeating the algorithm's purpose.

See also

BestFusionStrategy Uses palette-local cost for tile placement

OverloadAndRemoveStrategy Uses palette-local cost and efficiency for placement/removal

Definition in file packing_metrics.hpp.