QGAL: vertex simplification

Some vertices are connected by anchors with size 0, which means that
in practice, they represent the same point when positioning items,
i.e. their distance value is the same. In those cases, we can merge the two
anchors in one, that's what vertex simplification do.

The algorithm is walking in the graph, merging vertices in pairs (this could be enhanced to allow groups with arbitrary number of children vertices)

The vertex simplification stage happens before the anchor
simplification, so it'll make less passes. Also, in some situations of
redudant anchors it will allow more anchors to be simplified.

This commit creates a new type of AnchorVertex, add the algorithm
for vertex simplification and restoration, make sure that distribution also
works with simplified vertices.

Consequences:

 - the assert after creating a sequence might not be true anymore, it
   was a structural assumption that vertex simplification may destroy;

 - we assumed that a center anchor could appear only in the beginning
   or end of the candidates, because the "center vertex" always would
   have 3 adjacents. A mix of parallel+center and vertex
   simplification break that assumption.

The commit deal with those consequences.

We still have one limitation: vertex simplification needs to restore
the graph in every invalidation (which might be caused by some child's
updateGeometyry()), since a change in the sizeHint might cause a new
anchor to have size 0 or a 0-sized anchor to have a different size. In
the future we can track the 0 sized anchors and only
restore/re-simplify when the set changes.

Signed-off-by: Caio Marcelo de Oliveira Filho <caio.oliveira@openbossa.org>
Reviewed-by: Eduardo M. Fleury <eduardo.fleury@openbossa.org>

0 files changed, 0 insertions, 0 deletions