Once again, another week spent trying to make distribution snapping better in Inkscape!

This blog is meant to give a high level description of how Distribution snapping is implemented as of now.

“The Algorithm”

Collecting the objects.

First we gather all of the relevant objects’ bounding boxes in the canvas. For this we only look at objects that are visible in the viewing port. Bounding boxes are collected in 4 separate lists, each for a different direction (right, left, up and down).

any object that overlap the source object is ignored

All these four lists are sorted so that the objects are arranged from closest to farthest from the source object, in that direction respectively.

Finding equidistant objects

Once we have these four lists, the function _findSidewaysSnaps can look at each list and collect a group of objects that are equidistant. This function can takes as input the tolerance, one of the 4 lists previously mentioned, and a function pointer that describes how to calculate distance in the particualr direction of the list. It also takes in by reference an iterator of a list which is used to collect the output.

This is a recursive function that tries to find the largest sequence of equidistant objects in a list and also outputs the distance between them. The function returns true if it finds a snap, and false otherwise.

A brief description of the algorithm:

1. Make a new list to hold the result.

2. FOR each object in a list

   2.1. If it’s at a particular distance from the next object

   • Add the object to the result
   • And call _findSidewaysSnaps with next object as the source object

   2.2. If the returned result has more objects than the previous result, use this and discard the previous one.

3. Now we have a list of the longest sequence of equidistant objects.

Combining results from different directions

_findSidewaysSnaps alone can only look at one list at a time. The function _snapEquidistantPoints is responsible for combining the resutls obtained for separate directions.

Here is a simplification for looking for snaps to the Right:

1. IF _findSidewaysSnaps returns true for _bboxes_right.

   1.1. Add the equidistant bounding boxes to the list vecRight.

   1.2. Store the equal distance in equalDist.

   1.3. Now IF _findSidewaysSnaps returns true for _bboxes_left (looking left).

   • IF equalDist == leftDist.

     • add the equidistant boxes on left to vecRight.
2. Now vecRight has a list of all equidistant objects.

This procedure is repeated for each direction.

Case with Overlapping objects

In case we have overlapping objects, it is useful that apart from probing them individually, we also consider them to be a single object. This can be achieved with a simple hack.

This involves, looking at each of the 4 lists, and add to them, the overall bounding boxes of objects that overlap. It is important that these new bounding boxes are inserted in such a way that the overall list remains sorted. The function _addBBoxforIntersectingBBoxes takes care of this.

Conclusion

This was a very simple breakdown of how distribution snapping is implemented in inkscape. There are an few more details that I have left out, which make this entire process a little bit more efficient (like checking if the distance is withing tolerace before moving ahead).