9:23 p.m.
I'm not sure where in the source tree to look for this, so I'll ask this here.
What container does Inkscape use to store the nodes of its paths? I
mean, a drawing program would often use (in STL terminology)
push_back, pop_back, insert and erase. (I don't think push_front would
often be needed.) The contained value type would probably contain a
few flags in addition to the x,y coordinates. So I'm curious what
container you people chose to cater to these requirements.
Thanks.
--
Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा
11 p.m.
2013/4/22 Shriramana Sharma <samjnaa@...400...>:
I'm not sure where in the source tree to look for this, so
I'll ask this here.
What container does Inkscape use to store the nodes of its paths? I
mean, a drawing program would often use (in STL terminology)
push_back, pop_back, insert and erase. (I don't think push_front would
often be needed.) The contained value type would probably contain a
few flags in addition to the x,y coordinates. So I'm curious what
container you people chose to cater to these requirements.
I wrote a custom container based on boost::intrusive::list. This kind
of container works like a doubly-linked list and additionally allows
one to obtain an iterator from a reference to an element in constant
time, which is a very common operation required in Inkscape.
Regards, Krzysztof
2:23 a.m.
Hello and thanks for replying.
On Mon, Apr 22, 2013 at 7:30 PM, Krzysztof Kosiński <tweenk.pl@...972.....> wrote:
I wrote a custom container based on boost::intrusive::list.
Can you please point me to the exact location of this template in the
source code? And is it like tied into Inkscape's internals in any way
or easily adaptable to other value types.
This kind
of container works like a doubly-linked list and additionally allows
one to obtain an iterator from a reference to an element in constant
time, which is a very common operation required in Inkscape
Why would one want that particularly in a vector editing application?
Thanks for your patient replies.
--
Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा
12:59 a.m.
2013/4/22 Shriramana Sharma <samjnaa@...400...>:
Hello and thanks for replying.
On Mon, Apr 22, 2013 at 7:30 PM, Krzysztof Kosiński <tweenk.pl@...847...0...>
wrote:
> I wrote a custom container based on boost::intrusive::list.
Can you please point me to the exact location of this template in the
source code? And is it like tied into Inkscape's internals in any way
or easily adaptable to other value types.
src/ui/tool/node.h and .cpp, class NodeList.
Note that this is not a template. It's "based on"
boost::intrusive::list in the sense that the structure is the same -
it doesn't actually use it. It would require some work to adapt it for
use outside of Inkscape.
> This kind
> of container works like a doubly-linked list and additionally allows
> one to obtain an iterator from a reference to an element in constant
> time, which is a very common operation required in Inkscape
Why would one want that particularly in a vector editing application?
The list members are control points and receive GUI events through
callbacks, which are their member functions. You need to be able to
get an iterator to the element from the reference to the element
itself, because the element reference is all you've got within the
callback. (This sounds a little convoluted but I hope you get the
idea.)
Regards, Krzysztof
10:52 p.m.
On Tue, Apr 23, 2013 at 9:29 PM, Krzysztof Kosiński <tweenk.pl@...972.....> wrote:
src/ui/tool/node.h and .cpp, class NodeList.
Note that this is not a template. It's "based on"
boost::intrusive::list in the sense that the structure is the same -
it doesn't actually use it.
Hi Krzysztof,
A few more questions regarding this:
1) A doubly-linked list is costly in terms of having to store the prev
and next pointers per item. This cost is justified if the item-size is
quite greater than the size of two pointers. Is that true in case of
the Inkscape path nodes? Other than the X, Y coords, what other data
would you store per node?
2) From what I could learn from the code, it seems as if you store
off-curve i.e. handle points separately as part of the linked list and
not as adjuncts of on-curve points, i.e. for a single cubic bezier you
would have:
p1 (x,y,prev,next)
c1 (x,y,prev,next)
c2 (x,y,prev,next)
p2 (x,y,prev,next)
and not something like:
p1 (x, y, pre.x, pre.y, post.x, post.y, prev, next)
p2 (pre.x, pre.y, point.x, point.y, post.x, post.y, prev, next)
Is that right? This allows you to cut down the storage requirements in
case of linear segments but at significant cost (many more prev,next)
pointers in case of cubic segments. Was the tradeoff found acceptable?
Thanks!
--
Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा
6:46 a.m.
2013/7/6 Shriramana Sharma <samjnaa@...400...>:
On Tue, Apr 23, 2013 at 9:29 PM, Krzysztof Kosiński
<tweenk.pl@...847...0...> wrote:
> src/ui/tool/node.h and .cpp, class NodeList.
> Note that this is not a template. It's "based on"
> boost::intrusive::list in the sense that the structure is the same -
> it doesn't actually use it.
Hi Krzysztof,
A few more questions regarding this:
1) A doubly-linked list is costly in terms of having to store the prev
and next pointers per item. This cost is justified if the item-size is
quite greater than the size of two pointers. Is that true in case of
the Inkscape path nodes? Other than the X, Y coords, what other data
would you store per node?
The trivial "cost" of two pointers is justified, because many
algorithms operating on the nodes require the ability to insert /
delete nodes at arbitrary positions and to splice two node lists
together. These operations are constant time on a list, but linear
time on a vector.
The nodes also store attributes related to their appearance and type.
2) From what I could learn from the code, it seems as if you store
off-curve i.e. handle points separately as part of the linked list and
not as adjuncts of on-curve points, i.e. for a single cubic bezier you
would have:
p1 (x,y,prev,next)
c1 (x,y,prev,next)
c2 (x,y,prev,next)
p2 (x,y,prev,next)
and not something like:
p1 (x, y, pre.x, pre.y, post.x, post.y, prev, next)
p2 (pre.x, pre.y, point.x, point.y, post.x, post.y, prev, next)
Is that right? This allows you to cut down the storage requirements in
case of linear segments but at significant cost (many more prev,next)
pointers in case of cubic segments. Was the tradeoff found acceptable?
No, you must have misunderstood the code. Each Inkscape::UI::Node has
two Inkscape::UI::Handle members, regardless of the type of the node.
Handles are not stored in the linked list.
Before 0.48, the old node tool did store the handles in a linked list
together with the nodes.
Regards, Krzysztof
3615
days inactive
3690
days old
inkscape-devel@lists.inkscape.org
5 comments
2 participants
participants (2)
-
Krzysztof Kosiński -
Shriramana Sharma