Greedy palette packing algorithm using weighted cost optimization. More...

#include <best_fusion_strategy.hpp>

Inheritance diagram for porytiles::BestFusionStrategy:

Collaboration diagram for porytiles::BestFusionStrategy:

Public Member Functions
	BestFusionStrategy ()=default

ChainableResult< PackingOutput >	pack (const PackingInput &input) const override
	Packs tiles into palettes using the Best Fusion algorithm.

std::string	name () const override
	Returns the name of this strategy.

Public Member Functions inherited from porytiles::PackingStrategy
virtual	~PackingStrategy ()=default

Detailed Description

Greedy palette packing algorithm using weighted cost optimization.

BestFusionStrategy implements a greedy algorithm for palette packing based on the "Best Fusion" approach. For each tile, it computes the "weighted cost" of placing the tile in each candidate palette and selects the one with minimal cost.

The weighted cost for placing a tile in a palette is computed as: sum(1 / multiplicity[color]) for each color in the tile

where multiplicity[color] is the number of tiles that use that color. This rewards placing tiles in palettes where their colors are shared by many other tiles, maximizing color reuse and minimizing the number of palettes needed.

If the weighted cost is less than the tile's color count (indicating good color sharing), the tile is added to the best palette. Otherwise, a new palette is created.

This algorithm is based on insights and samples from:

Grange, A., Kacem, I., & Martin, S. (2018). Algorithms for the bin packing problem with overlapping items. Computers & Industrial Engineering, 115, 331–341. https://doi.org/10.1016/j.cie.2017.10.015 https://arxiv.org/pdf/1605.00558

Definition at line 32 of file best_fusion_strategy.hpp.

Constructor & Destructor Documentation

◆ BestFusionStrategy()

porytiles::BestFusionStrategy::BestFusionStrategy ( )

default

Member Function Documentation

◆ name()

std::string porytiles::BestFusionStrategy::name ( ) const

inlineoverridevirtual

Returns the name of this strategy.

Returns: "Best Fusion"

Implements porytiles::PackingStrategy.

Definition at line 49 of file best_fusion_strategy.hpp.

◆ pack()

ChainableResult< PackingOutput > porytiles::BestFusionStrategy::pack ( const PackingInput & input ) const

overridevirtual

Packs tiles into palettes using the Best Fusion algorithm.

Parameters

input The packing input containing tiles, hints, fixed slots, and constraints

Returns: A PackingOutput on success, or an error if packing fails