A data structure for vector drawing?

Learn
1

Think of the application Inkscape, if you know it, but other drawing software may have similar features. In Inkscape you can select some visual elements in a drawing and group them. Once grouped, they select and move as a unit. Groups can also be incorporated into other groups. When a group is ungrouped, its elements are pulled back to the top-level of the drawing (any child groups are not broken up, only promoted to back to the top-level as groups).

At the moment I represent this something like this:

type alias Drawing =
    { elements : Dict String Element
    , order : Int
    }

type Element 
    = Box ...
    | Line ...
    | AndOtherShapes ...
    | Group Drawing

So its a tree with Dicts inside Dicts whenever there is a group node, and all the other shapes as leafs in the tree.

Disadvantages are:

  • When looking for an element by id, it may be necessary to iterate over and scan all the groups, losing the O (log n) efficiency of a simple Dict.

  • Elements are given an order value which should be unique and determines in what order shapes are drawn, back to front. When items are moved into a group this value is preserved. When re-ordering elements it becomes difficult to avoid clashing with order values inside groups. When ungrouping it becomes difficult to ensure that there will still be space within the numbering to re-insert the de-grouped items.

Its definitely a tree. Just wondering if anyone might have any thoughts on whether there are better ways to manage this kind of drawing data with groups.

2

SVG offers a glimpse as to how this could all work in terms of what data to track. For Elm inspiration, take a look at elm-playground. In short, there is a Shape type that keeps track of transformations and the “form” of the shape: Circle, Square … and Group.

As for lookup via ID. The (wonderful) paper “Out of the Tar Pit” makes a distinction between data/data-structure that we NEED “essential complexity” and the stuff that is nice for a specific deployment/integration/optimization/etc “accidental complexity”. Importantly: essential complexity should never know about accidental complexity.

So, model the essential data as it is (a tree). For performance, if needed, have another data-structre keyed by ID to locate items quickly.

2 Likes
3

Nice idea thanks. Basically use a Dict as the source of truth to hold the actual element data by id. And then structure the ids into some kind of tree reflecting how they are grouped:

type alias Drawing = 
    { elements : Dict String Element
    , structure : Tree String
    }

type Element 
    = Box ...
    | Line ...
    | AndOtherShapes ...
    -- No need for a Group constructor, grouping is described by the explicit tree.

Group/Ungroup operations just only the tree. Changes to element data can proceed efficiently against the dict.

4

“No need for a Group constructor” - though a group can also have an id and semantically serve as an Element.

Also, I wonder what use case benefits from the quick lookup, because in rendering and picking (point and select) - I guess accounting for most operations - you need to walk through the structure anyway. I am probably missing an important case, or the example might be simplified (where there is more to Element than only a simple shape).

5

But also a Group should never be a leaf in the tree, since it must always contains >=2 elements. So perhaps instead, use a Tree implementation that allows different data types at node/leaf positions:

type alias Drawing =
    { elements : Dict String Element
    , structure: Tree Group String
    }

But now I maybe need another Dict to lookup Groups by…? But I do like the way it helps to enforce correct grouping invariants by not allowing groups at the leaf position.

6

Maybe if a user clicks and drags on something. We know its id, and want to update its position. So ideally its a quick lookup by id and change the .pos property, and avoid walking the whole tree just to do that kind of update.

Tree walking would only be needed for adding/removing drawing elements, changing z-order of elements, and group/ungroup operations.

7

Ah, of course, I see, occlusion (in rendering) you don’t need the tree structure for, only the order of elements drawn back to front.
An additional case where you need the grouping is when transforming a group in its entirety.

8

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.