Which JavaScript library can do boolean operations with bezier curves?

Question

Does a Javascript library exist which can perform boolean operations on paths (bezier curves)?

I know about Paper.js and Raphael.js, but both cannot perform these actions now.

Do you mean you want to compare curves, and check for equality? — Aesthete, Aug 09 '12 at 09:58
i mean boolean operations like union, intersections, difference. Maybe curves is the wrong notion for this, but these operations are standards in all vector graphic applications like adobe illustrator or inkscape. look here: http://www.angelfire.com/mi/kevincharles/inkscape/p7c4.html — philipp, Aug 09 '12 at 10:09
what about http://stackoverflow.com/questions/109364/bezier-clipping/3005394#3005394 ? — wnrph, Sep 12 '12 at 00:50

Jürg Lehni · Answer 1 · 2013-10-10T13:05:59.557

8

Paper.js now has boolean operations in its core:

https://github.com/paperjs/paper.js/blob/master/src/path/PathItem.Boolean.js

And here you can see the operations in action:

http://assets.paperjs.org/boolean/

edited Oct 10 '13 at 13:05

answered May 07 '13 at 07:46

Jürg Lehni

1,677
13
16

1

I tried it out and uniting two circles already shows some significant bugs. – Ian Terrell Jul 12 '13 at 19:40
Clipper from Timo above is very reliable. I have it in a webapp we developed together with Timo and it is phenomenal both in speed and reliability. Only problem is the polygonization of the curves but if done in small intervals the visual result is indistinguishable. Curve boolean operations are notoriously difficult to get right so expect more bugs with paper.js boolean ops. Just my opinion – nicholaswmin Aug 06 '13 at 09:37
1

@IanTerrell we've improved the boolean operations quite a bit since. But if you encounter bugs it would be nice if you could report them, so we can fix them. – Jürg Lehni Oct 10 '13 at 13:04
1

@NicholasKyriakides paper.js uses the bezier fat line clipping algorithm for the detection of path intersections and therefore performs extremely fast. We have heavily tested our approach and have found it work very reliably. Please note that there is a big difference between performing such operations on polygons (consisting only of lines) and actual bezier paths. Paper.js preserves the bezier paths and does not require you to convert paths to polygons at a loss of precision. – Jürg Lehni Oct 10 '13 at 13:07
@JürgLehni what is the accuracy loss you are having? Do you use integers in your computations or floating points? I am asking because geometric operations tend to use integers to avoid numerical robustness issues. The integer rounding causes loss of accuracy – nicholaswmin Nov 27 '13 at 17:12
@NicholasKyriakides no I'm talking of the loss of precision when tessellating a smooth bezier curve into a sequence of straight lines, as required by Clipper. Paper.js' own boolean operations don't require this step, thus preserve the original quality of the shapes. – Jürg Lehni Dec 23 '13 at 11:45
Jurg, happy to hear back from you. We are currently in the process of creating a "curve-to polygons-boolean operate - reconstruct curves" scenario. Mind the term "reconstruct curves", and not curve fitting. At a point we had to reach a decision whether to use integer arithmetic OR floating point arithmetic. Due to rounding there is always some loss of accuracy in geometric operations. Therefore your solution has some although i would reckon very minimal loss of accuracy itself. We no longer receive polygons instead of curves. We receive pure reconstructed curves. I will update my answer soon. – nicholaswmin Dec 23 '13 at 12:22
Floating point arithmetic is more accurate but has numerical robustness issues, integer on the other hand results in more loss of accuracy but it is numerically robust. What did you use in Paper.js? – nicholaswmin Dec 23 '13 at 12:23
1

We're using floating point, and work around the robustness issues. We are currently implementing a new approach based on winding direction, as outlined by Cary Clark in this video: "Skia Path Ops: High Performance Set Operations for Geometry", http://www.youtube.com/watch?v=OmfliNQsk88 – Jürg Lehni Jan 04 '14 at 16:08
@JürgLehni what about self intersecting shapes? – nicholaswmin Jan 21 '14 at 08:37
1

@NicholasKyriakides we're working on that, should be ready soon! – Jürg Lehni Feb 12 '14 at 23:04

Timo Kähkönen · Answer 2 · 2013-04-22T07:14:29.543

If you convert path to polygons (eg. using pathelement.getPointAtLength()), then you can use Javascript Clipper, which is a javascript port of popular Angus Johnson's Clipper Library.

