mapnik / clipper Goto Github PK
View Code? Open in Web Editor NEWLicense: Boost Software License 1.0
clipper's People
Contributors
Stargazers
Watchers
clipper's Issues
Debian packaging
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?
Fuzz testing
@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.
Reproducible free-without-malloc crash
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
Unclean geometries
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.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.