mapnik / clipper Goto Github PK
View Code? Open in Web Editor NEWLicense: Boost Software License 1.0
License: Boost Software License 1.0
===================================================================== Clipper Change Log ===================================================================== v6.2.1 (31 October 2014) Rev 482 * Bugfix in ClipperOffset.Execute where the Polytree.IsHole property was returning incorrect values with negative offsets * Very minor improvement to join rounding in ClipperOffset * Fixed CPP OpenGL demo. v6.2.0 (17 October 2014) Rev 477 * Numerous minor bugfixes, too many to list. (See revisions 454-475 in Sourceforge Repository) * The ZFillFunction (custom callback function) has had its parameters changed. * Curves demo removed (temporarily). * Deprecated functions have been removed. v6.1.5 (26 February 2014) Rev 460 * Improved the joining of output polygons sharing a common edge when those common edges are horizontal. * Fixed a bug in ClipperOffset.AddPath() which would produce incorrect solutions when open paths were added before closed paths. * Minor code tidy and performance improvement v6.1.4 (6 February 2014) * Fixed bugs in MinkowskiSum * Fixed minor bug when using Clipper.ForceSimplify. * Modified use_xyz callback so that all 4 vertices around an intersection point are now passed to the callback function. v6.1.3a (22 January 2014) Rev 453 * Fixed buggy PointInPolygon function (C++ and C# only). Note this bug only affected the newly exported function, the internal PointInPolygon function used by Clipper was OK. v6.1.3 (19 January 2014) Rev 452 * Fixed potential endless loop condition when adding open paths to Clipper. * Fixed missing implementation of SimplifyPolygon function in C++ code. * Fixed incorrect upper range constant for polygon coordinates in Delphi code. * Added PointInPolygon function. * Overloaded MinkowskiSum function to accommodate multi-contour paths. v6.1.2 (15 December 2013) Rev 444 * Fixed broken C++ header file. * Minor improvement to joining polygons. v6.1.1 (13 December 2013) Rev 441 * Fixed a couple of bugs affecting open paths that could raise unhandled exceptions. v6.1.0 (12 December 2013) * Deleted: Previously deprecated code has been removed. * Modified: The OffsetPaths function is now deprecated as it has been replaced by the ClipperOffset class which is much more flexible. * Bugfixes: Several minor bugs have been fixed including occasionally an incorrect nesting within the PolyTree structure. v6.0.0 (30 October 2013) * Added: Open path (polyline) clipping. A new 'Curves' demo application showcases this (see the 'Curves' directory). * Update: Major improvement in the merging of shared/collinear edges in clip solutions (see Execute). * Added: The IntPoint structure now has an optional 'Z' member. (See the precompiler directive use_xyz.) * Added: Users can now force Clipper to use 32bit integers (via the precompiler directive use_int32) instead of using 64bit integers. * Modified: To accommodate open paths, the Polygon and Polygons structures have been renamed Path and Paths respectively. The AddPolygon and AddPolygons methods of the ClipperBase class have been renamed AddPath and AddPaths respectively. Several other functions have been similarly renamed. * Modified: The PolyNode Class has a new IsOpen property. * Modified: The Clipper class has a new ZFillFunction property. * Added: MinkowskiSum and MinkowskiDiff functions added. * Added: Several other new functions have been added including PolyTreeToPaths, OpenPathsFromPolyTree and ClosedPathsFromPolyTree. * Added: The Clipper constructor now accepts an optional InitOptions parameter to simplify setting properties. * Bugfixes: Numerous minor bugs have been fixed. * Deprecated: Version 6 is a major upgrade from previous versions and quite a number of changes have been made to exposed structures and functions. To minimize inconvenience to existing library users, some code has been retained and some added to maintain backward compatibility. However, because this code will be removed in a future update, it has been marked as deprecated and a precompiler directive use_deprecated has been defined. v5.1.6 (23 May 2013) * BugFix: CleanPolygon function was buggy. * Changed: The behaviour of the 'miter' JoinType has been changed so that when squaring occurs, it's no longer extended up to the miter limit but is squared off at exactly 'delta' units. (This improves the look of mitering with larger limits at acute angles.) * Added: New OffsetPolyLines function * Update: Minor code refactoring and optimisations v5.1.5 (5 May 2013) * Added: ForceSimple property to Clipper class * Update: Improved documentation v5.1.4 (24 March 2013) * Update: CleanPolygon function enhanced. * Update: Documentation improved. v5.1.3 (14 March 2013) * Bugfix: Minor bugfixes. * Update: Documentation significantly improved. v5.1.2 (26 February 2013) * Bugfix: PolyNode class was missing a constructor. * Update: The MiterLimit parameter in the OffsetPolygons function has been renamed Limit and can now also be used to limit the number of vertices used to construct arcs when JoinType is set to jtRound. v5.1.0 (17 February 2013) * Update: ExPolygons has been replaced with the PolyTree & PolyNode classes to more fully represent the parent-child relationships of the polygons returned by Clipper. * Added: New CleanPolygon and CleanPolygons functions. * Bugfix: Another orientation bug fixed. v5.0.2 - 30 December 2012 * Bugfix: Significant fixes in and tidy of the internal Int128 class (which is used only when polygon coordinate values are greater than ±0x3FFFFFFF (~1.07e9)). * Update: The Area algorithm has been updated and is faster. * Update: Documentation updates. The newish but undocumented 'CheckInputs' parameter of the OffsetPolygons function has been renamed 'AutoFix' and documented too. The comments on rounding have also been improved (ie clearer and expanded). v4.10.0 - 25 December 2012 * Bugfix: Orientation bugs should now be resolved (finally!). * Bugfix: Bug in Int128 class v4.9.8 - 2 December 2012 * Bugfix: Further fixes to rare Orientation bug. v4.9.7 - 29 November 2012 * Bugfix: Bug that very rarely returned the wrong polygon orientation. * Bugfix: Obscure bug affecting OffsetPolygons when using jtRound for the JoinType parameter and when polygons also contain very large coordinate values (> +/-100000000000). v4.9.6 - 9 November 2012 * Bugfix: Another obscure bug related to joining polygons. v4.9.4 - 2 November 2012 * Bugfix: Bugs in Int128 class occasionally causing wrong orientations. * Bugfix: Further fixes related to joining polygons. v4.9.0 - 9 October 2012 * Bugfix: Obscure bug related to joining polygons. v4.8.9 - 25 September 2012 * Bugfix: Obscure bug related to precision of intersections. v4.8.8 - 30 August 2012 * Bugfix: Fixed bug in OffsetPolygons function introduced in version 4.8.5. v4.8.7 - 24 August 2012 * Bugfix: ReversePolygon function in C++ translation was broken. * Bugfix: Two obscure bugs affecting orientation fixed too. v4.8.6 - 11 August 2012 * Bugfix: Potential for memory overflow errors when using ExPolygons structure. * Bugfix: The polygon coordinate range has been reduced to +/- 0x3FFFFFFFFFFFFFFF (4.6e18). * Update: ReversePolygons function was misnamed ReversePoints in C++. * Update: SimplifyPolygon function now takes a PolyFillType parameter. v4.8.5 - 15 July 2012 * Bugfix: Potential for memory overflow errors in OffsetPolygons(). v4.8.4 - 1 June 2012 * Bugfix: Another obscure bug affecting ExPolygons structure. v4.8.3 - 27 May 2012 * Bugfix: Obscure bug causing incorrect removal of a vertex. v4.8.2 - 21 May 2012 * Bugfix: Obscure bug could cause an exception when using ExPolygon structure. v4.8.1 - 12 May 2012 * Update: Cody tidy and minor bug fixes. v4.8.0 - 30 April 2012 * Bugfix: Occasional errors in orientation fixed. * Update: Added notes on rounding to the documentation. v4.7.6 - 11 April 2012 * Fixed a bug in Orientation function (affecting C# translations only). * Minor documentation update. v4.7.5 - 28 March 2012 * Bugfix: Fixed a recently introduced bug that occasionally caused an unhandled exception in C++ and C# translations. v4.7.4 - 15 March 2012 * Bugfix: Another minor bugfix. v4.7.2 - 4 March 2012 * Bugfix: Fixed bug introduced in ver 4.7 which sometimes caused an exception if ExPolygon structure was passed to Clipper's Execute method. v4.7.1 - 3 March 2012 * Bugfix: Rare crash when JoinCommonEdges joined polygons that 'cancelled' each other. * Bugfix: Clipper's internal Orientation method occasionally returned wrong result. * Update: Improved C# code (thanks to numerous excellent suggestions from David Piepgrass) v4.7 - 10 February 2012 * Improved the joining of output polygons sharing a common edge. v4.6.6 - 3 February 2012 * Bugfix: Another obscure bug occasionally causing incorrect polygon orientation. v4.6.5 - 17 January 2012 * Bugfix: Obscure bug occasionally causing incorrect hole assignment in ExPolygon structure. v4.6.4 - 8 November 2011 * Added: SimplifyPolygon and SimplifyPolygons functions. v4.6.3 - 11 November 2011 * Bugfix: Fixed another minor mitering bug in OffsetPolygons. v4.6.2 - 10 November 2011 * Bugfix: Fixed a rare bug in the orientation of polygons returned by Clipper's Execute() method. * Bugfix: Previous update introduced a mitering bug in the OffsetPolygons function. v4.6 - 29 October 2011 * Added: Support for Positive and Negative polygon fill types (in addition to the EvenOdd and NonZero fill types). * Bugfix: The OffsetPolygons function was generating the occasional artefact when 'shrinking' polygons. v4.5.5 - 8 October 2011 * Bugfix: Fixed an obscure bug in Clipper's JoinCommonEdges method. * Update: Replaced IsClockwise function with Orientation function. The orientation issues affecting OffsetPolygons should now be finally resolved. * Change: The Area function once again returns a signed value. v4.5.1 - 28 September 2011 * Deleted: The UseFullCoordinateRange property has been deleted since integer range is now managed implicitly. * BugFix: Minor bug in OffsetPolygon mitering. * Change: C# JoinType enum moved from Clipper class to ClipperLib namespace. * Change: The Area function now returns the absolute area (irrespective of orientation). * Change: The IsClockwise function now requires a second parameter - YAxisPositiveUpward - to accommodate displays with Y-axis oriented in either direction v4.4.4 - 10 September 2011 * Change: Deleted jtButt from JoinType (used by the OffsetPolygons function). * BugFix: Fixed another minor bug in OffsetPolygons function. * Update: Further improvements to the help file v4.4.3 - 29 August 2011 * BugFix: fixed a minor rounding issue in OffsetPolygons function (affected C++ & C# translations). * BugFix: fixed a minor bug in OffsetPolygons' function declaration (affected C++ translation only). * Change: 'clipper' namespace changed to 'ClipperLib' namespace in both C++ and C# code to remove the ambiguity between the Clipper class and the namespace. (This also required numerous updates to the accompanying demos.) v4.4.2 - 26 August 2011 * BugFix: minor bugfixes in Clipper. * Update: the OffsetPolygons function has been significantly improved by offering 4 different join styles. v4.4.0 - 6 August 2011 * BugFix: A number of minor bugs have been fixed that mostly affected the new ExPolygons structure. v4.3.0 - 17 June 2011 * New: ExPolygons structure that explicitly associates 'hole' polygons with their 'outer' container polygons. * New: Execute method overloaded so the solution parameter can now be either Polygons or ExPolygons. * BugFix: Fixed a rare bug in solution polygons orientation. v4.2.8 - 21 May 2011 * Update: JoinCommonEdges() improved once more. * BugFix: Several minor bugs fixed. v4.2.6 - 1 May 2011 * Bugfix: minor bug in SlopesEqual function. * Update: Merging of output polygons sharing common edges has been significantly inproved v4.2.4 - 26 April 2011 Input polygon coordinates can now contain the full range of signed 64bit integers (ie +/-9,223,372,036,854,775,807). This means that floating point values can be converted to and from Clipper's 64bit integer coordinates structure (IntPoint) and still retain a precision of up to 18 decimal places. However, since the large-integer math that supports this expanded range imposes a small cost on performance (~15%), a new property UseFullCoordinateRange has been added to the Clipper class to allow users the choice of whether or not to use this expanded coordinate range. If this property is disabled, coordinate values are restricted to +/-1,500,000,000. v4.2 - 12 April 2011 JoinCommonEdges() code significantly improved plus other minor improvements. v4.1.2 - 9 April 2011 * Update: Minor code tidy. * Bugfix: Possible endless loop in JoinCommonEdges() in clipper.pas. v4.1.1 - 8 April 2011 * Update: All polygon coordinates are now stored as 64bit integers (though they're still restricted to range -1.5e9 to +1.5e9 pending the inclusion of code supporting 64bit math). * Change: AddPolygon and AddPolygons methods now return boolean values. * Bugfix: Bug in JoinCommonEdges() caused potential endless loop. * Bugfix: Bug in IsClockwise(). (C++ code only) v4.0 - 5 April 2011 * Clipper 4 is a major rewrite of earlier versions. The biggest change is that floating point values are no longer used, except for the storing of edge slope values. The main benefit of this is the issue of numerical robustness has been addressed. Due to other major code improvements Clipper v4 is approximately 40% faster than Clipper v3. * The AddPolyPolygon method has been renamed to AddPolygons. * The IgnoreOrientation property has been removed. * The clipper_misc library has been merged back into the main clipper library. v3.1.0 - 17 February 2011 * Bugfix: Obscure bug in TClipperBase.SetDx method that caused problems with very small edges ( edges <1/1000th pixel in size). v3.0.3 - 9 February 2011 * Bugfix: Significant bug, but only in C# code. * Update: Minor refactoring. v3.0 - 31 January 2011 * Update: Major rewrite of the portion of code that calculates the output polygons' orientation. * Update: Help file significantly improved. * Change: Renamed ForceOrientation property to IgnoreOrientation. If the orientation of output polygons is not important, or can be managed separately, clipping routines can be sped up by about 60% by setting IgnoreOrientation to true. Defaults to false. * Change: The OffsetPolygon and Area functions have been moved to the new unit - clipper_misc. 2.99 - 15 January 2011 * Bugfix: Obscure bug in AddPolygon method could cause an endless loop. 2.8 - 20 November 2010 * Updated: Output polygons which previously shared a common edge are now merged. * Changed: The orientation of outer polygons is now clockwise when the display's Y axis is positive downwards (as is typical for most Windows applications). Inner polygons (holes) have the opposite orientation. * Added: Support module for Cairo Graphics Library (with demo). * Updated: C# and C++ demos. 2.522 - 15 October 2010 * Added C# translation (thanks to Olivier Lejeune) and a link to Ruby bindings (thanks to Mike Owens). 2.0 - 30 July 2010 * Clipper now clips using both the Even-Odd (alternate) and Non-Zero (winding) polygon filling rules. (Previously Clipper assumed the Even-Odd rule for polygon filling.) 1.4c - 16 June 2010 * Added C++ support for AGG graphics library 1.2s - 2 June 2010 * Added C++ translation of clipper.pas 1.0 - 9 May 2010
@flippmoke As we briefly discussed yesterday, I wrote a quick fuzz-testing program to generate random terrible polygons and see how long it takes Clipper to handle them.
Many of the random polygons take 20 or more seconds to complete and some look like they never will. A typical stack trace (from this polygon) when interrupted looks like this:
* thread #1: tid = 0x5c6888, 0x00000001000015cb a.out`ClipperLib::PointInPolygon(pt=0x000000010010b508, op=0x00000001005dc360) + 43 at clipper.cpp:492, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
* frame #0: 0x00000001000015cb a.out`ClipperLib::PointInPolygon(pt=0x000000010010b508, op=0x00000001005dc360) + 43 at clipper.cpp:492
frame #1: 0x000000010000dd7c a.out`ClipperLib::Clipper::FixupFirstLefts2(ClipperLib::OutRec*, ClipperLib::OutRec*) [inlined] ClipperLib::Poly2ContainsPoly1(OutPt1=<unavailable>, OutPt2=0x00000001028792a0) + 12 at clipper.cpp:533
frame #2: 0x000000010000dd70 a.out`ClipperLib::Clipper::FixupFirstLefts2(this=0x00007fff5fbff5e0, InnerOutRec=0x00000001002d1c30, OuterOutRec=0x00000001002d1e10) + 128 at clipper.cpp:3906
frame #3: 0x0000000100008e5a a.out`ClipperLib::Clipper::DoSimplePolygons(this=0x00007fff5fbff5e0) + 3274 at clipper.cpp:4995
frame #4: 0x0000000100005ed9 a.out`ClipperLib::Clipper::ExecuteInternal(this=0x00007fff5fbff5e0) + 1033 at clipper.cpp:1706
frame #5: 0x0000000100005017 a.out`ClipperLib::Clipper::Execute(this=0x00007fff5fbff5e0, clipType=<unavailable>, polytree=0x00007fff5fbff548, subjFillType=<unavailable>, clipFillType=<unavailable>) + 71 at clipper.cpp:1626
frame #6: 0x000000010001d429 a.out`main + 921 at abuse.cc:50
frame #7: 0x00007fff8f3fe5c9 libdyld.dylib`start + 1
It's not checking whether the output seems reasonable, only if it completes at all.
I think I am seeing two geometric errors (one case of intersecting polygon sides, one case of point-in-polygon showing inner ring not to be entirely inside the outer ring) in Clipper output.
In the tippecanoe earcut-polygon branch at cb4a837,
$ ./tippecanoe -z9 --check-polygons -f -o foo.mbtiles ne_10m_admin_0_countries.json > log
There must be a better way to provide sample input for Clipper problems, but this log was the best representation I could think of.
In the tippecanoe earcut-polygon branch, at e5461b1, which contains a copy of Clipper at 68c49e9:
$ ./tippecanoe -z6 -f -o foo.mbtiles ne_10m_admin_0_countries.json
For layer 0, using name "ne_10m_admin_0_countries"
254 features, 1711238 bytes of geometry, 61421 bytes of metadata, 24955 bytes of string pool
Warning: splitting up polygon with more than 700 sides
tippecanoe(20345,0x1019ec000) malloc: *** error for object 0x7fbee4918950: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
The crash claims to be in Clipper:
(lldb) bt
* thread #2: tid = 0x9b799, 0x00007fff8b147286 libsystem_kernel.dylib`__pthread_kill + 10, stop reason = signal SIGABRT
* frame #0: 0x00007fff8b147286 libsystem_kernel.dylib`__pthread_kill + 10
frame #1: 0x00007fff81e5d9f9 libsystem_pthread.dylib`pthread_kill + 90
frame #2: 0x00007fff8aa629b3 libsystem_c.dylib`abort + 129
frame #3: 0x00007fff8fbab1cb libsystem_malloc.dylib`free + 428
frame #4: 0x00000001000319f3 tippecanoe`ClipperLib::DisposeOutPts(ClipperLib::OutPt*&) + 131
frame #5: 0x0000000100038475 tippecanoe`ClipperLib::ClipperBase::DisposeOutRec(unsigned long) + 101
frame #6: 0x0000000100038318 tippecanoe`ClipperLib::ClipperBase::DisposeAllOutRecs() + 120
frame #7: 0x0000000100039883 tippecanoe`ClipperLib::Clipper::Execute(ClipperLib::ClipType, ClipperLib::PolyTree&, ClipperLib::PolyFillType, ClipperLib::PolyFillType) + 147
frame #8: 0x00000001000397dd tippecanoe`ClipperLib::Clipper::Execute(ClipperLib::ClipType, ClipperLib::PolyTree&, ClipperLib::PolyFillType) + 45
frame #9: 0x0000000100023a2d tippecanoe`clean_or_clip_poly(geom=<unavailable>, z=<unavailable>, detail=<unavailable>, buffer=<unavailable>, clip=<unavailable>) + 1613 at geometry.cc:483
frame #10: 0x0000000100012c64 tippecanoe`partial_feature_worker(v=0x00000001001ca630) + 1572 at tile.cc:544
frame #11: 0x0000000100014cca tippecanoe`write_tile(geoms=0x00000001001caec0, metabase=0x0000000100134000, stringpool=0x0000000100143000, z=1, tx=0, ty=0, detail=<unavailable>, min_detail=<unavailable>, basezoom=<unavailable>, file_keys=<unavailable>, layernames=<unavailable>, outdb=<unavailable>, droprate=2.5, buffer=<unavailable>, fname=<unavailable>, geomfile=<unavailable>, minzoom=0, maxzoom=0, todo=2508802, geomstart=<unavailable>, along=<unavailable>, gamma=0, nlayers=<unavailable>, prevent=<unavailable>, additional=<unavailable>, child_shards=0, meta_off=<unavailable>, pool_off=<unavailable>, initial_x=<unavailable>, initial_y=<unavailable>, running=<unavailable>) + 6874 at tile.cc:869
frame #12: 0x0000000100016825 tippecanoe`run_thread(vargs=0x00007fff5fbfd0d0) + 789 at tile.cc:1121
frame #13: 0x00007fff81e5c05a libsystem_pthread.dylib`_pthread_body + 131
frame #14: 0x00007fff81e5bfd7 libsystem_pthread.dylib`_pthread_start + 176
frame #15: 0x00007fff81e593ed libsystem_pthread.dylib`thread_start + 13
Since the mapnik Debian package was updated to 3.0.x, the mapnik-vector-tile package has become unusable. The recent mapnik-vector-tile releases require this clipper fork which is not available in Debian yet. The git repo cannot be cloned as part of the build process because Debian build environments have no network connectivity.
Now the question is how to best package mapnik/clipper for Debian to allow mapnik-vector-tile to build again.
The only requirement for the mapnik-vector-tile build seems to be the availability of the modified clipper.hpp
in the include paths.
We can easily install clipper.hpp
in /usr/include/mapnik
along with the other mapnik headers for example. This may not require a separate package, we can also include it as a patch in the mapnik package.
Because we already have the polyclipping library packaged in Debian (as libpolyclipping) we cannot build this mapnik fork as-is because it uses the same library name instead of something like libmapnikclipper for example. This doesn't appear to be much of an issue, because only the single header is used, not the shared library.
If my assessment is correct, would it make sense to include the fixed clipper.hpp
in the mapnik releases to not require this repository as part of the mapnik-vector-tile build?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.