[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: