[haiku-appserver] Re: Going "back" & clipping
- From: Ingo Weinhold <bonefish@xxxxxxxxxxxxxxx>
- To: haiku-appserver@xxxxxxxxxxxxx
- Date: Wed, 20 Apr 2005 15:21:20 +0200 (MEST)
On Wed, 20 Apr 2005, Stephan Assmus wrote:
[...]
> As for doing the in-place copy of all the rects in a BRegion in the
> correct order, I have already contacted Stefano in privat (because he
> wrote BRegion). If anybody else has an idea for a fast topological
> sorting algorithm, feel free to speak up! :-) To learn more about the
> problem, read the extensive comment above src/servers/app/drawing/
> DisplayDriverPainter::CopyRegionList().
I probably don't have a perfect solution, but it strikes me that this
problem looks similar to topologically sorting directed acyclic graphs
(DAGs), for which a beautiful solution by Tarjan exists.
For those not familar with graphs, a directed graph consists of a set of
nodes (aka vertices) and directed edges (aka arcs or arrows) between the
nodes. If there's no cycle in the graph (i.e. no path along the edges
that ends where is started), it's a DAG.
Topologically sorting the nodes of a DAG means to enumerate the nodes such
that for any two nodes one may be enumerated before the other if and only
if there is no path along the edges from the latter to the former. Or
formulated differently, if you remove the nodes one after the other in the
order they are enumerated (and the incident edges with them) you would
always only remove a node that has no ingoing edges.
This is pretty much already the idea of Tarjan's algorithm. The
representation of the graph should be a set per node containing the nodes
the node has outgoing edges to. First the algorithm counts the number of
ingoing edges for each node (aka indegree). It maintains a set (a list or
stack is sufficient) of nodes with indegree 0. It picks one of those
nodes and removes it from the graph, decrementing the indegrees of
adjacent nodes, putting those whose indegree dropped to 0 into the set.
This goes on until the 0 indegree set is empty, which in case of a DAG
only happens, when all nodes have been removed. If there are still nodes,
the remaining subgraph(s) is/are cyclic.
Back to the problem of topologically sorting non-overlapping rectangles:
If you consider the rectangles nodes and add edges respective to their
horizontal and vertical relationship, topologically sorting the nodes
sorts the rectangles as required. In case of left->right, top->bottom
moving for any pair of nodes you would add an edge when one rect is
to the right or to the bottom of the other. If both is the case, but with
opposite directions (as for A and B in your example) neither edge is added
(the order between the two rects shouldn't matter).
Unfortunately the complexity is O(n^2) here, but I actually think we can't
do faster, anyway. At least not when considering the dimensions
separately. Maybe one can use the fact that the rectangles don't overlap
to reduce the complexity, but I don't see how.
CU, Ingo
Other related posts:
