Catalog · How the catalog works
clipper2-legacy
fork of experimental clipper2
- ★ 2 on GitHub
Anyone may press Interesting, signed in or not. It helps others find this project.
README
This is a preview of a major Clipper update. While the code in previous versions
was functional, in many places it is/was downright ugly. This new version is a
significant rewrite that should be easier to understand and maintain. There's
also some performance improvement. This new Clipper it's roughly twice as fast
as the previous version, even allowing for the absence of any merging or
simplifying of polygons with common/touching edges in clipping solutions. (That
feature was imperfect in previous versions and it's difficult to get right
without overly complicating, slowing and bloating the library. It remains
a work in progress.) The 'offsetting' code has also undergone significant
revision and a new Triangulation unit has been added.
There are quite a few changes to Clipper's interface including ...
1. Most noteworthy of all ... the Closed parameter in the AddPath and AddPaths
methods has been changed to IsOpen (ie the exact opposite to previously).
2. The PolyFillType enumeration has been renamed FillRule (TFillRule in Delphi).
3. The cInt type has been replaced with the native 64bit integer type (Int64
or int64_t) as there's no longer a need to restrict the range of 64bit path
coordinates (at least in the core/base Clipper class).
4. The IntPoint and IntRect types have also been renamed Point64 and Rect64
respectively (or TPoint64 and TRect64 in Delphi).
5. The Clipper object's Execute parameters have changed with the addition of an
(optional) OpenPaths (solution) parameter, and with the removal of one of
two FillRule parameters. (On reflection it was probably unnecessary and also
confusing providing different fill rules for Subject and Clip paths.)
6. The Polytree class now contains only closed paths (ie polygons) since open
paths can't contain/own polygons. (Any open paths in the solution are now
returned via a separate Paths parameter in Clipper's Execute method.)
When I originally translated this Library from Delphi (Pascal) to C# and C++,
I deliberately kept a strong Delphi naming style as I thought this would help
with maintenance. In hindsight this was a mistake. It didn't really achieve
that goal, and it made the C# and C++ code look odd. With this new version,
I've attempted to adopt a more conventional naming style for each language,
while admitting that I still have limited coding experience in both C# and C++.
Below I've benchmarked some comparisons between the old and the new versions of
Clipper. (I also removed the polygon 'merging' code from the old version so
we're comparing 'apples with apples'.) All tests were performed on a Windows 10
64Bit PC with Intel i7 2.0GHz CPU & 8GB RAM.
Tests 1a and 2 reflect Delphi code (compiled to 32bit using Delphi 10.1).Test
1b reflects C# code (compiled to 64bit .NET Framework with MSVS Community 2017).
Test 1c reflects C++ code (compiled to 32bit with MSVS Community 2017).
TEST1a: Time (secs) to intersect 2 COMPLEX polygons - a subject and a clip
polygon - having random coordinates and varying numbers of edges (Delphi 32bit).
+===================+=========+=========+=======+
|No. Edges | New | Old | Perf. |
|(for each polygon) | Clipper | Clipper | Incr. |
+===================+=========+=========+=======+
| 100 | 0.002 | 0.003 | 50% |
| 500 | 0.055 | 0.078 | 42% |
|1000 | 0.32 | 0.60 | 88% |
|2000 | 4.17 | 8.15 | 95% |
|2500 | 9.84 | 20.0 | 103% |
|3000 | 21.5 | 48.8 | 127% |
|3500 | 48.7 | 93.5 | 92% |
|4000 | 94.3 | 173 | 83% |
|4500 | 183 | 294 | 60% |
|5000 | 273 | 497 | 82% |
+===================+=========+=========+=======+
Vertex coordinate ranges X:0-800, Y:0-600 (rounded to nearest 10).
TEST1b: Same test as above but using C# code (to 64bit .NET framework).
+===================+=========+=========+=======+
|No. Edges | New | Old | Perf. |
|(for each polygon) | Clipper | Clipper | Incr. |
+===================+=========+=========+=======+
| 100 | 0.002 | 0.003 | 50% |
| 500 | 0.074 | 0.148 | 100% |
|1000 | 0.422 | 0.729 | 73% |
|2000 | 3.87 | 7.34 | 90% |
|2500 | 8.34 | 16.6 | 99% |
|3000 | 16.8 | 36.8 | 119% |
|3500 | 33.3 | 68.6 | 106% |
|4000 | 57.2 | 121 | 111% |
|4500 | 105 | 214 | 104% |
|5000 | 171 | 363 | 112% |
+===================+=========+=========+=======+
TEST1c: Same test as above but using MSVS C++ code (to 32bit).
+===================+=========+=========+=======+
|No. Edges | New | Old | Perf. |
|(for each polygon) | Clipper | Clipper | Incr. |
+===================+=========+=========+=======+
| 100 | 0.003 | 0.003 | 0% |
| 500 | 0.054 | 0.084 | 56% |
|1000 | 0.270 | 0.500 | 85% |
|2000 | 1.99 | 4.80 | 141% |
|2500 | 4.64 | 12.1 | 161% |
|3000 | 10.8 | 25.6 | 137% |
|3500 | 21.6 | 55.7 | 158% |
|4000 | 40.9 | 91.3 | 123% |
|4500 | 70.7 | 191 | 170% |
|5000 | 110 | 258 | 135% |
+===================+=========+=========+=======+
TEST2: Time (secs) to intersect multiple polygon ELLIPSES.
+===================+=========+=========+=======+
|No. Ellipses | New | Old | Perf. |
|(each subj & clip) | Clipper | Clipper | Incr. |
+===================+=========+=========+=======+
|1000 | 0.45 | 0.87 | 93% |
|2000 | 5.01 | 9.54 | 90% |
|2500 | 12.57 | 21.33 | 70% |
|3000 | 27.90 | 48.16 | 73% |
+===================+=========+=========+=======+
Paths approximating ellipses are such that the edges deviate from their true
elliptical paths by <= 1/2px. Random ellipses are bounded by the range
X:0-800, Y:0-600 where the max. elliptical radii are 1/3 of axis bounds
and the min. radii is 10. (Delphi 32bit)