This is an example of Difference, but also Union, Intersect and Xor are possible: Difference of polygons

The page of Javascript Clipper is here.

If getPointAtLength() gives too much points, Javascript Clipper has a function ClipperLib.Lighten(), which can reduce point count significantly.

The library supports also polygon offsetting. See the live demo.

EDIT: after testing I can confirm that pathelement.getPointAtLength() is best suitable for eg. hit testing, but not so good for polygonizing in this case, because it produces too few or too much points and doesn't take into account the curvature. It's the fact that tight curves need more points and loose curves fewer. Better is to convert all path segments to Cubic curves and use some adaptive algorithm for polygonizing curves. I have made some tests and may be soon can introduce a better way for polygonizing.

EDIT: I have managed to implement SVG path polygonizing function, which handles all kind of paths and also flattens transformations. After testing thousands randomly generated paths and transformations it seems to be reliable. Also all possible degenerate cases (where curves are collinear or some of the points are the same) are handled without issues. Although it is already many times faster and more precise than native getPointAtLength() while producing significantly fewer points, the process has room for speed improvements using eg. taxicab angles instead of atan2() and making the code fully Web Workers compatible by removing all DOM methods. I want to make it 100% bugfree before publishing it. It's ideal use case is eg. possibility to make boolean operations with generated polygons.

score 3 · Answer 3 · answered Dec 28 '18 at 06:15

Example of PaperJS boolean operations with intersect function

We can do it with PaperJS boolean operations, which can operate with SVG paths (bezier curves paths inclusive).

PaperJS has 5 different boolean operations: exclude, subtract, unite, intersect, divide. You can see all this examples here.

This operations are also functions with the same name and they return item object, which has the function exportSVG(). It returns true SVG Path element, which has a new shape of both paths intersection. It is very useful – you can get the value for the path attribute d or you can append this path element to your new SVG element.

paper.install(window);
window.onload = function()
{
    paper.setup('canvas');

    var p1 = 'M 24.379464,51.504463 23.434524,23.156249 38.742559,12.572916 c 0,0 29.860118,-9.0714281 17.00893,0.755953 -12.851191,9.82738 13.229166,19.465774 13.229166,19.465774 z',
        p2 = 'm 32.883928,0.28869028 c 0,0 -15.686011,1.51190452 -8.504463,7.18154712 7.181546,5.6696426 50.270836,30.0491076 26.458332,42.3333336 -23.8125,12.284226 47.058036,14.174107 47.058036,14.174107 z',
        path1 = new Path(p1),
        path2 = new Path(p2);

    path1.fillColor = 'rgba(255,0,0,.5)';
    path1.position = new Point(25, 25);

    path2.fillColor = 'rgba(0,255,0,.5)';
    path2.position = new Point(40, 25);
    
    var result = path2.intersect(path1);
    result.selected = true;
    result.fillColor = '#77f';

    //exportSVG() docu: http://paperjs.org/reference/item/#exportsvg
    var svgPathElement = result.exportSVG(),
        dPath = svgPathElement.getAttribute('d');
    
    document.querySelector('path').setAttribute('d', dPath);

    var output = document.querySelector('#output');
    output.innerHTML = '<pre><b>D value from path:</b> ' + dPath + '</pre>';
    output.innerHTML += '<xmp>HTML string of path: ' + svgPathElement.outerHTML + '</xmp>';
};

table
{
    margin-left:14px;
    padding-left:14px;
    border-left:1px solid gray;
    display:inline-block
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/paper.js/0.12.0/paper-full.min.js"></script>

<canvas id="canvas" width="75" height="75" resize></canvas>
<table><tr><td><b>Our new shape of both paths intersection in separate SVG:</b></td></tr>
<tr><td>
    <svg width="75" height="75" viewBox="0 0 75 75">
    <path fill="rgba(0,0,255,.5)" d=""/>
    </svg>
</td></tr></table>

<div id="output"></div>

Useful links:

score 1 · Answer 4 · answered Aug 17 '12 at 10:17

1

Try to use this - https://github.com/interstateone/polygons

answered Aug 17 '12 at 10:17

Paramonych

11
1

score 1 · Answer 5 · answered Jan 08 '13 at 11:53

1

There's a plugin for raphael.js providing this functionality – https://github.com/poilu/raphael-boolean

answered Jan 08 '13 at 11:53

poilu

11
2

Which JavaScript library can do boolean operations with bezier curves?

5 Answers5

Example of PaperJS boolean operations with intersect function

Linked