Donate Javascript Clipper Project
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.
Your main source for information is the documentation. Every function is covered with an usage example.
Please check the LIVE DEMO in http://jsclipper.sourceforge.net/6.2.1.1/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.
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
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:
Include Clipper library using
<script src="clipper.js"></script>
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.
The main methods in creating paths are: ClipperLib.Path()
, ClipperLib.Paths()
, ClipperLib.IntPoint()
.
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);
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);
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.
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.
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}]];
Create an instance of Clipper object.
var cpr = new ClipperLib.Clipper();
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.
Add subject and clip paths to Clipper (object) using AddPaths()
method.
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.
We need a holder for boolean operation result: an empty path.
var solution_paths = new ClipperLib.Paths();
or simpler:
var solution_paths = [];
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
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.
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.
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.
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.
<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:
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:
If not included yet, include Clipper library using
<script src="clipper.js"></script>
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.
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.
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
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.
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);
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.
Add paths to ClipperOffset
using AddPath
or AddPaths
methods:
co.AddPaths(paths, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);
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.
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.
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:
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:
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.
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.
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.
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);
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);
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.