Proposal for Voronoi extension

[Vincent Nivoliers]

Hi,
  I was looking for a plugin to compute Voronoi diagrams in inkscape. Although there already exists a plugin for Voronoi in inkscape, it is intended for the generation of random Voronoi patterns in paths [1]. My usage of this was more to be able to select a set of objects and have the Voronoi diagram of their centroids as a bunch of lines.
  the attached file does so using a "voronoi_backend.py" file which is actually the voronoi.py file shipped with inkscape from Bill Simons.

Here is a small description of what it does:

Input: http://www.pasteall.org/pic/12432
a set of selected objects (text objects are not handled) to be treated as seeds

Output: http://www.pasteall.org/pic/12433
a set of lines representing the Voronoi diagram of these seeds. The bounding box of the diagram is computed to be 9 times as big as the bounding box of the input objects, centered on it. However providing the capability of using any box (page area or provided by the user) would be easy.

I believe this feature is some kind of trivial extension of what the Voronoi script is already capable of, but it took me less time to code it myself than to bother you with some feature request. I'm open to suggestions and I will do my best to make the code more readable in case you would want to use it.

[1] Related report:
Bug #171901 “Effect Voronoi or Mosaic random”
<https://bugs.launchpad.net/inkscape/+bug/171901>

[Vincent Nivoliers (nivoliev)]

The associated inx file

[Vincent Nivoliers (nivoliev)]

And the voronoi_backend file which is a copy of Bill Simon's if you don't want to change the "import vornoi_backend" to whatever is necessary to get the file shipped with inkscape

[Vincent Nivoliers (nivoliev)]

A slight modification of the original attachment adding all the paths in a group.

[su_v (suv-lp)]

Works well in Inkscape 0.48+devel r10207 on OS X 10.5.8 (using Python 2.6.6) - initial tests done with minor changes to import the voronoi.py script shipping with inkscape, instead of 'voronoi_backend.py'.

- Additional options to set the size of the diagram bounding box (page size, or a rectangle as last in stack - i.e. visually on top - of the selected objects, or width/height with a units selector) would be great
- Would it make sense to optionally parse the nodes of a single path as seed for the diagram, instead of using the bbox centers of individual objects?
- Possibly this version could be added as a second tab to the existing (pattern-generating) Voronoi extension dialog?

[Vincent Nivoliers (nivoliev)]

-Added the possibility to choose between automatically generated box and page for the clipping area. Also added the possibility to activate or not the drawing of the clipping box.

-Fixed the position where the group was added. It now appears in the current layer.

-Fixed a problem due to numerical imprecision when the seeds were horizontally aligned

[Vincent Nivoliers (nivoliev)]

The corresponding inx file

[su_v (suv-lp)]

There still are some constellations which can cause irregularities in the resulting Voronoi diagram: the attached file shows some variants (see different layers) with some zero-length paths (i.e. missing lines in the diagram). I haven't figured out what exactly triggers it (possibly relation to neighboring seeds as well as absolute position can have an influence).

[su_v (suv-lp)]

Enhancement proposal (please review and improve):
- allow to optionally draw the Delaunay triangulation (or both) based on the selected objects (as seeds)
- works in current 0.48.1 and trunk (referencing the bundled voronoi.py python script)

[su_v (suv-lp)]

For the Delaunay triangulation, there is minor change required in the bundled 'voronoi.py' (s/true/True/) - I don' t know the triangulation fails otherwise.

[Alvin Penner (apenner)]

hi, very interesting extension!

- if I draw 4 objects, or more
- do not select anything
- use Voronoi Diagram option
- use Automatic from Seeds option (problem does not occur with Page option)

get the crash message:

