Structure to store Z-ordered shapes
Hi all,
I would like to know what structure do you use to store shapes in Z-order. It seems to me that a simple linked list would perform poorly for a large number of shapes, since it has a time complexity of O(n) to find the index (the z-value) of a shape.
So, I was thinking at two other structures. The first one would be similar to a linked list except that each node would store its own z value. However, since the Z order is only a "less than or equal to" relation, Z values don't need to be equal to their index in the list or even be continuous. So, this class would not waste time to reuse the indices from removed/moved shapes. Operations like add-last, bring-to-front, send-to-back would allocate a new Z-value each time they are called. And operations like remove would not adjust the indices of the other nodes. So, all operations would perform in O(1) time cost!
However there is a disavantage of not resuing indice. This class cannot perform an illimited number of some operations (because these operations allocate a new Z value each time they are called). However, this should not be a limitation in real world applications, because that I would be surprised that a user performs more than 2^31 operations (for an integer z value). Another disavantage is that it's not possible to know the real value of the Z order; a Z value makes sence only by comparing it with another.
The second structure doesn't have these limitations but it's more complex to implement and a little bit less performant. This structure is a balanced tree where the predicate to insert a node is the in-order index in the tree. The main idea is that the index of a node (thus it's Z value) can be computed by traversing the tree upward to the root, thus in O(log n). So, the nodes don't have to keep its own Z value, and don't need to adjust them. All other operations perform in amortized O(1), since we may need to make some rotations to balance the tree, which should be really fast in practice.
Note that these structures assume that a shape *is* a node, i.e. having a reference on a shape means that we have a reference on the node. Thus, we don't need to find the node corresponding to a given shape.
What so you think of these structures? What structure InkScape actually uses?
Thanks for your comments, Jean
---------- Forwarded message ---------- From: Jean Morissette <jean.morissette@...400...> Date: 13 oct. 2006 15:47 Subject: Structure to store Z-ordered shapes To: inkscape-devel@lists.sourceforge.net
Hi all,
I would like to know what structure do you use to store shapes in Z-order. It seems to me that a simple linked list would perform poorly for a large number of shapes, since it has a time complexity of O(n) to find the index (the z-value) of a shape.
So, I was thinking at two other structures. The first one would be similar to a linked list except that each node would store its own z value. However, since the Z order is only a "less than or equal to" relation, Z values don't need to be equal to their index in the list or even be continuous. So, this class would not waste time to reuse the indices from removed/moved shapes. Operations like add-last, bring-to-front, send-to-back would allocate a new Z-value each time they are called. And operations like remove would not adjust the indices of the other nodes. So, all operations would perform in O(1) time cost!
However there is a disavantage of not resuing indice. This class cannot perform an illimited number of some operations (because these operations allocate a new Z value each time they are called). However, this should not be a limitation in real world applications, because that I would be surprised that a user performs more than 2^31 operations (for an integer z value). Another disavantage is that it's not possible to know the real value of the Z order; a Z value makes sence only by comparing it with another.
The second structure doesn't have these limitations but it's more complex to implement and a little bit less performant. This structure is a balanced tree where the predicate to insert a node is the in-order index in the tree. The main idea is that the index of a node (thus it's Z value) can be computed by traversing the tree upward to the root, thus in O(log n). So, the nodes don't have to keep its own Z value, and don't need to adjust them. All other operations perform in amortized O(1), since we may need to make some rotations to balance the tree, which should be really fast in practice.
Note that these structures assume that a shape *is* a node, i.e. having a reference on a shape means that we have a reference on the node. Thus, we don't need to find the node corresponding to a given shape.
What so you think of these structures? What structure InkScape actually uses?
Thanks for your comments, Jean
Quoting Jean Morissette <jean.morissette@...400...>:
Hi all,
I would like to know what structure do you use to store shapes in Z-order. It seems to me that a simple linked list would perform poorly for a large number of shapes, since it has a time complexity of O(n) to find the index (the z-value) of a shape.
[SNIP]
What so you think of these structures? What structure InkScape actually uses?
Just look at the source code, it's publically available.
The main thing is that SVG does not use a simple list of objects, but instead is a tree structure, like most XML-based formats.
participants (2)
-
unknown＠example.com -
Jean Morissette