Menu ▾ ▴

Home 6

Timo Kähkönen

Donate Javascript Clipper Project

Javascript Clipper library, version 6

Javascript translation of Angus Johnson's C# Clipper Library

With Javascript Clipper library you can modify path (polygon and polyline) geometry in various ways. The main features are:

A) Principal boolean operations: Union, Intersection, Difference and Xor.
B) Offsetting paths with positive or negative amount. Other terms are inflating/deflating, dilating/eroding.

The other features are:
C) Simplifying polygons, which means that selfintersecting polygons are converted to simple polygons. After this operation polygon that has selfintersecting parts is split into multiple simple polygons.
D) Calculating area of polygons.
E) Cleaning polygons. Merges too near vertices which causes distortion when offsetting.
F) Lightening polygons. Reduces count of vertices by removing unnecessary vertices.
G) Calculating Minkowski Sum and Difference of polygons.
H) Calculating perimeter of paths.

In this wiki we will cover all the above mentioned features of this library and provide both step-by-step instructions and full functional sample codes.

Documentation

Your main source for information is the documentation. Every function is covered with an usage example.

Main Demo Program

Please check the LIVE DEMO in http://jsclipper.sourceforge.net/6.4.2.2/main_demo.html

You may want to take a look at the wiki of Main Demo. There are plenty of screen captures and description of interesting Polygon Explorer feature of the Main Demo.

Table of Contents

Translation notes

The features are the same as in original Clipper library with the following differences:

  • Some PolyTree and PolyNode properties are implemented as functions, eg. PolyTree.Total is PolyTree.Total().

  • Int128 struct of C# is implemented using big integer library JSBN of Tom Wu, which is the fastest of available big integer libraries in Javascript. Because of Javascript lack of 64-bit integer support, the coordinate space is a little more restricted than in C# version.

// Original (C#) version has support for coordinate space:
+-4611686018427387903 ( sqrt(2^127 -1)/2 )
// while Javascript version has support for coordinate space:
+-4503599627370495 ( sqrt(2^106 -1)/2 )

  • Also because there is no integer type in Javascript, you have to make sure that when calling ClipperLib.IntPoint(), the parameter values are rounded to integers using Math.round().

  • ClipperLib.JS object provides functions for calculating area, bounds and perimeter, cleaning, cloning, reducing vertices (lighten) and exPolygons related functions.

Author: Timo Kähkönen

A. Boolean operations of paths

First a quick starter example for busy people, which when executed produces a very simple shape:

In the above image two yellow frames (outer and hole polygon) are unioned to one shape (one outer polygon with three holes).

And then more detailed step-by-step instruction for anyone, who wants more information:

A1. Include library

Include Clipper library using

:::html
<script src="clipper.js"></script>

A2. Create paths

There are two types of paths: Subject and Clip. In Union and Intersection the result is the same despite of which is subject and which is clip. In Difference and Xor the result differs.

