livarot

a set of c++ classes doing basic operations on polygons and computing voronoi diagrams. A C conversion is in progress; only the polygon part of livarot has been translated for the moment.

Need to focus on other stuff, so i leave livarot alone for the time being. In case explanations or (simple) features are needed, just mail me.

18/04/04: it's been a while... just added a couple of bugfixes, nothing really new. those looking for the most up-to-date version of livarot (the C++ version) will find it in the source code of inkscape, in the folder named "livarot". i still have to put the C version up to date...

29/11/03: added some functions to do approximate outline of curves. the algorithm comes from a plugin for Sketch: PathStroke.py.

18/11/03: added the voronoi computation code to the nlivarot; no voronoi rasterization or clipping yet, maybe next time...

8/11/03: changed the curve-> polyline code; added the ability to recompose curves from polylines, so you can have curve->polygons, make operations on the polygons (only boolean ops and removing self-intersections until i find a way to deal with offsets of curves), and then transform the polygons back into curves. Also: aaaarrrrgh! silly sourceforge doesn't seem to put different releases of a same package in different places, so i lost the previous versions (huitieme and neuvieme) since they had the same name....

13/09/03: wrote a bit of documentation for the releases huitieme and neuvieme. Also added (silently) several bugfixes.

29/07/03: added real linear and radial gradient; corrected the dashing function, which was buggy; added a quick&dirty subsampling algorithm to deal with shapes that aren't full-fledged polygon, for example shapes with intersections. It's faster than the exact-coverage antialiasing algorithm, but not as nice.

27/07/03: added the possibility to put dashes on strokes; removed some 1-character bugs (and two 2-characters ones)

21/07/03: in a never-ending quest for robustness, i rewrote the polygon intersector; now it uses a rounding scheme similar to the one proposed by J. Hobby (see here for pointers). Also did a conversion of the polygon handling part to straight C.

24/05/03: added a clip function for voronoi (the boolean operation function doesn't work with these); also a clipped polygon rasterization function; improved the justification algorithm and the DumbText class. [this is still named release "septieme"; i just re-uploaded the file]

21/05/03: a little modification to speed up the justification part. It was something that Knuth was explaining in the Complete TeX Source, but i just understood it... [this is still named release "septieme"; i just re-uploaded the file]

18/05/03: i know i shouldn't waste time on that, but i added a class Metric that loads AFM files and uses them to compute word lengths and glyph positions. The DumbText example class has been modified to accomodate this. [this is still named release "septieme"; i just re-uploaded the file]

15/05/03: added a little paragraph justification algorithm for arbitrary shapes, and a CoverRuns class to compute coverage of the shape by a band (for the justification algorithm, namely). Justification has nothing to do with livarot, but since it was done, i added it here. Also, this does just justification, not hyphenation. The handling of the text is deferred to a helper class. All the justification does is try to stack boxes given by the helper class in a shape, and ask to that same helper class where to hyphenate.

What it can do:
- create paths, bezier paths, and cubic path
- transform paths in polylines
- stroke polylines with differents butt and join types
- fill polylines
- transform polylines into shapes (non-intersecting eulerian graphs)
- boolean operations on shapes: intersection, union, difference
- compute offsets of shapes
- raster shapes in 32bit ARGB buffers with anti-aliasing
- compute voronoi diagrams of points and segments
- clamp the voronoi diagram to a given distance, and clamp the inside to a given distance and the outside to different distances
- raster voronoi diagrams by filling them, or using the distance as an index in a color table, or the gradient (it's a bad term, just meaning: "vector to the nearest point of the shape") as index

What is does not (and probably will never do):
- be blazing fast. For the moment shape operations and rasterization are relatively fast, but offset is a bit slow, and voronoi will always be slow, because they involve lots of complicated math (and lots of my sweat)
- compute exact voronoi diagrams and shapes: shape points are rounded to 0.001 and voronoi computations don't compute the region for segments smaller than 0.1; this removes some numerical problems, but not all
- work with all pixel sizes (8bit, 16bit, 32bit and more), with all kinds of display... the raster functions were initially for debugging purposes, and anyway, i don't know much in that field. It isn't be very difficult to modify the raster functions to handle differents cases (see documentation), since i insulated most of the display stuff from the rasterization computations
- stink and taste like the livarot cheese does

Questions? @mail me...