Traceback (most recent call last):

  File "voronoi2svg.py", line 285, in <module>

    e.affect()

  File "C:\Program Files\Inkscape\share\extensions\inkex.py", line 215, in affect

    self.effect()

  File "voronoi2svg.py", line 211, in effect

    clipBox = (2*gBbox[0]-gBbox[1],

TypeError: 'NoneType' object is unsubscriptable

[jazzynico (jazzynico)]

> get the crash message:

Confirmed on Windows XP, Inkscape trunk revision 10221.
Same error, no matter how many paths are on the canvas (tested from 0 to 4).

[su_v (suv-lp)]

> no matter how many paths are on the canvas

The extension needs a selection of seeds, but the code for the voronoi diagram doesn't test if the selection is empty (I added basic checks when actually calling the voronoi module, but the calculation of the clip-box doesn't yet include the check - I'll see if I can upload a version with additional checks, or maybe Vincent is faster ;) ).

[Vincent Nivoliers (nivoliev)]

Hi, thanks for the feedback and contributions. Here is a new version of the current voronoi2svg.py file. The modifications are:

- Fixed a bug mentionned by ~suv on 2011-05-21. It occurred when the edges of the Voronoi diagram intersected a corner of the clipping box. Nice catch !

- Moved the "Please select seed objects!" error so that it occurs earlier to avoid the behavior described by Alvin on 2011-05-24. The automatic clipping box from seeds used a non existing bounding box. Thanks for testing.

- Handled correctly any transformation set on the tree branch leading to the group containing the seeds for "Page" clipping mode (previous version did not clip by page when a transformation was set on the group containing the seeds). To do so I coded two functions that could be useful in "simpletransform.py":
  * invertTransform which computes the inverse transformation matrix of a given one
  * getGlobalTransform which gathers the transformation of a node from the root of the document
These functions are currently in the attached file but if you feel like they could be useful in simpletransform.py I can generate a patch against it with this addition.

[su_v (suv-lp)]

> Handled correctly any transformation (…)

When toggling 'Live Preview' repeatedly without closing the dialog in-between, the transformation is wrong after the first preview and doesn't get correctly calculated on later previews. The same already happened in the previous version(s) when e.g. using seeds within a rotated group (i.e. not related to most recent changes to compensate parent transform(s)).

Is this a bug in the extension system (do subsequent runs of the extension script when toggling 'Live Preview' get different data from Inkscape)?

[su_v (suv-lp)]

> Is this a bug in the extension system (…)?

Apparently the current layer/group level (self.current_layer) is reset to the parent inkscape layer group [1] after toggling 'Live Preview' (i.e. undoing the extension effect) while the selection of objects doesn't change. The new Voronoi group then is created in 'Layer 1' instead of inside the transformed (e.g. rotated) group.

[1] or to 'root' e.g. with 'Extensions > Render > Triangle': the triangle is created in 'root' instead of the current (nested) group level if applied after toggling the live preview at least once.

[Alvin Penner (apenner)]

any objections if I commit this?

[Alvin Penner (apenner)]

committed to bzr rev 10243, thanks Vincent and ~suv

[Alvin Penner (apenner)]

This is a follow-up to comment 16 by ~suv. It looks as though there is still a remaining issue with transforms, which is not necessarily related to Live Preview, but is related to the root layer.

-load the file test_translate.svg, which contains a translate operation on Layer 1
- make sure the layer is Layer 1, select all objects and perform Voronoi
- confirm that the diagram is correct
- now force the drawing into root layer by opening the XML editor and clicking on the "Layer 1" node
- confirm that the layer says root on the status bar
- select all objects and perform Voronoi again

[Alvin Penner (apenner)]

get the attached svg file, where the second diagram is translated compared to the first

[Vincent Nivoliers (nivoliev)]

Thanks for the commit and testing. Here is a new version which hopefully solves your problem. Here is what it fixes:

- Old version: the group containing the selected nodes was supposed to be self.current_layer which is actually not always the case in the cases you submitted.

- New version: the group containing the elements is recovered using the parent node of the first selected object.

[su_v (suv-lp)]

Confirmed - the latest version works around the problem of losing the current layer/group level when toggling live-preview.

[Alvin Penner (apenner)]

thanks, committed to rev 10248

[Vincent Nivoliers (nivoliev)]

Thanks !

@JazzyNico ~suv told me to contact you for translation matters. Since I'm French, I could also do the translation if you'd like.

[jazzynico (jazzynico)]

Thanks Vincent!
I've just committed a translatable version of the extension (also modified for UI consistency) and a first version of the French translation in the trunk, revision 10249.
Don't hesitate to tell me if you have better translations (I'm really not sure how to translate "seeds" in that context...).

[Alvin Penner (apenner)]

> translate "seeds"

would it be appropriate to use the phrase "Automatic from selected objects" ?

[Vincent Nivoliers (nivoliev)]

Thanks for the translation. I checked on Wikipedia, it seems that a standard name in english is "sites" which translates in "sites" in French.

For "Area bounding the diagram" maybe "Bounding box of the diagram" would have been more appropriate. You made me realize this by translating "Show the bounding area" by "Montrer la boîte englobante". To be consistent, I would therefore say:

"Bounding box of the diagram" -> "Boîte englobante du diagramme"
"Show the bounding box" -> "Montrer la boîte englobante"

Alvin, you're right too, nothing explains in the interface how the extension works, and that objects should be selected.

Here is a new version of the inx file from that commited by JazzyNico. I hope I didn't break anything. I modified the text to conform to your remarks and added a help tab.

A last thing I don't know how to handle is the error messages triggered from the python file. Is there any way I could also mark these for translation ?

[su_v (suv-lp)]

> I don't know how to handle is the error messages
> triggered from the python file

Other extensions do it like this:
generate_voronoi.py: inkex.errormsg(_("Please select an object"))
inkex.py: inkex.errormsg(_("This extension requires two selected paths."))
interp_att_g.py: inkex.errormsg( 'There is no selection to interpolate' )
web-set-att.py: inkwebeffect.inkex.errormsg(_("You must select at least two elements."))

AFAIU related to or limited due to
Bug #425202 “Script messages not translated”
<https://bugs.launchpad.net/inkscape/+bug/425202>

[su_v (suv-lp)]

Oops, the one from 'interp_att_g.py' slipped in (apparently, it doesn't use gettext to mark the string for translation).

[Vincent Nivoliers (nivoliev)]

Here is the extension python file, with a minor fix related to the addition of a tab in the inx file, and the translation marker added on the error message.

[su_v (suv-lp)]

The python script v0.4 seems to be based on an older version (before the transform / current_layer fix).

[Vincent Nivoliers (nivoliev)]

Erf you're very right. Old files messing up. I deleted the wrong attachment. Here is the right one.

[jazzynico (jazzynico)]

New INX and internationalized version of the Python file committed in the trunk, revision 10258.
interp_att_g.py fixed, same revision.
POT files and French translation updated.

[Vincent Nivoliers (nivoliev)]

@JazzyNico: Thanks. One tiny problem, each object is a site (I may not have been clear about that), therefore "sites" should be in the plural in the French translation. (file po.fr line 27486).

[jazzynico (jazzynico)]

@Vincent - Translation fixed in the trunk as of revision 10321. Thanks for your help!