MPT_GREEDYMERGING Greedy merging of polyhedra
===============================================================================
Title: greedyMerging.m
Project: merging of polyhedra
Inputs: PolyIn: set of polytopes either
as an array of polytopes using the MPT toolbox, or
or as a structure using the halfspaces description Hi*x <= Ki
Options (optional):
multiple: 0: one loop
1: do multiple merging loops until no improvement (default)
trials: 0: one trial (default)
>0: do multiple trials. If a better solution is found,
reset the counter to zero
verbose: 0: verbosity off
1: verbosity on (default)
union.lpsolver: LP solver used when computing the union
0: NAG Toolbox (default)
1: Matlab's linprog
union.tolerance: tolerance when computing the union
1e-6 (default)
union.reduce: reduce union to minimal representation
0: no (default)
1: yes
Outputs: PolyOut: set of merged polytopes either
as an array of polytopes using the MPT toolbox, or
or as a structure using the halfspaces description Hi*x <= Ki.
The tool choses the same representation as for PolyIn
Comments: The algorithm tries to merge as many of the given polyhedra as
possible using a greedy approach. The algorithm cycles through
the regions and checks if any two regions form a convex union.
If so, the algorithm combines them in one region, and continues
checking the remaining regions.
To improve the solution, multiple merging loops are enabled
by default.
To reduce the problem of getting stuck in local minima, several
trials can be used until the solution is not improved.
Author: Tobias Geyer
History: date subject
2004.01.16 initial version based on mb_reducePWA by Mato Baotic
2004.05.06 debugged, comments added
Requires: multi parametric toolbox MPT,
mb_buildBClist
cell2mpt, mpt2cell,
mb_polyunion,
facetinnercircle
Contact: Tobias Geyer
Automatic Control Laboratory
ETH Zentrum,
Zurich, Switzerland
geyer@control.ee.ethz.ch
Comments and bug reports are highly appreciated
===============================================================================