mapbox / wagyu Goto Github PK

View Code? Open in Web Editor NEW

163.0 123.0 32.0 2.69 MB

A general library for geometry operations of union, intersections, difference, and xor

License: Other

C++ 94.39% Makefile 0.23% Shell 2.91% CMake 2.47%

computational-geometry union intersection xor geometry difference clipping

wagyu's Introduction

Wagyu Geometry Processing Library

Wagyu is a general library for the following basic geometric operations:

Union
Intersection
Difference
XOR

The output geometry from each of these operations is guaranteed to be valid and simple as per the OGC.

Documentation

Documentation of any library is critical to its existance and it really takes a community of effort. All of the documentation for the library is included with the library. The Wagyu project loves pull requests so please feel free to contribute at any point in time to the docs/ directory in any way you see fit! If you see a problem in documentation, at least please make an issue in the github repository.

wagyu's People

Contributors

Stargazers

Watchers

wagyu's Issues

Intersection and Snap Rounding Documentation

It is not intuitive right away how the intersection processing and the snap rounding is done in the code. Documentation should be added and put in the /docs directory of the repository.

-Weffc++ flags pointer data members without copy ctor and assignment ctor override

This warning is one of the less helpful of -Weffc++ (Added in #70), but since we set -Werror we should ideally find a way to avoid it:

include/mapbox/geometry/wagyu/bound.hpp:20:8: error: ‘struct mapbox::geometry::wagyu::bound<long int>’ has pointer data members [-Werror=effc++]
 struct bound {
        ^
include/mapbox/geometry/wagyu/bound.hpp:20:8: error:   but does not override ‘mapbox::geometry::wagyu::bound<long int>(const mapbox::geometry::wagyu::bound<long int>&)’ [-Werror=effc++]
include/mapbox/geometry/wagyu/bound.hpp:20:8: error:   or ‘operator=(const mapbox::geometry::wagyu::bound<long int>&)’ [-Werror=effc++]
cc1plus: all warnings being treated as errors

Compile with -Wsign-conversion

The -Wsign-conversion is a good warning to enable and it looks like we're missing it in the wagyu Makefile. Let's add it and fix any warnings that occur.

Enable code coverage

We should track code coverage from the start:

Enable --coverage in debug builds on travis
Enable coveralls or codecov integration

Test for 3098baa

@flippmoke
3098baa landed without a testcase that demonstrates the problem. I would have expected to see a test along with this to ensure it is working. Is that possible?

Crash in fixup_out_polygon()

pp->next == NULL in

frame #1: 0x0000000100032217 tippecanoe`void mapbox::geometry::wagyu::fixup_out_polygon<long long>(ring=0x00000001006014d0, simple=<unavailable>) + 119 at vatti.hpp:1028
   1025         }
   1026 
   1027         // test for duplicate points and collinear edges ...
-> 1028         if ((*pp == *pp->next) || (*pp == *pp->prev) ||
   1029             (slopes_equal(*pp->prev, *pp, *pp->next) &&
   1030              (!simple || !point_2_is_between_point_1_and_point_3(*pp->prev, *pp, *pp->next)))) {
   1031             lastOK = 0;

From

adding 0 to 55  
0: 1 -80 -80
1: 2 4176 -80
2: 2 4176 4176
3: 2 -80 4176
4: 2 -80 -80
adding 5 to 6
5: 1 4176 -80
(not adding)
adding 6 to 15
6: 1 4176 -80
7: 2 -80 -80
8: 2 -80 3000
9: 2 0 3040
10: 2 448 3264
11: 2 2752 3519
12: 2 4096 2990
13: 2 4176 2958
14: 2 4176 -80

next and prev: 0x0 0x7fc59ae00fc0
/bin/sh: line 1: 22155 Segmentation fault: 11  ./tippecanoe -ad -f -o tests/dateline/out/-z5.json.check.mbtiles -z5 tests/dateline/in.json < /dev/null

Investigating…

Indeterminate Results

I have noticed while running make fuzzer there are often situations where a failure occurs but it is not repeatable when running make test or make debug the saved fuzzer test does not fail. Additionally testing while using mapnik-vector-tile has shown that the results of the clip operation are changing between runs. Therefore, there is some piece of code that is not producing determinate results.

I have spent some time looking over different parts of the code attempting to find where this is being done but have not yet been able to find the problem with certainty.

Hunch - sorting

@springmeyer once brought up the fact that it might be sorting as this is a problem that he has seen before. One bug in the past was cleaned up where sorting was done on the value of a pointer, but this was removed. It is likely still that sorting could be the cause of the indeterminate results however, as sorting used in many parts of the topology correction.

The most likely sorting problem would have to do with the sorting of the different paths during self intersections.

wagyu/include/mapbox/geometry/wagyu/topology_correction.hpp

Line 1092 in 9dab09d

 std::stable_sort(angle_points.begin(), angle_points.end(), segment_angle_sorter<T>()); 

This seems like the most likely cause because it is sorting doubles that are the result of a series of operations, if the double values slightly differ between runs this could affect the sorting order.

Compatibility with g++ 4.8 (older libstdc++)

I've noticed that there is only one line of code in wagyu that prevents compilation with g++-4.8. Therefore this I think is worth fixing, if only with an #ifdef. it looks like the libstdc++ that ships with g++-4.8 does not have the signature that supports std::initializer_list. @flippmoke can you think of a clean way to avoid this usage?

./deps/wagyu/include/mapbox/geometry/wagyu/active_bound_list.hpp:115:12: error: no viable conversion from returned value of type 'void' to function return type
      'active_bound_list_itr<long>' (aka '__gnu_cxx::__normal_iterator<mapbox::geometry::wagyu::bound<long> **, std::vector<mapbox::geometry::wagyu::bound<long> *,
      std::allocator<mapbox::geometry::wagyu::bound<long> *> > >')
    return active_bounds.insert(itr, { &left, &right });

Entire error at: https://gist.github.com/springmeyer/c89c98abfaaf6f7d3ad082fbdbb3a01d

Note: I've replicated the problem on travis and attempted to fix, but failed: https://github.com/mapbox/wagyu/compare/g++-4.8

Angus Transition

The following is a rough list of the high level methods that still need to be migrated from the angus library into wagyu.

/cc @springmeyer @mapsam @jakepruitt @ericfischer @tcql

Address sanitizer failures

Clang++ -fsanitize=address finds buffer overflows with certain polygons:

=================================================================
==27858==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60d00000ce90 at pc 0x0001015110ab bp 0x7fff5e6fb050 sp 0x7fff5e6fb048
READ of size 8 at 0x60d00000ce90 thread T0
    #0 0x1015110aa in bool mapbox::geometry::wagyu::build_edge_list<long long>(mapbox::geometry::linear_ring<long long, std::__1::vector> const&, std::__1::vector<mapbox::geometry::wagyu::edge<long long>, std::__1::allocator<mapbox::geometry::wagyu::edge<long long> > >&) (fixture-tester+0x10001d0aa)
    #1 0x10150ed11 in bool mapbox::geometry::wagyu::add_linear_ring<long long>(mapbox::geometry::linear_ring<long long, std::__1::vector> const&, std::__1::deque<mapbox::geometry::wagyu::local_minimum<long long>, std::__1::allocator<mapbox::geometry::wagyu::local_minimum<long long> > >&, mapbox::geometry::wagyu::polygon_type) (fixture-tester+0x10001ad11)
    #2 0x1014f94dc in main (fixture-tester+0x1000054dc)
    #3 0x7fff98be05ac in start (libdyld.dylib+0x35ac)

0x60d00000ce90 is located 16 bytes to the left of 144-byte region [0x60d00000cea0,0x60d00000cf30)
allocated by thread T0 here:
    #0 0x10403206b in wrap__Znwm (libclang_rt.asan_osx_dynamic.dylib+0x5f06b)
    #1 0x103f062a7 in std::__1::vector<mapbox::geometry::point<long long>, std::__1::allocator<mapbox::geometry::point<long long> > >::allocate(unsigned long) (fixture-tester+0x10001a2a7)
    #2 0x103f0601f in std::__1::vector<mapbox::geometry::point<long long>, std::__1::allocator<mapbox::geometry::point<long long> > >::vector(std::__1::vector<mapbox::geometry::point<long long>, std::__1::allocator<mapbox::geometry::point<long long> > > const&) (fixture-tester+0x10001a01f)
    #3 0x103f05b8f in void std::__1::vector<mapbox::geometry::linear_ring<long long, std::__1::vector>, std::__1::allocator<mapbox::geometry::linear_ring<long long, std::__1::vector> > >::__emplace_back_slow_path<mapbox::geometry::linear_ring<long long, std::__1::vector>&>(mapbox::geometry::linear_ring<long long, std::__1::vector>&&&) (fixture-tester+0x100019b8f)
    #4 0x103eee65c in parse_file(char const*) (fixture-tester+0x10000265c)
    #5 0x103ef147e in main (fixture-tester+0x10000547e)
    #6 0x7fff98be05ac in start (libdyld.dylib+0x35ac)

SUMMARY: AddressSanitizer: heap-buffer-overflow (fixture-tester+0x10001d0aa) in bool mapbox::geometry::wagyu::build_edge_list<long long>(mapbox::geometry::linear_ring<long long, std::__1::vector> const&, std::__1::vector<mapbox::geometry::wagyu::edge<long long>, std::__1::allocator<mapbox::geometry::wagyu::edge<long long> > >&)

The failing polygons are:

tests/geometry-test-data/input-polyjson/stairstep.json
tests/geometry-test-data/input-polyjson/nz-crash2.json

To reproduce:

make clean
CXXFLAGS=-fsanitize=address LDFLAGS=-fsanitize=address CXX=/Users/enf/clang+llvm-3.9.0-x86_64-apple-darwin/bin/clang++ make test

(You may not need to set CXX if your default clang++ is newer than mine.)

STL assert while doing union for two polys

I suspect that I'm doing something fundamentally wrong.
VS2015. LLVM-vs2014 toolset has the same effect.

#define TYPE std::int64_t
mapbox::geometry::wagyu::wagyu<TYPE> Wagyu;

bool bRes;

//A	
mapbox::geometry::linear_ring<TYPE> RingA;

RingA.push_back({ 200986, 661584 });
RingA.push_back({ 100000, 670000 });
RingA.push_back({ 45000,  648310 });
RingA.push_back({ 45715,  125631 });

bRes = Wagyu.add_ring(RingA);

//B
mapbox::geometry::linear_ring<TYPE> RingB;

RingB.push_back({ 45000,   122869 });
RingB.push_back({ 45000,   648310 });
RingB.push_back({ -610000, 390000 });
RingB.push_back({ -650000, 220000 });
RingB.push_back({ -660000, 60000 });
RingB.push_back({ -610000, -320000 });
RingB.push_back({ -409999, -459999 });
RingB.push_back({ -50000,  -550000 });
RingB.push_back({ 150000,  -550000 });
RingB.push_back({ 470000,  -409999 });
RingB.push_back({ 730000,  -50000 });
RingB.push_back({ 750000,  80000 });
RingB.push_back({ 350000,  600000 });
RingB.push_back({ 227060,  656741 });
RingB.push_back({ 62080,   110243 });
RingB.push_back({ 45000,   115399 });
RingB.push_back({ 42933,   116023 });

bRes = Wagyu.add_ring(RingB);

//
mapbox::geometry::multi_polygon<TYPE> OutPolys;
bRes = Wagyu.execute(mapbox::geometry::wagyu::clip_type_union, OutPolys, mapbox::geometry::wagyu::fill_type_non_zero, mapbox::geometry::wagyu::fill_type_non_zero);

Return early if original polygons don't require fixing

In context of mapbox/mapbox-gl-native#15268: if the original polygons are correct, there is no need to provide result that reorders original and return true.
Client then constructs another container, copying and casting all returned to domain specific type... e.g
https://github.com/mapbox/mapbox-gl-native/blob/273ad436fb4d2a18c6749bd4e40fa56546e9285c/src/mbgl/tile/geometry_tile_data.cpp#L51

In context of wagyu code, bookkeeping the dirty state would enable return statement after correct_topology:

template <typename T2>
bool execute(clip_type cliptype,
                 mapbox::geometry::multi_polygon<T2>& solution,
                 fill_type subject_fill_type,
                 fill_type clip_fill_type) {

        if (minima_list.empty()) {
            return false;
        }

        ring_manager<T> manager;

        build_hot_pixels(minima_list, manager);

        execute_vatti(minima_list, manager, cliptype, subject_fill_type, clip_fill_type);

        correct_topology(manager);

        build_result(solution, manager, reverse_output);

        return true;
    }

Multipolygon test failures

The testcases seem to be filled with multipolygon test case failures on validity, but I do am not certain there is in fact any validity errors. I think this may be a bug in boost 1.61.0. I have filed a bug report with boost.

https://svn.boost.org/trac/boost/ticket/12503

Add support for double and float

Currently the wagyu algorithm only works with integers, however, with some fine tuning it might be possible to support floating point numbers.

Steps:

Polyline Support

Since the the API and functionality is intended to be similar to the Angus Clipper library, it would be good to be able to clip polylines in addition to polygons. As discussed, this will be difficult to incorporate, but it should be done.

Note the Angus docs showing clipping of a mixture of polygons with polylines:

http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/ClipType.htm

Interruption mechanism

The only thing currently blocking me to use wagyu as-is to clip and validate polygons in PostGIS is that is impossible to interrupt the library once you've given it control.
This isn't an important issue with small polygons as callee gets the control fast (because the library is fast 😉), but for really big polygons it can take several seconds of waiting (~15-20 seconds in my worst tests) until the library is done, which is indeed an issue.

To solve this I created a pretty simple interrupt header that raises an exception when the interrupt is requested (by a trap): postgis/postgis@9126fd9.

I'm wondering if this could be added to wagyu itself (via some flags to enable/disable at compile time) so I'll clean it up a bit and create a PR. What's your take on this? Does it makes sense to keep it within wagyu itself?

Test creation from fuzzer

The ideal solution here would be the creation of a new test fixture each time that fuzzer fails (with a flag to do so). Basically it is very difficult to debug single tests in the fuzzer currently because they might be many iterations from the initial seed value.

/cc @ericfischer

Create Proper README

Make a proper readme that explains the project entirely.

Mapbox Issue with snapping of LineString to the actual road

I am not sure if this is an issue or not, cause Google does not seem to have much on Mapbox documentation and examples.

So am trying to show route directions in Mapbox using the Directions API, but the geometry coordinates returned back does not snap to the road properly like how an actual navigation App would do, it's showing a straight line and totally ignores the corners and curves of roads

, maybe am doing this wrong or am missing function or something.

add a CONTRIBUTING.md

Hey @springmeyer @flippmoke @ericfischer @tcql @mourner @jakepruitt how do I contribute to this project?

Fixture tester should not access invalid array entries

The fixture tester is not careful to check that the coordinate arrays it is parsing in this loop:

wagyu/tests/fixture-tester.cpp

Lines 105 to 107 in c1efc21

 for (SizeType j = 0; j < document[i].Size(); ++j) { 

 lr.push_back({ document[i][j][0].GetInt(), document[i][j][1].GetInt() }); 

 }

have both X and Y values. This means that an invalid JSON file like:

[
    [
   [-2500],
     [-2500.20], [-25250000,-2,-2500],
   [-2500.2500],
   [250062500],
   [2500,-2560],[-2500,-2500] ]
]

Will result in bogus values in release mode like:

-2500 0
1717986918 0
-25250000 -2
0 250062500
250062500 2500
2500 -2560
-2500 -2500

^^ generated by doing:

diff --git a/tests/fixture-tester.cpp b/tests/fixture-tester.cpp
index 02036d7..b1dde95 100644
--- a/tests/fixture-tester.cpp
+++ b/tests/fixture-tester.cpp
@@ -103,6 +103,7 @@ mapbox::geometry::polygon<value_type> parse_file(const char* file_path) {
                                      ") is not a valid json array");
         }
         for (SizeType j = 0; j < document[i].Size(); ++j) {
+            std::clog << document[i][j][0].GetInt() << " " << document[i][j][1].GetInt() << "\n";
             lr.push_back({ document[i][j][0].GetInt(), document[i][j][1].GetInt() });
         }
         poly.emplace_back(lr);

And in debug mode rapidjson catches the problem:

Assertion failed: (index < data_.a.size), function operator[], file mason_packages/headers/rapidjson/1.1.0/include/rapidjson/document.h, line 1498.

Initial set of benchmarks

We need an good set of benchmarks to judge performance of wagyu vs the angus clipper (and to judge performance differences in releases). This could be similar in some ways to the benchmarks in MVT.

Goals for this benchmark would be:

Runs on Travis with rough "test" for performance
Tests geometry that is:
- Very complex with large numbers of intersections
- Has many different rings with many vertices
- Has a small number of vertices (similar to amount of data in "normal vector tile")
- Tests all data in fixtures? (expected times?)
- "No change" in geometry test (if no fixes are made on a normal geometry how long does it take normally?)
Tests all types of operations and fill types

/cc @jakepruitt

Recent large code coverage changes

After #89 merged coverage dropped from 94% to 44%:

Before:

After:

@flippmoke is this expected?

G++ -Wconversion warnings

We should enable -Wconversion since:

It enables a large subset of useful conversion warnings
Works with both g++ and clang++ (each enable different warnings they support)

The group of sub-warnings enabled by clang++ are documented at https://clang.llvm.org/docs/DiagnosticsReference.html#wconversion

These are the warning we'll need to fix to be able to enable this option with g++:

g++-4.9 -O3 -DNDEBUG tests/test.cpp tests/unit/*.cpp -Wall -Wextra -Weffc++ -Werror -Wsign-compare -Wfloat-equal -Wconversion -Wshadow  -Iinclude -isystem mason_packages/.link/include -std=c++11 -isystem ./tests -o test
In file included from tests/unit/quick_clip.cpp:4:0:
include/mapbox/geometry/wagyu/quick_clip.hpp: In instantiation of 'mapbox::geometry::point<T> mapbox::geometry::wagyu::quick_clip::intersect(mapbox::geometry::point<T>, mapbox::geometry::point<T>, size_t, const mapbox::geometry::box<T>&) [with T = long int; size_t = long unsigned int]':
include/mapbox/geometry/wagyu/quick_clip.hpp:74:62:   required from 'mapbox::geometry::linear_ring<T> mapbox::geometry::wagyu::quick_clip::quick_lr_clip(const mapbox::geometry::linear_ring<T>&, const mapbox::geometry::box<T>&) [with T = long int]'
tests/unit/quick_clip.cpp:40:75:   required from here
include/mapbox/geometry/wagyu/quick_clip.hpp:21:65: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.x + static_cast<double>(b.x - a.x) * (box.min.y - a.y) / (b.y - a.y)),
                                                                 ^
include/mapbox/geometry/wagyu/quick_clip.hpp:21:85: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.x + static_cast<double>(b.x - a.x) * (box.min.y - a.y) / (b.y - a.y)),
                                                                                     ^
include/mapbox/geometry/wagyu/quick_clip.hpp:21:32: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.x + static_cast<double>(b.x - a.x) * (box.min.y - a.y) / (b.y - a.y)),
                                ^
include/mapbox/geometry/wagyu/quick_clip.hpp:27:65: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.y + static_cast<double>(b.y - a.y) * (box.max.x - a.x) / (b.x - a.x)));
                                                                 ^
include/mapbox/geometry/wagyu/quick_clip.hpp:27:85: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.y + static_cast<double>(b.y - a.y) * (box.max.x - a.x) / (b.x - a.x)));
                                                                                     ^
include/mapbox/geometry/wagyu/quick_clip.hpp:27:32: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.y + static_cast<double>(b.y - a.y) * (box.max.x - a.x) / (b.x - a.x)));
                                ^
include/mapbox/geometry/wagyu/quick_clip.hpp:31:65: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.x + static_cast<double>(b.x - a.x) * (box.max.y - a.y) / (b.y - a.y)),
                                                                 ^
include/mapbox/geometry/wagyu/quick_clip.hpp:31:85: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.x + static_cast<double>(b.x - a.x) * (box.max.y - a.y) / (b.y - a.y)),
                                                                                     ^
include/mapbox/geometry/wagyu/quick_clip.hpp:31:32: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.x + static_cast<double>(b.x - a.x) * (box.max.y - a.y) / (b.y - a.y)),
                                ^
include/mapbox/geometry/wagyu/quick_clip.hpp:37:65: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.y + static_cast<double>(b.y - a.y) * (box.min.x - a.x) / (b.x - a.x)));
                                                                 ^
include/mapbox/geometry/wagyu/quick_clip.hpp:37:85: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.y + static_cast<double>(b.y - a.y) * (box.min.x - a.x) / (b.x - a.x)));
                                                                                     ^
include/mapbox/geometry/wagyu/quick_clip.hpp:37:32: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             static_cast<T>(a.y + static_cast<double>(b.y - a.y) * (box.min.x - a.x) / (b.x - a.x)));
                                ^
In file included from include/mapbox/geometry/wagyu/wagyu.hpp:14:0,
                 from include/mapbox/geometry/wagyu/quick_clip.hpp:6,
                 from tests/unit/quick_clip.cpp:4:
include/mapbox/geometry/wagyu/snap_rounding.hpp: In instantiation of 'bool mapbox::geometry::wagyu::horizontals_at_top_scanbeam(T, mapbox::geometry::wagyu::active_bound_list_itr<T>&, mapbox::geometry::wagyu::active_bound_list<T>&, mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int; mapbox::geometry::wagyu::active_bound_list_itr<T> = __gnu_cxx::__normal_iterator<mapbox::geometry::wagyu::bound<long int>**, std::vector<mapbox::geometry::wagyu::bound<long int>*, std::allocator<mapbox::geometry::wagyu::bound<long int>*> > >; mapbox::geometry::wagyu::active_bound_list<T> = std::vector<mapbox::geometry::wagyu::bound<long int>*, std::allocator<mapbox::geometry::wagyu::bound<long int>*> >]':
include/mapbox/geometry/wagyu/snap_rounding.hpp:111:88:   required from 'void mapbox::geometry::wagyu::process_hot_pixel_edges_at_top_of_scanbeam(T, mapbox::geometry::wagyu::scanbeam_list<T>&, mapbox::geometry::wagyu::active_bound_list<T>&, mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int; mapbox::geometry::wagyu::scanbeam_list<T> = std::vector<long int, std::allocator<long int> >; mapbox::geometry::wagyu::active_bound_list<T> = std::vector<mapbox::geometry::wagyu::bound<long int>*, std::allocator<mapbox::geometry::wagyu::bound<long int>*> >]'
include/mapbox/geometry/wagyu/snap_rounding.hpp:188:96:   required from 'void mapbox::geometry::wagyu::build_hot_pixels(mapbox::geometry::wagyu::local_minimum_list<T>&, mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int; mapbox::geometry::wagyu::local_minimum_list<T> = std::deque<mapbox::geometry::wagyu::local_minimum<long int>, std::allocator<mapbox::geometry::wagyu::local_minimum<long int> > >]'
include/mapbox/geometry/wagyu/wagyu.hpp:128:46:   required from 'bool mapbox::geometry::wagyu::wagyu<T>::execute(mapbox::geometry::wagyu::clip_type, mapbox::geometry::multi_polygon<T2>&, mapbox::geometry::wagyu::fill_type, mapbox::geometry::wagyu::fill_type) [with T2 = long int; T = long int]'
tests/unit/quick_clip.cpp:268:86:   required from here
include/mapbox/geometry/wagyu/snap_rounding.hpp:63:59: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
                 wround<T>((*bnd_next)->current_edge->bot.y) != top_y) {
                                                           ^
include/mapbox/geometry/wagyu/snap_rounding.hpp:62:83: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             if (*bnd_next != nullptr && wround<T>((*bnd_next)->current_edge->top.y) != top_y &&
                                                                                   ^
include/mapbox/geometry/wagyu/snap_rounding.hpp:79:63: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
                     wround<T>((*bnd_prev)->current_edge->bot.y) != top_y) {
                                                               ^
include/mapbox/geometry/wagyu/snap_rounding.hpp:78:87: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
                 if (*bnd_prev != nullptr && wround<T>((*bnd_prev)->current_edge->top.y) != top_y &&
                                                                                       ^
In file included from include/mapbox/geometry/wagyu/build_result.hpp:4:0,
                 from include/mapbox/geometry/wagyu/wagyu.hpp:11,
                 from include/mapbox/geometry/wagyu/quick_clip.hpp:6,
                 from tests/unit/quick_clip.cpp:4:
include/mapbox/geometry/wagyu/ring_util.hpp: In instantiation of 'mapbox::geometry::point<double> mapbox::geometry::wagyu::centroid_of_points(mapbox::geometry::wagyu::point_ptr<T>) [with T = long int; mapbox::geometry::wagyu::point_ptr<T> = mapbox::geometry::wagyu::point<long int>*]':
include/mapbox/geometry/wagyu/ring_util.hpp:810:45:   required from 'mapbox::geometry::wagyu::point_in_polygon_result mapbox::geometry::wagyu::inside_or_outside_special(mapbox::geometry::wagyu::point_ptr<T>, mapbox::geometry::wagyu::point_ptr<T>) [with T = long int; mapbox::geometry::wagyu::point_ptr<T> = mapbox::geometry::wagyu::point<long int>*]'
include/mapbox/geometry/wagyu/ring_util.hpp:847:75:   required from 'bool mapbox::geometry::wagyu::poly2_contains_poly1(mapbox::geometry::wagyu::ring_ptr<T>, mapbox::geometry::wagyu::ring_ptr<T>) [with T = long int; mapbox::geometry::wagyu::ring_ptr<T> = mapbox::geometry::wagyu::ring<long int>*]'
include/mapbox/geometry/wagyu/topology_correction.hpp:1313:50:   required from 'void mapbox::geometry::wagyu::correct_tree(mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int]'
include/mapbox/geometry/wagyu/topology_correction.hpp:1359:25:   required from 'void mapbox::geometry::wagyu::correct_topology(mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int]'
include/mapbox/geometry/wagyu/wagyu.hpp:132:33:   required from 'bool mapbox::geometry::wagyu::wagyu<T>::execute(mapbox::geometry::wagyu::clip_type, mapbox::geometry::multi_polygon<T2>&, mapbox::geometry::wagyu::fill_type, mapbox::geometry::wagyu::fill_type) [with T2 = long int; T = long int]'
tests/unit/quick_clip.cpp:268:86:   required from here
include/mapbox/geometry/wagyu/ring_util.hpp:796:44: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
     return { (prev->x + edge->x + next->x) / 3.0, (prev->y + edge->y + next->y) / 3.0 };
                                            ^
include/mapbox/geometry/wagyu/ring_util.hpp:796:81: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
     return { (prev->x + edge->x + next->x) / 3.0, (prev->y + edge->y + next->y) / 3.0 };
                                                                                 ^
cc1plus: all warnings being treated as errors
In file included from include/mapbox/geometry/wagyu/wagyu.hpp:14:0,
                 from tests/unit/vatti.cpp:5:
include/mapbox/geometry/wagyu/snap_rounding.hpp: In instantiation of 'bool mapbox::geometry::wagyu::horizontals_at_top_scanbeam(T, mapbox::geometry::wagyu::active_bound_list_itr<T>&, mapbox::geometry::wagyu::active_bound_list<T>&, mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int; mapbox::geometry::wagyu::active_bound_list_itr<T> = __gnu_cxx::__normal_iterator<mapbox::geometry::wagyu::bound<long int>**, std::vector<mapbox::geometry::wagyu::bound<long int>*, std::allocator<mapbox::geometry::wagyu::bound<long int>*> > >; mapbox::geometry::wagyu::active_bound_list<T> = std::vector<mapbox::geometry::wagyu::bound<long int>*, std::allocator<mapbox::geometry::wagyu::bound<long int>*> >]':
include/mapbox/geometry/wagyu/snap_rounding.hpp:111:88:   required from 'void mapbox::geometry::wagyu::process_hot_pixel_edges_at_top_of_scanbeam(T, mapbox::geometry::wagyu::scanbeam_list<T>&, mapbox::geometry::wagyu::active_bound_list<T>&, mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int; mapbox::geometry::wagyu::scanbeam_list<T> = std::vector<long int, std::allocator<long int> >; mapbox::geometry::wagyu::active_bound_list<T> = std::vector<mapbox::geometry::wagyu::bound<long int>*, std::allocator<mapbox::geometry::wagyu::bound<long int>*> >]'
include/mapbox/geometry/wagyu/snap_rounding.hpp:188:96:   required from 'void mapbox::geometry::wagyu::build_hot_pixels(mapbox::geometry::wagyu::local_minimum_list<T>&, mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int; mapbox::geometry::wagyu::local_minimum_list<T> = std::deque<mapbox::geometry::wagyu::local_minimum<long int>, std::allocator<mapbox::geometry::wagyu::local_minimum<long int> > >]'
include/mapbox/geometry/wagyu/wagyu.hpp:128:46:   required from 'bool mapbox::geometry::wagyu::wagyu<T>::execute(mapbox::geometry::wagyu::clip_type, mapbox::geometry::multi_polygon<T2>&, mapbox::geometry::wagyu::fill_type, mapbox::geometry::wagyu::fill_type) [with T2 = long int; T = long int]'
tests/unit/vatti.cpp:15:5:   required from here
include/mapbox/geometry/wagyu/snap_rounding.hpp:63:59: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
                 wround<T>((*bnd_next)->current_edge->bot.y) != top_y) {
                                                           ^
include/mapbox/geometry/wagyu/snap_rounding.hpp:62:83: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
             if (*bnd_next != nullptr && wround<T>((*bnd_next)->current_edge->top.y) != top_y &&
                                                                                   ^
include/mapbox/geometry/wagyu/snap_rounding.hpp:79:63: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
                     wround<T>((*bnd_prev)->current_edge->bot.y) != top_y) {
                                                               ^
include/mapbox/geometry/wagyu/snap_rounding.hpp:78:87: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
                 if (*bnd_prev != nullptr && wround<T>((*bnd_prev)->current_edge->top.y) != top_y &&
                                                                                       ^
In file included from include/mapbox/geometry/wagyu/build_result.hpp:4:0,
                 from include/mapbox/geometry/wagyu/wagyu.hpp:11,
                 from tests/unit/vatti.cpp:5:
include/mapbox/geometry/wagyu/ring_util.hpp: In instantiation of 'mapbox::geometry::point<double> mapbox::geometry::wagyu::centroid_of_points(mapbox::geometry::wagyu::point_ptr<T>) [with T = long int; mapbox::geometry::wagyu::point_ptr<T> = mapbox::geometry::wagyu::point<long int>*]':
include/mapbox/geometry/wagyu/ring_util.hpp:810:45:   required from 'mapbox::geometry::wagyu::point_in_polygon_result mapbox::geometry::wagyu::inside_or_outside_special(mapbox::geometry::wagyu::point_ptr<T>, mapbox::geometry::wagyu::point_ptr<T>) [with T = long int; mapbox::geometry::wagyu::point_ptr<T> = mapbox::geometry::wagyu::point<long int>*]'
include/mapbox/geometry/wagyu/ring_util.hpp:847:75:   required from 'bool mapbox::geometry::wagyu::poly2_contains_poly1(mapbox::geometry::wagyu::ring_ptr<T>, mapbox::geometry::wagyu::ring_ptr<T>) [with T = long int; mapbox::geometry::wagyu::ring_ptr<T> = mapbox::geometry::wagyu::ring<long int>*]'
include/mapbox/geometry/wagyu/topology_correction.hpp:1313:50:   required from 'void mapbox::geometry::wagyu::correct_tree(mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int]'
include/mapbox/geometry/wagyu/topology_correction.hpp:1359:25:   required from 'void mapbox::geometry::wagyu::correct_topology(mapbox::geometry::wagyu::ring_manager<T>&) [with T = long int]'
include/mapbox/geometry/wagyu/wagyu.hpp:132:33:   required from 'bool mapbox::geometry::wagyu::wagyu<T>::execute(mapbox::geometry::wagyu::clip_type, mapbox::geometry::multi_polygon<T2>&, mapbox::geometry::wagyu::fill_type, mapbox::geometry::wagyu::fill_type) [with T2 = long int; T = long int]'
tests/unit/vatti.cpp:15:5:   required from here
include/mapbox/geometry/wagyu/ring_util.hpp:796:44: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
     return { (prev->x + edge->x + next->x) / 3.0, (prev->y + edge->y + next->y) / 3.0 };
                                            ^
include/mapbox/geometry/wagyu/ring_util.hpp:796:81: error: conversion to 'double' from 'long int' may alter its value [-Werror=conversion]
     return { (prev->x + edge->x + next->x) / 3.0, (prev->y + edge->y + next->y) / 3.0 };
                                                                                 ^
cc1plus: all warnings being treated as errors
make: *** [build-test] Error 1

Re-running Wagyu on its own output sometimes makes additional changes

tests/geometry-test-data/input-polyjson/croatia1.json is an uncleaned border polygon for Croatia at z0, the one that Tippecanoe calls Wagyu to clean when you run

grep Croatia tests/border/in.json | ./tippecanoe -z1 --detect-shared-borders -f -o foo.mbtiles

If you run Wagyu on this polygon:

./fixture-tester -t union -f positive tests/geometry-test-data/input-polyjson/croatia1.json

you get the cleaned polygon in tests/geometry-test-data/input-polyjson/croatia2.json. However, if you rerun Wagyu on that second polygon:

./fixture-tester -t union -f positive tests/geometry-test-data/input-polyjson/croatia2.json

you get a third polygon, the one in tests/geometry-test-data/input-polyjson/croatia3.json. If you run Wagyu again on the third polygon, it is stable and you get an identical polygon back.

I had expected that giving Wagyu a strictly simple polygon that was previously the output of Wagyu would return the identical polygon rather than making additional changes to it.

Master Ticket Towards - 1.0

This is the master ticket to discuss what needs to be done prior to releasing version 1.0 of wagyu. Updates to follow

Add test assertions on # of allocations

Idea:

We could have the unit tests override C++ new operator and then track allocations
Assert on the total count
- Hopefully it is stable across platforms?
- It will change as more tests get written - so we'll have to update it
- Or, only track allocations in a single, standlone unit test which would require the # be updated when the core implementation changes (ideally only dropping # of allocations required to process a given polygon)

Compare against PostGIS MakeValid()

It would be very interesting to see how Wagyu compares against GEOS/MakeValid in PostGIS both from performance and accuracy. It seems that the method for PostGIS is located here and perhaps it could be extracted and put into a benchmark.

First step would be to determine how to use this method in a standalone fashion if possible.

/cc @pramsey @strk

Possible null pointer dereference in add_ring_to_local_minima_list()

Xcode 8.3.3 reports a static analyzer warning in mbgl-core in mapbox/mapbox-gl-native@19e872b caused by a call to wagyu::add_ring():

/path/to/mapbox-gl-native/src/mbgl/tile/geometry_tile_data.cpp:45:9: Access to field 'maximum_bound' results in a dereference of a null pointer (loaded from variable 'last_maximum') (within a call to 'add_ring')
/path/to/mapbox-gl-native/src/mbgl/tile/geometry_tile_data.cpp:44:27: Entering loop body
/path/to/mapbox-gl-native/src/mbgl/tile/geometry_tile_data.cpp:45:9: Calling 'wagyu::add_ring'
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/wagyu.hpp:47:5: Entered call from 'fixupPolygons'
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/wagyu.hpp:49:16: Calling 'add_linear_ring'
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/build_local_minima_list.hpp:13:1: Entered call from 'wagyu::add_ring'
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/build_local_minima_list.hpp:18:9: Assuming the condition is false
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/build_local_minima_list.hpp:18:63: Assuming the condition is false
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/build_local_minima_list.hpp:21:5: Calling 'add_ring_to_local_minima_list'
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/local_minimum_util.hpp:202:1: Entered call from 'add_linear_ring'
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/local_minimum_util.hpp:206:9: Assuming the condition is false
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/local_minimum_util.hpp:214:5: 'last_maximum' initialized to a null pointer value
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/local_minimum_util.hpp:215:12: Assuming the condition is false
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/local_minimum_util.hpp:215:12: Loop body executed 0 times
/path/to/mapbox-gl-native/mason_packages/headers/wagyu/0.4.1/include/mapbox/geometry/wagyu/local_minimum_util.hpp:294:33: Access to field 'maximum_bound' results in a dereference of a null pointer (loaded from variable 'last_maximum')

/cc @flippmoke @kkaefer

Enable clang sanitizers on travis

We now have Debug builds on Travis (#2) - further step is to enable running key sanitizers per commit:

-fsanitize=address (with leak checking)
-fsanitize=integer

Pull mapbox::geometry via mason package

Instead of bundling mapbox::geometry (aka https://github.com/mapbox/geometry.hpp) we should install via its mason package.

Wagyu should only compile with integer type coordinates

Use static_assert or similar compile-time guard to prevent compilation with float and double

Visualize Differences in Fixture Tests

We had the start of some work towards using https://github.com/mapnik/geometry-test-data/ for fixture testing as part of Wagyu and this is excellent! However, it is very difficult to see differences in the results from wagyu currently as we can not visually inspect the differences quickly. Additionally the input and output formats are not in a format that can be easily loaded into other software. Perhaps updating this to be geojson or another format?

/cc @tcql @jakepruitt

Wrong points retained in polygon with many collinear edges

So that I don't lose track of it…

Reproduce with

make build-fixture-tester && ./fixture-tester -t union -f non_zero input.geojson.txt

Increase Difficulty of Fuzzer

Currently we only generate a single ring of random points, perhaps this doesn't cover all the possible edge cases. It might be a good choice to change this to multiple rings?

Example Input Currently:

Example Output Currently:

Drops small polygons

I have a geometry that is producing invalid outputs when intersecting it with others or itself.

Here is an example of an intersection that works. Since I'm intersecting a polygon (POLYGON((0 0, 0 10, 10 10, 10 0, 0 0)) with itself, I'm expecting the result to be the same polygon):

Click to expand

TEST_CASE("Self intersection (OK)") {

    mapbox::geometry::linear_ring<std::int64_t> ring0_0;

    ring0_0.push_back(mapbox::geometry::point<std::int64_t>( 0, 0));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>( 0, 10));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(10, 10));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(10, 0));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>( 0, 0));

    mapbox::geometry::polygon<std::int64_t> pol0;
    pol0.push_back(ring0_0);

    mapbox::geometry::linear_ring<std::int64_t> ring1_0;
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>( 0, 0));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>( 0, 10));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(10, 10));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(10, 0));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>( 0, 0));

    mapbox::geometry::polygon<std::int64_t> pol1;
    pol1.push_back(ring1_0);

    mapbox::geometry::wagyu::wagyu<std::int64_t> wagyu;

    wagyu.add_polygon(pol0, mapbox::geometry::wagyu::polygon_type::polygon_type_subject);
    wagyu.add_polygon(pol1, mapbox::geometry::wagyu::polygon_type::polygon_type_clip);

    mapbox::geometry::multi_polygon<std::int64_t> solution;
    wagyu.execute(mapbox::geometry::wagyu::clip_type_intersection, solution, mapbox::geometry::wagyu::fill_type_even_odd,
                  mapbox::geometry::wagyu::fill_type_even_odd);

    REQUIRE(solution.size() == 1);
    REQUIRE(solution[0].size() == 1);
    REQUIRE(solution[0][0].size() == 5);
}

$ ./cmake-build/unit-tests "Self intersection (OK)"
===============================================================================
All tests passed (3 assertions in 1 test case)

On the other hand, when I change the geometry to this one: POLYGON((1252 1904,1253 1905,1253 1906,1251 1904,1252 1904)) what I don't get anything out of the intersection with itself:

Click to expand

TEST_CASE("Self intersection (KO)") {

    mapbox::geometry::linear_ring<std::int64_t> ring0_0;

    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(1252, 1904));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(1253, 1905));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(1253, 1906));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(1251, 1904));
    ring0_0.push_back(mapbox::geometry::point<std::int64_t>(1252, 1904));

    mapbox::geometry::polygon<std::int64_t> pol0;
	pol0.push_back(ring0_0);

    mapbox::geometry::linear_ring<std::int64_t> ring1_0;
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(1252, 1904));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(1253, 1905));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(1253, 1906));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(1251, 1904));
    ring1_0.push_back(mapbox::geometry::point<std::int64_t>(1252, 1904));

    mapbox::geometry::polygon<std::int64_t> pol1;
    pol1.push_back(ring1_0);

    mapbox::geometry::wagyu::wagyu<std::int64_t> wagyu;

    wagyu.add_polygon(pol0, mapbox::geometry::wagyu::polygon_type::polygon_type_subject);
    wagyu.add_polygon(pol1, mapbox::geometry::wagyu::polygon_type::polygon_type_clip);

    mapbox::geometry::multi_polygon<std::int64_t> solution;
    wagyu.execute(mapbox::geometry::wagyu::clip_type_intersection, solution, mapbox::geometry::wagyu::fill_type_even_odd,
                  mapbox::geometry::wagyu::fill_type_even_odd);

    REQUIRE(solution.size() == 1);
    REQUIRE(solution[0].size() == 1);
    REQUIRE(solution[0][0].size() == 5);
}

./cmake-build/unit-tests "Self intersection (KO)"

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
unit-tests is a Catch v1.9.6 host application.
Run with -? for options

-------------------------------------------------------------------------------
Self intersection (KO)
-------------------------------------------------------------------------------
/home/raul/dev/public/wagyu/tests/unit/vatti.cpp:443
...............................................................................

/home/raul/dev/public/wagyu/tests/unit/vatti.cpp:475: FAILED:
  REQUIRE( solution.size() == 1 )
with expansion:
  0 == 1

===============================================================================
test cases: 1 | 1 failed
assertions: 1 | 1 failed

In both cases the geometries are identical, but in one the intersection works as expected while in the other one it doesn't.

In the second case, if I remove correct_topology the resulting polygon has the following points:

So at some point, the algorithm has decided to turn back around (1253 1905 => 1253 1906 => 1253 1905) instead of continuing its path.

A similar thing happens if I intersect the bad polygon with its bounding box or with a bigger box (in my case an standard mvt tile (0 0, 4096 4096).

Is the code to calculate the intersection correct?

I'm investigating what's causing the issue so any pointers are greatly welcomed.

Input and output rings have opposite winding

https://github.com/mapbox/wagyu/blob/ring-orientation/tests/orient.cpp contains a simple example of asking wagyu to process a single ring. The input ring is

(0,0), (1,0), (1,1), (0,1), (0,0)

and the output is

(1,0), (0,0), (0,1), (1,1), (1,0)

If it isn't clear, the problem is that the points are in the opposite order in the input and the output. (They also start counting from a different point around the ring, but that is fine and expected.)

cc @flippmoke

Assign to `nullptr` rather than zero

We should assign to nullptr in these cases for best C++11 style rather than zero:

wagyu/include/mapbox/geometry/wagyu/ring_util.hpp

Lines 488 to 496 in bfbf289

 point_ptr<T> dups = 0; 

 point_ptr<T> p = pp->next; 

 while (p != pp) { 

 if (p->y > pp->y) { 

 pp = p; 

 dups = 0; 

 } else if (p->y == pp->y && p->x <= pp->x) { 

 if (p->x < pp->x) { 

 dups = 0;

Feature request: another set of add_xxx functions

Is it possible to have another set of add_xxx functions like:

bool add_ring (const void* vertices, int stride, int num_vertices, polygon_type p_type);

The main purpose of this is perf gain due to lack of data conversion.
I think people that write real time applications (ex.: game developers) will be grateful for this.

Endless Loop - Looping Rings

Found an endless loop in the fuzzer, unfortunately it doesn't create a test in this event. Here is the sample:

It seems this is likely a situation where a child parent relationship is causing a loop.

dispose_out_points never called

The dispose_out_points function is never called in the fixture tests or unit tests. Are we missing test for this code, or is it unneeded?

Handle SIGINT in fuzzer or exit cleanly at max iterations

I'm working on looking at the % of code coverage the fuzzer hits. The way llvm-cov works if you ctrl-c a process no coverage data is output. So I'm going to look at adding SIGINT handling to the fuzzer. Another option I considered was adding a max iterations option to the fuzzer and gracefully exiting when that is hit.

decide fixture-tester output

Right now fixture-tester takes input as flat arrays of rings:

[
    [[-79102, 0],[-70312, -55285],[85254, -30747],[58008, 80592],[-79102, 0]],
    [[44824, 42149],[51855, -21089],[-65918, -32502],[-50098, 4394],[44824, 42149]],
    [[-40430, -3076],[-26367, -18454],[34277, -4834],[33838, 17136],[-40430, -3076]]
]

with no extra nesting for boundaries vs holes.

At the moment, it outputs nested structures:

[
    [
        [[-70312,-55285],[-79102,0],[58008,80592],[85254,-30747],[-70312,-55285]],
        [[-65918,-32502],[51855,-21089],[44824,42149],[-50098,4394],[-65918,-32502]]
    ],
    [
        [[10547,-19771],[-5728,-13819],[-26367,-18454],[-40430,-3076],[-12792,4446],[4834,19771],[19761,13305],[33838,17136],[34277,-4834],[18998,-8265],[10547,-19771]]
    ]
]

. Should we keep input and output formats the same? Nested output is useful for converting to geojson, since a geojson converter would only need to wrap the structures in geometry objects. A flat list of rings means that geojson converters would need to detect which rings are holes within which other polygons.

/cc @jakepruitt @flippmoke @ericfischer @mourner

clang format

Let's set up Clang formatter (e.g. pulling options from https://github.com/mapbox/mapbox-gl-native/blob/master/.clang-format), and then use that throughout the code so that it has consistent formatting style. cc @flippmoke

Investigate if bounding box check makes quick_clip faster

For features that are completely inside a bounding box, it might be faster to simply copy the entire feature at once rather then running through the quick clipping algorithm. However, this would add overhead of search if feature is entirely in a bounding box prior to doing this operation, so it might make operations slower on the whole. This ticket is to investigate the performance of each option.

Method in quesiton: mapbox::geometry::wagyu::quick_clip::quick_lr_clip

Ref: mapbox/mapnik-vector-tile#126

No usage of `reverse_output` in push_ring_to_polygon

It appears that push_ring_to_polygon has a reverse_output argument that is never passed and therefore the code for this is fully uncovered. Should this be removed?

Update License

Update the license such that it properly includes the angus libraries license and put license as necessary into project.

documentation!

Documenting this whole thing is going to be epic. A very general, evolving list of things to keep in mind (please edit inline!):

All purpose API docs - for now we are not thinking about inline documentation (i.e. documentationjs).
- API.md
- C++ examples
- JS examples
installation, os & compiler requirements #48
README.md - wat even is this thing #4
CONTRIBUTING.md #10
developer docs around algorithm choices, code structure, tests, etc. - possibly in a separate repo?

cc @springmeyer @mourner @tcql @flippmoke @jakepruitt @GretaCB @ericfischer

Removing atan2 - Better Self Intersection Process Ordering

A new way to determine the order of self intersections processing order at a single point that does not use std::atan2 would be wonderful for many reasons. One is that std::atan2 is slow to calculate and the accuracy of its results is questionable.

The Fundamental Assumption

The resulting rings from the vatti processing are guaranteed to never result in the path of a ring crossing with itself. While the path might be collinear or share intersection points that need to be cleaned up, it does not ever result in an "crossing intersection".

The image below shows a single ring - this is not a crossing intersection because the pairing of any two segments (one being towards, one being away) does not result in the path crossing over itself.

The next image however is an example of a crossing intersection.

Notice how no pair of towards and away paths can be selected such that the paths do not cross.

This is important for one reason - splitting a ring into two distinct rings is the critical part of self intersection processing and if an intersection is crossing the two resulting rings will be crossing each other such that one ring could be partial inside the other. This makes it MUCH more difficult to properly determine parent child relationship of the resulting rings.

When crossing intersections occur

Crossing intersections could possibly occur when a self intersection of a ring at a single point has more then 2 paths through the point. The following is an example of where this can occur.

It is difficult to visualize the original path with out "spreading out" the points that intersect ever so slightly (this is shown below).

Assuming that we labeled each of the intersection points from left to right in the picture above as A, B, C, D. Lets explore how the order of the self intersection processing can result in intersections.

What does self intersection processing do?

At its core self intersections are corrected by swapping where each intersection point will travel to next. This can be seen here.

    // split the polygon into two ...
    point_ptr<T> op3 = op->prev;
    point_ptr<T> op4 = op2->prev;
    op->prev = op4;
    op4->next = op;
    op2->prev = op3;
    op3->next = op2;

If we processed A and B together first it will result in the creation of a new ring as shown below:

This is proper because the resulting two rings -- are either completely within or completely outside of the other ring. Notice as well that when we zoom in there are still no crossing intersections.

However, lets say we attempt now to process B and D. Hint: this will result in a crossing intersection.

## Preventing Crossing Intersections

In order to prevent this from occuring, self intersections should only be performed between any two paths selected for another intersection where there is no other path that would bisect them! To determine this the angles of each of the segments is first measured and sorted. After this a pair of paths is found that satisfies this requirement.

However, this is an often repeated process and repeated calls to atan2 are required.

Optimizing the code could result in performance increases such that atan2 could be called less, but if a sorting method that avoided floating point numbers could be avoided this would be much better as currently this methodology seems to be making indeterminate results in the outputs of wagyu.

/cc @mourner @ericfischer

Fuzzing

In addition to the testing work coming together in #25 we should port over the fuzzer work from mapnik/clipper#3 to ensure we root out potential crashes and hangs on nasty input.

	for (SizeType j = 0; j < document[i].Size(); ++j) {
	lr.push_back({ document[i][j][0].GetInt(), document[i][j][1].GetInt() });
	}

	point_ptr<T> dups = 0;
	point_ptr<T> p = pp->next;
	while (p != pp) {
	if (p->y > pp->y) {
	pp = p;
	dups = 0;
	} else if (p->y == pp->y && p->x <= pp->x) {
	if (p->x < pp->x) {
	dups = 0;