===============================================================================
Title: mpt_optMergeDivCon
Project: Optimal merging of a set of polyhedra using divide and
conquer strategy
Input: PA: polyhedral array
Opt: Options with the following fields
.color: color of polyhedra
This is an integer 1,2,... The algorithm will merge
polyhedra with the same color. If color is not specified, it
is assumed to be 1 for all polyhedra.
.PAdom:
the set of polyhedra (the so called domain) the problem is
defined in. If not given, the algorithm assumes the domain is
given by the hull (or envelope if the hull computation fails)
of PA.
.PAcompl:
polyhedral array that is within the domain and not
in PA - it is the so called complement. If not specified,
the algorithm assumes PAcompl is empty. Then the
complement is filled up optimally by the merging algorithm.
Refer also to the second remark below.
.verbose:
0: silent (=default)
1: verbose only important information
2: verbose everything
.algo:
0: overlapping merging (boolean minimization)
[1, inf]: optimal merging, with the given upper bound on nodes
(default is inf)
.maxHA: [1, inf]: maximal number of hyperplanes for which we
can compute the markings for sub1 or 2 (default inf)
.maxHA_sub1and2: [1, inf]: maximal number of hyperplanes for
which we can compute the markings for the combined problem
of sub1 and 2 (default maxHA+10)
.divideSub:
0: use an artificial hyperplane parallel to axis of the
coordinate with the longest edge of the bounding box to
divide a problem into 2 subproblems (fast)
1: go through all hyperplanes, choose the one that minimizes
the cost abs(# GL in Sub1 - # GL in Sub2) + # GL in Sub1 + # GL in Sub2 (slow) (=default)
.tol.simplifyHA: 1-norm of cluster of hyperplanes from center
clustering is done in order to simplify the hyperplane
arrangement and to thus reduce the complexity of the
solution. Clustering is beneficial, if we have many
hyperplanes that are almost the same. Then we can take a
weighted average of such a cluster. When the tolerance is
0, no clustering is performed.
Output: PAmer: merged polyhedra array
colorMer: colors with the following fields
.Reg: color of each region
.Table: regions with the same color
Author: Tobias Geyer <geyer@control.ee.ethz.ch>
Remarks: some important remarks and explanations:
* the input polyhedral array may be overlapping
First, we identify all existing hyperlanes, remove unecessary ones,
and compute then the markings in the hyperplane arrangement. Then,
we identify the colors of the cells in the arrangement by chosing
one cell, getting the center of it and then identifying the
polyhedron in PA that includes the center. Thus overlaps do not matter.
* the input polyhedral array may contain small holes
Holes may always occur (also in the hyperplane arrangement based on
which we merge). Holes are assigned to 'don't cares' and are filled
with neighbouring polyhedra. Acutally, to reduce complexity, we remove
very small cells (say with radii < 1e-5) from the arrangement. These
are then 'don't cares'.
* we keep in the hyperplane arrangment only hyperplanes that are facets
of polyhedra with different colors
These hyperplanes separate the colors. Shouldn't we keep also the other
hyperplanes? No, as we are allowing for overlapping polyhedra (merging
based on boolean minimization), we only need these 'dividing' hyperplanes.
Adding additional hyperplanes does not reduce the number of resulting
polyhedra. Proof?
* we plan to later allow to also simplify the hyperplanes, i.e. to
aggregate similar hyperplanes in only one.
History: date ver. subject
2004.06.16 1.0 initial version based on mpt_iterMerge
2004.07.14 1.1 divide problem into subproblems using 'best' hyperplane
2005.07.20 1.2 improved help
Requires: mpt_exHyperAdv,
espresso or merge5,
plotPaCol,
mpt2cell,
MPT toolbox
Contact: Tobias Geyer
Automatic Control Laboratory
ETH Zentrum, CH-8092 Zurich, Switzerland
geyer@control.ee.ethz.ch
Comments and bug reports are highly appreciated
===============================================================================