There are two (or more) ways to create paths. We show first the complicated one (that you'll understand the principle) and then the simpler one.

A2.1 Create subject path

The main methods in creating paths are: ClipperLib.Path(), ClipperLib.Paths(), ClipperLib.IntPoint().

:::javascript
var subj_paths = new ClipperLib.Paths();
var subj_path = new ClipperLib.Path();
subj_path.push(
  new ClipperLib.IntPoint(0, 0),
  new ClipperLib.IntPoint(100, 0),
  new ClipperLib.IntPoint(100, 100),
  new ClipperLib.IntPoint(0, 100));
subj_paths.push(subj_path);

A2.2 Create clip path

:::javascript
var clip_paths = new ClipperLib.Paths();
var clip_path = new ClipperLib.Path();
clip_path.push(
  new ClipperLib.IntPoint(0, 0),
  new ClipperLib.IntPoint(100, 0),
  new ClipperLib.IntPoint(100, 100),
  new ClipperLib.IntPoint(0, 100));
clip_paths.push(clip_path);

A2.3 Holes in polygons

If you want to add a hole, it's not possible using only one polygon. You have to create at least two sub polygons, one for outer and one for hole. The winding order of outer polygon (ie. non-hole) has to be opposite to the winding order of the hole polygon. You can add as many sub polygons as needed.

A2.4 Too complicated?

Alternatively you can create paths more simpler (and faster) way, because
ClipperLib.Path() and ClipperLib.Paths() are arrays. The following code creates two Paths, subj_paths and clip_paths, which both consist of two sub paths. The second one of each is a hole.

:::javascript
var subj_paths = [[{X:10,Y:10},{X:110,Y:10},{X:110,Y:110},{X:10,Y:110}],
                      [{X:20,Y:20},{X:20,Y:100},{X:100,Y:100},{X:100,Y:20}]]; 
var clip_paths = [[{X:50,Y:50},{X:150,Y:50},{X:150,Y:150},{X:50,Y:150}],
                      [{X:60,Y:60},{X:60,Y:140},{X:140,Y:140},{X:140,Y:60}]];

A3. Create Clipper object

Create an instance of Clipper object.

:::javascript
var cpr = new ClipperLib.Clipper();

A4. Scale coordinates if needed

Because Clipper library handles coordinates as integers, you have to scale them up before adding them to Clipper (and scale them back down before drawing). The scaling is done easily with traversing path arrays.

var scale = 100;
ClipperLib.JS.ScaleUpPaths(subj_paths, scale);
ClipperLib.JS.ScaleUpPaths(clip_paths, scale);
// Use ClipperLib.JS.ScaleUpPath() if you have single Path.

Note! This scaling requirement may be removed in future Clipper version and handled internally.

A5. Add paths to Clipper

Add subject and clip paths to Clipper (object) using AddPaths() method.

:::javascript
cpr.AddPaths(subj_paths, ClipperLib.PolyType.ptSubject, true);
cpr.AddPaths(clip_paths, ClipperLib.PolyType.ptClip, true);

The last parameter true means that paths are closed (polygons); false would mean that paths are open (lines). Subject can be open or closed or mixture of both, but clip has to be closed.

A6. Create an empty solution path

We need a holder for boolean operation result: an empty path.

:::javascript
var solution_paths = new ClipperLib.Paths();

or simpler:

:::javascript
var solution_paths = [];

A7. Select ClipType and PolyFillType and execute clipping operation

A7.1 Select ClipType

Select the ClipType, which is the actual clipping operation:

var clipType = ClipperLib.ClipType.ctIntersection;
// or simpler
var clipType = 0;

The ClipType can be one of the following (or respective numbers 0, 1, 2, 3):

ClipperLib.ClipType.ctIntersection
ClipperLib.ClipType.ctUnion
ClipperLib.ClipType.ctDifference
ClipperLib.ClipType.ctXor

A7.2 Select PolyFillType

Select the PolyFillType, which tells how polygon is filled. The PolyFillType has not to be the same in subject and clip polygons, but below we use the same for both.

var subject_fillType = ClipperLib.PolyFillType.pftNonZero;
var clip_fillType = ClipperLib.PolyFillType.pftNonZero;

or simpler

var subject_fillType = 1;
var clip_fillType = 1;

The PolyFillType can be one of the following (or respective numbers 0, 1, 2, 3):

ClipperLib.PolyFillType.pftEvenOdd
ClipperLib.PolyFillType.pftNonZero
ClipperLib.PolyFillType.pftPositive
ClipperLib.PolyFillType.pftNegative

Note! Although all those PolyFillTypes are supported by Javascript Clipper Library, the graphics backend may support only limited subset of those. EvenOdd and NonZero are supported by SVG format. Html5 canvas seems to have currently only NonZero rule.

A7.2 Execute boolean operation

var succeeded = cpr.Execute(clipType, solution_paths, subject_fillType, clip_fillType);

That's it!

Now solution_paths is populated by the result of the above boolean operation (Intersection in this case) and can be drawn (or modified more or serialized for sending) somewhere.

A8. Drawing boolean operated polygons

Polygons can be drawn in various ways using Javascript in web browsers. We cover here two popular ways used in modern browsers: inline SVG and canvas. The other possibilities are using Microsoft's VML or Walter Zorn's Vector Graphics Library (although I'm not sure if it's possible to draw polygons with holes with it).

There are many libraries that use SVG, VML or canvas as graphical backend, eg. Raphaël JS.

A8.1 FULL CODE EXAMPLE: Draw boolean operated polygons using SVG

We can draw polygons in various ways in SVG. There is a native <polygon> element, but the disadvantage is that it does not support holes and sub polygons. So better way is to use <path> element. Each sub polygon is drawn as one subpath. Each subpath starts with M (moveTo) and ends with Z (closePath).

The following is a full example of making boolean operations to polygons and appending them to SVG. In this case we create four inline SVG documents and draw one boolean result on each one.

Get full source code.

After executing the code above, you should have four clipped polygons as SVG paths in your svgcontainer element like the image below shows.

A8.2 FULL CODE EXAMPLE: Drawing boolean operated polygons using <canvas>

Canvas differs from SVG. We cannot use textual strings like in SVG. Paths are drawn as commands moveTo() and lineTo(). Note! after they are drawn they cannot be modified as in SVG. The whole canvas is needed to be redrawn if something is wanted to be updated.

Get full source code.

After you execute the code, you'll see that Canvas result is very similar with SVG:

B. Offsetting paths

Another main feature in Clipper library is polygon and polyline offsetting. It's purpose is to fatten (bolden, inflate, dilate, positive offset) or thin (deflate, erode, negative offset) polygons by certain amount or fatten polylines.

In section B we provide first a quick starter code for offsetting, then detailed step-by-step instructions and finally a more complex full code example.

First, an easy quick starter example for busy people, which produces when executed the following shape:

In the above image a frame (outer polygon with a hole) is thinned by 10 units.

Then detailed step-by-step instructions for anyone who wants more information:

B1. Include library

If not included yet, include Clipper library using

:::html
<script src="clipper.js"></script>

B2. Create path

First we create a path that is going to be offsetted.

var paths = [[{X:30,Y:30},{X:130,Y:30},{X:130,Y:130},{X:30,Y:130}],
                 [{X:60,Y:60},{X:60,Y:100},{X:100,Y:100},{X:100,Y:60}]];

The paths above is a multi-path, ie. consists of two sub paths, the outer one and a hole.

B3. Scale up polygon coordinates

Because Clipper library uses "integer" coordinates, we have to scale up coordinates to maintain precision. The scale value should be large enough, but for performance reasons not too high. If coordinates have a precision of 2 decimals, the sufficient scale coefficient is 100.

Note! Although main principle is the above, please be careful when deciding the proper scaling factor. If coordinates are originally integers, it may not always be sufficient to scale with coefficient 1 (ie. not to scale up at all). If joinType is jtRound and up-scaling is not done, then it's not always true that integers can represent the rounded corners of result. So safest is to always scale up at least by 10 or 100.

var scale = 100;
ClipperLib.JS.ScaleUpPaths(paths, scale);
// Use ClipperLib.JS.ScaleUpPath() if you have single Path.

B4. Simplifying and Cleaning

B4.1 Simplifying

The requirement for offsetting is that polygons are free of self-intersections, although all of them doesn't cause problems in all cases.

In order to convert a complex polygon to simple ones, Clipper library provides SimplifyPolygon() and SimplifyPolygons() methods. Complex polygon means a polygon that has self-intersections, Simple polygon means opposite.

Simplifying is optional. If polygon hasn't self-intersections, then this step is not needed. If there may be, then you should simplify polygon before offsetting. It's not a bad mistake to simplify for certainty.

If path is open (polyline), then there is no need for simplifying, because there is no harm, if polyline crosses itself.

To remove self-intersections use:

paths = ClipperLib.Clipper.SimplifyPolygons(paths, ClipperLib.PolyFillType.pftNonZero);
                                             // or ClipperLib.PolyFillType.pftEvenOdd

B4.2 Cleaning

The Clipper Simplify feature (or more specifically the internal Union operation) has a limitation regarding to minor self-intersections. It can't remove all of them. It well should, but for the moment it can't. The creator of the original library is aware of this problem, but has not provided a solution so far, but instead provided a CleanPolygon() function which merges too-near points and the problem seems to be solved.

The following image shows an example of the problem. Both the left side and right side have polygons offsetted using joinType jtMiter and MiterLimit 100. The right one has cleaned using Clean() function and the distortion is disappeared. The distortion is bad when joinType is jtMiter and MiterLimit is big, but is clearly noticeable also with other joinTypes. Increasing the scaling factor may help in some cases, but is not a solution, because it increases also processing time and is not a general solution.

Example of distortion due to self-intersections

To remove minor self-intersections use:

var cleandelta = 0.1; // 0.1 should be the appropriate delta in different cases
paths = ClipperLib.JS.Clean(paths, cleandelta * scale);

Internally Clean() uses Radial Reduction algorithm, which merges sequential vertices, if they are at or under certain distance of each other.

Note! There are also cleaning functions in Clipper: CleanPolygon and CleanPolygons. They differ from Clean(), as they merge also collinear vertices:

var cleandelta = 0.1; // 0.1 should be the appropriate delta in different cases
paths = ClipperLib.Clipper.CleanPolygons(paths, cleandelta * scale);

B5. Create an instance of ClipperOffset object

The ClipperOffset object encapsulates the process of offsetting (inflating/deflating) both open and closed paths.

The Execute method can be called multiple times using different offsets (deltas) without having to reassign paths. Offsetting can be performed on a mixture of open and closed paths in a single operation.

If not yet created, create an instance of ClipperOffset object using:

var miterLimit = 2;
var arcTolerance = 0.25;
var co = new ClipperLib.ClipperOffset(miterLimit, arcTolerance);

See also documentation: ClipperOffset, ArcTolerance, MiterLimit.

B6. Add paths

Add paths to ClipperOffset using AddPath or AddPaths methods:

co.AddPaths(paths, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

B7. Create an empty solution and execute the offset operation

Now you can execute the offset operation using delta value, which can be negative or positive number:

var delta = -10;
var offsetted_paths = new ClipperLib.Paths();
co.Execute(offsetted_paths, delta*scale);

or if you want PolyTree:

var delta = -10;
var offsetted_polytree = new ClipperLib.PolyTree();
co.Execute(offsetted_polytree, delta*scale);

That's it. Now offsetted_paths or offsetted_polytree is populated by the result of offsetting operation, in this case thinned by -10 * scale. Please remember that before drawing this, the coordinates have to be scaled down by the scale factor, because the coordinates in result set are always "integers".

Note! The result may be empty or have more or less sub paths than in the original.

Note! If joinType is jtRound, rounded corners in result are represented as lines.

B8. Drawing offsetted polygons

As we made in the examples of boolean operated polygons, we'll present full functional examples of offsetting polygons and drawing them on two popular graphical backend in modern browsers: inline SVG and canvas.

B8.1 FULL CODE EXAMPLE: Drawing offsetted polygons using SVG

This is the full functional example of offsetting polygons and drawing them using SVG.

Get full source code.

Offsetted polygons are as follows when And here is the result after drawn on SVG:

B8.2 FULL CODE EXAMPLE: Drawing offsetted polygons using canvas

This is the full functional example of offsetting polygons and drawing them using canvas.

Get full source code.

And here is the result after executing the above code:

C. Boolean operations on ExPolygons and PolyTree

Sometimes you need to know, which hole belongs to which contour. This is the case eg. in triangulating polygons for use in 3D programs. This is not possible using Polygons structure. The answer is ExPolygons or PolyTree structure.

ExPolygon is an 'extended' polygon structure that encapsulates an outer polygon contour together with any contained polygon holes. Please read more about Boolean operations on ExPolygons and PolyTree.

D. Using Web Workers with Clipper

Clipper can handle very complex paths, and page update can take several seconds. In these cases it may be wise to use Web Workers to avoid browser hanging. Please read more about using Web Workers with Clipper.

Lightening Paths

In many cases polygons and polylines have too much vertices, which causes overload in drawing. This is eg. true when bitmaps are traced to vector graphics, in cartography and also when polygons are offsetted using Clipper with joinType jtRound.

To remove unnecessary vertices, we provide a method ClipperLib.Lighten(). It uses Perpendicular Reduction algorithm; all the vertices are traversed and the middle vertex of three sequential vertices is removed, if it's perpendicular distance to the line between start and end point of current three point sequence is at or under certain tolerance (distance).

To reduce vertices, use:

var tolerance = 0.1;
polygons = ClipperLib.JS.Lighten(polygons, tolerance * scale);

The tolerance above is negative or positive Number or zero. If negative, the clone of the original path is returned. The higher the tolerance is, the more vertices will be deleted.

Note! The reduction algorithm is not best suited for larger tolerance values, because it determines the border line very locally (in sequences of three vertices) and doesn't add new vertices in places where the addition could improve the fidelity to the original. By the way, it is fast. And the fidelity is ideal, if the tolerance is rather low, eg. 0.1 - 0.2 units.

Calculating area of polygon

To get the area of a polygon, the Javascript Clipper library provides AreaOfPolygon() and AreaOfPolygons() functions:

var area = ClipperLib.JS.AreaOfPolygon(polygon);

To get the area of a multipolygon, use this:

var area = ClipperLib.JS.AreaOfPolygons(polygons);

Calculating perimeter of polygon

To get the perimeter of a polygon, the Javascript Clipper library provides PerimeterOfPath() and PerimeterOfPaths() functions:

var polygonal_perimeter = ClipperLib.JS.PerimeterOfPath(path, true, 1);

To get the perimeter of a multipolygon, use this:

var polygonal_perimeter = ClipperLib.JS.PerimeterOfPaths(paths, true, 1);

The above two examples calculates the polygonal perimeter, which means that the perimeter is measured from the first point to the first point, regardless whether the last point is the same as the first point. If you want to measure line perimeter, use these:

var line_perimeter = ClipperLib.JS.PerimeterOfPath(path, false, 1);

To get the perimeter of a multipolygon, use this:

var line_perimeter = ClipperLib.JS.PerimeterOfPaths(paths, false, 1);

Licence

Javascript Clipper Library is dual licenced.

The actual Clipper Library is licenced as the original Angus Johnson's Clipper Library, which uses Boost Software Licence.

Javascript Clipper Library uses an implementation of the biginteger library JSBN of Tom Wu, which is licenced under a BSD license. See LICENSE for details.