Donot embed earcut.hpp (#313)

* Do not embed mapbox/earcut.hpp.

* Fix python binding build.

* Fix python binding build on Azure pipeline

* Include <array>.
Use compiler-specific compile flags in python module build.

* format python code.

9 files changed, 906 insertions, 865 deletions

diff --git a/LICENSE b/LICENSE
index 3af18ab..e9fbe44 100644
--- a/LICENSE
+++ b/LICENSE
@@ -19,3 +19,24 @@ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 THE SOFTWARE.
+
+----------------------------------
+
+mapbox/earcut.hpp
+
+ISC License
+
+Copyright (c) 2015, Mapbox
+
+Permission to use, copy, modify, and/or distribute this software for any purpose
+with or without fee is hereby granted, provided that the above copyright notice
+and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+THIS SOFTWARE.
+
diff --git a/README.md b/README.md
index bfd902c..94c7a13 100644
--- a/README.md
+++ b/README.md
@@ -251,7 +251,8 @@ TinyObjLoader triangulate polygons(faces with 4 or more vertices).
 Built-in trinagulation code may not work well in some polygon shape.
 
 You can define `TINYOBJLOADER_USE_MAPBOX_EARCUT` for robust triangulation using `mapbox/earcut.hpp`.
-This requires C++11 compiler though.
+This requires C++11 compiler though. And you need to copy `mapbox/earcut.hpp` to your project.
+If you have your own `mapbox/earcut.hpp` file incuded in your project, you can define `TINYOBJLOADER_DONOT_INCLUDE_MAPBOX_EARCUT` so that `mapbox/earcut.hpp` is not included inside of `tiny_obj_loader.h`.
 
 #### Example code (Deprecated API)
 
diff --git a/azure-pipelines.yml b/azure-pipelines.yml
index 0e835ae..a71c43b 100644
--- a/azure-pipelines.yml
+++ b/azure-pipelines.yml
@@ -37,6 +37,8 @@ jobs:
           pip3 install cibuildwheel twine
           # Make the header files available to the build.
           cp *.h python
+          mkdir python/mapbox
+          cp mapbox/earcut.hpp python/mapbox/
           cd python
 
           # Source dist
@@ -73,6 +75,8 @@ jobs:
           pip3 install cibuildwheel
           # Make the header files available to the build.
           cp *.h python
+          mkdir python/mapbox
+          cp mapbox/earcut.hpp python/mapbox/earcut.hpp
           cd python
           cibuildwheel --output-dir wheelhouse .
       - task: CopyFiles@2
@@ -93,6 +97,8 @@ jobs:
           pip install cibuildwheel
           # Make the header files available to the build.
           cp *.h python
+          mkdir python/mapbox
+          cp mapbox/earcut.hpp python/mapbox/
           cd python
           cibuildwheel --output-dir wheelhouse .
       - task: CopyFiles@2
diff --git a/loader_example.cc b/loader_example.cc
index 69e5597..8143bb7 100644
--- a/loader_example.cc
+++ b/loader_example.cc
@@ -379,12 +379,12 @@ static bool TestStreamLoadObj() {
    public:
     MaterialStringStreamReader(const std::string& matSStream)
         : m_matSStream(matSStream) {}
-    virtual ~MaterialStringStreamReader() {}
+    virtual ~MaterialStringStreamReader() TINYOBJ_OVERRIDE {}
     virtual bool operator()(const std::string& matId,
                             std::vector<material_t>* materials,
                             std::map<std::string, int>* matMap,
                             std::string* warn,
-                            std::string* err) {
+                            std::string* err) TINYOBJ_OVERRIDE {
       (void)err;
       (void)matId;
       LoadMtl(matMap, materials, &m_matSStream, warn, err);
diff --git a/mapbox/LICENSE b/mapbox/LICENSE
new file mode 100644
index 0000000..8bafb57
--- /dev/null
+++ b/mapbox/LICENSE
@@ -0,0 +1,15 @@
+ISC License
+
+Copyright (c) 2015, Mapbox
+
+Permission to use, copy, modify, and/or distribute this software for any purpose
+with or without fee is hereby granted, provided that the above copyright notice
+and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+THIS SOFTWARE.
diff --git a/mapbox/earcut.hpp b/mapbox/earcut.hpp
new file mode 100644
index 0000000..01bd7e9
--- /dev/null
+++ b/mapbox/earcut.hpp
@@ -0,0 +1,820 @@
+#pragma once
+
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <memory>
+#include <vector>
+
+namespace mapbox {
+
+namespace util {
+
+template <std::size_t I, typename T> struct nth {
+    inline static typename std::tuple_element<I, T>::type
+    get(const T& t) { return std::get<I>(t); };
+};
+
+}
+
+namespace detail {
+
+template <typename N = uint32_t>
+class Earcut {
+public:
+    std::vector<N> indices;
+    std::size_t vertices = 0;
+
+    template <typename Polygon>
+    void operator()(const Polygon& points);
+
+private:
+    struct Node {
+        Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {}
+        Node(const Node&) = delete;
+        Node& operator=(const Node&) = delete;
+        Node(Node&&) = delete;
+        Node& operator=(Node&&) = delete;
+
+        const N i;
+        const double x;
+        const double y;
+
+        // previous and next vertice nodes in a polygon ring
+        Node* prev = nullptr;
+        Node* next = nullptr;
+
+        // z-order curve value
+        int32_t z = 0;
+
+        // previous and next nodes in z-order
+        Node* prevZ = nullptr;
+        Node* nextZ = nullptr;
+
+        // indicates whether this is a steiner point
+        bool steiner = false;
+    };
+
+    template <typename Ring> Node* linkedList(const Ring& points, const bool clockwise);
+    Node* filterPoints(Node* start, Node* end = nullptr);
+    void earcutLinked(Node* ear, int pass = 0);
+    bool isEar(Node* ear);
+    bool isEarHashed(Node* ear);
+    Node* cureLocalIntersections(Node* start);
+    void splitEarcut(Node* start);
+    template <typename Polygon> Node* eliminateHoles(const Polygon& points, Node* outerNode);
+    Node* eliminateHole(Node* hole, Node* outerNode);
+    Node* findHoleBridge(Node* hole, Node* outerNode);
+    bool sectorContainsSector(const Node* m, const Node* p);
+    void indexCurve(Node* start);
+    Node* sortLinked(Node* list);
+    int32_t zOrder(const double x_, const double y_);
+    Node* getLeftmost(Node* start);
+    bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const;
+    bool isValidDiagonal(Node* a, Node* b);
+    double area(const Node* p, const Node* q, const Node* r) const;
+    bool equals(const Node* p1, const Node* p2);
+    bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2);
+    bool onSegment(const Node* p, const Node* q, const Node* r);
+    int sign(double val);
+    bool intersectsPolygon(const Node* a, const Node* b);
+    bool locallyInside(const Node* a, const Node* b);
+    bool middleInside(const Node* a, const Node* b);
+    Node* splitPolygon(Node* a, Node* b);
+    template <typename Point> Node* insertNode(std::size_t i, const Point& p, Node* last);
+    void removeNode(Node* p);
+
+    bool hashing;
+    double minX, maxX;
+    double minY, maxY;
+    double inv_size = 0;
+
+    template <typename T, typename Alloc = std::allocator<T>>
+    class ObjectPool {
+    public:
+        ObjectPool() { }
+        ObjectPool(std::size_t blockSize_) {
+            reset(blockSize_);
+        }
+        ~ObjectPool() {
+            clear();
+        }
+        template <typename... Args>
+        T* construct(Args&&... args) {
+            if (currentIndex >= blockSize) {
+                currentBlock = alloc_traits::allocate(alloc, blockSize);
+                allocations.emplace_back(currentBlock);
+                currentIndex = 0;
+            }
+            T* object = &currentBlock[currentIndex++];
+            alloc_traits::construct(alloc, object, std::forward<Args>(args)...);
+            return object;
+        }
+        void reset(std::size_t newBlockSize) {
+            for (auto allocation : allocations) {
+                alloc_traits::deallocate(alloc, allocation, blockSize);
+            }
+            allocations.clear();
+            blockSize = std::max<std::size_t>(1, newBlockSize);
+            currentBlock = nullptr;
+            currentIndex = blockSize;
+        }
+        void clear() { reset(blockSize); }
+    private:
+        T* currentBlock = nullptr;
+        std::size_t currentIndex = 1;
+        std::size_t blockSize = 1;
+        std::vector<T*> allocations;
+        Alloc alloc;
+        typedef typename std::allocator_traits<Alloc> alloc_traits;
+    };
+    ObjectPool<Node> nodes;
+};
+
+template <typename N> template <typename Polygon>
+void Earcut<N>::operator()(const Polygon& points) {
+    // reset
+    indices.clear();
+    vertices = 0;
+
+    if (points.empty()) return;
+
+    double x;
+    double y;
+    int threshold = 80;
+    std::size_t len = 0;
+
+    for (size_t i = 0; threshold >= 0 && i < points.size(); i++) {
+        threshold -= static_cast<int>(points[i].size());
+        len += points[i].size();
+    }
+
+    //estimate size of nodes and indices
+    nodes.reset(len * 3 / 2);
+    indices.reserve(len + points[0].size());
+
+    Node* outerNode = linkedList(points[0], true);
+    if (!outerNode || outerNode->prev == outerNode->next) return;
+
+    if (points.size() > 1) outerNode = eliminateHoles(points, outerNode);
+
+    // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
+    hashing = threshold < 0;
+    if (hashing) {
+        Node* p = outerNode->next;
+        minX = maxX = outerNode->x;
+        minY = maxY = outerNode->y;
+        do {
+            x = p->x;
+            y = p->y;
+            minX = std::min<double>(minX, x);
+            minY = std::min<double>(minY, y);
+            maxX = std::max<double>(maxX, x);
+            maxY = std::max<double>(maxY, y);
+            p = p->next;
+        } while (p != outerNode);
+
+        // minX, minY and size are later used to transform coords into integers for z-order calculation
+        inv_size = std::max<double>(maxX - minX, maxY - minY);
+        inv_size = inv_size != .0 ? (1. / inv_size) : .0;
+    }
+
+    earcutLinked(outerNode);
+
+    nodes.clear();
+}
+
+// create a circular doubly linked list from polygon points in the specified winding order
+template <typename N> template <typename Ring>
+typename Earcut<N>::Node*
+Earcut<N>::linkedList(const Ring& points, const bool clockwise) {
+    using Point = typename Ring::value_type;
+    double sum = 0;
+    const std::size_t len = points.size();
+    std::size_t i, j;
+    Node* last = nullptr;
+
+    // calculate original winding order of a polygon ring
+    for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) {
+        const auto& p1 = points[i];
+        const auto& p2 = points[j];
+        const double p20 = util::nth<0, Point>::get(p2);
+        const double p10 = util::nth<0, Point>::get(p1);
+        const double p11 = util::nth<1, Point>::get(p1);
+        const double p21 = util::nth<1, Point>::get(p2);
+        sum += (p20 - p10) * (p11 + p21);
+    }
+
+    // link points into circular doubly-linked list in the specified winding order
+    if (clockwise == (sum > 0)) {
+        for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last);
+    } else {
+        for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last);
+    }
+
+    if (last && equals(last, last->next)) {
+        removeNode(last);
+        last = last->next;
+    }
+
+    vertices += len;
+
+    return last;
+}
+
+// eliminate colinear or duplicate points
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::filterPoints(Node* start, Node* end) {
+    if (!end) end = start;
+
+    Node* p = start;
+    bool again;
+    do {
+        again = false;
+
+        if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) {
+            removeNode(p);
+            p = end = p->prev;
+
+            if (p == p->next) break;
+            again = true;
+
+        } else {
+            p = p->next;
+        }
+    } while (again || p != end);
+
+    return end;
+}
+
+// main ear slicing loop which triangulates a polygon (given as a linked list)
+template <typename N>
+void Earcut<N>::earcutLinked(Node* ear, int pass) {
+    if (!ear) return;
+
+    // interlink polygon nodes in z-order
+    if (!pass && hashing) indexCurve(ear);
+
+    Node* stop = ear;
+    Node* prev;
+    Node* next;
+
+    int iterations = 0;
+
+    // iterate through ears, slicing them one by one
+    while (ear->prev != ear->next) {
+        iterations++;
+        prev = ear->prev;
+        next = ear->next;
+
+        if (hashing ? isEarHashed(ear) : isEar(ear)) {
+            // cut off the triangle
+            indices.emplace_back(prev->i);
+            indices.emplace_back(ear->i);
+            indices.emplace_back(next->i);
+
+            removeNode(ear);
+
+            // skipping the next vertice leads to less sliver triangles
+            ear = next->next;
+            stop = next->next;
+
+            continue;
+        }
+
+        ear = next;
+
+        // if we looped through the whole remaining polygon and can't find any more ears
+        if (ear == stop) {
+            // try filtering points and slicing again
+            if (!pass) earcutLinked(filterPoints(ear), 1);
+
+            // if this didn't work, try curing all small self-intersections locally
+            else if (pass == 1) {
+                ear = cureLocalIntersections(filterPoints(ear));
+                earcutLinked(ear, 2);
+
+            // as a last resort, try splitting the remaining polygon into two
+            } else if (pass == 2) splitEarcut(ear);
+
+            break;
+        }
+    }
+}
+
+// check whether a polygon node forms a valid ear with adjacent nodes
+template <typename N>
+bool Earcut<N>::isEar(Node* ear) {
+    const Node* a = ear->prev;
+    const Node* b = ear;
+    const Node* c = ear->next;
+
+    if (area(a, b, c) >= 0) return false; // reflex, can't be an ear
+
+    // now make sure we don't have other points inside the potential ear
+    Node* p = ear->next->next;
+
+    while (p != ear->prev) {
+        if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
+            area(p->prev, p, p->next) >= 0) return false;
+        p = p->next;
+    }
+
+    return true;
+}
+
+template <typename N>
+bool Earcut<N>::isEarHashed(Node* ear) {
+    const Node* a = ear->prev;
+    const Node* b = ear;
+    const Node* c = ear->next;
+
+    if (area(a, b, c) >= 0) return false; // reflex, can't be an ear
+
+    // triangle bbox; min & max are calculated like this for speed
+    const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x));
+    const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y));
+    const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x));
+    const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y));
+
+    // z-order range for the current triangle bbox;
+    const int32_t minZ = zOrder(minTX, minTY);
+    const int32_t maxZ = zOrder(maxTX, maxTY);
+
+    // first look for points inside the triangle in increasing z-order
+    Node* p = ear->nextZ;
+
+    while (p && p->z <= maxZ) {
+        if (p != ear->prev && p != ear->next &&
+            pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
+            area(p->prev, p, p->next) >= 0) return false;
+        p = p->nextZ;
+    }
+
+    // then look for points in decreasing z-order
+    p = ear->prevZ;
+
+    while (p && p->z >= minZ) {
+        if (p != ear->prev && p != ear->next &&
+            pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
+            area(p->prev, p, p->next) >= 0) return false;
+        p = p->prevZ;
+    }
+
+    return true;
+}
+
+// go through all polygon nodes and cure small local self-intersections
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::cureLocalIntersections(Node* start) {
+    Node* p = start;
+    do {
+        Node* a = p->prev;
+        Node* b = p->next->next;
+
+        // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
+        if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) {
+            indices.emplace_back(a->i);
+            indices.emplace_back(p->i);
+            indices.emplace_back(b->i);
+
+            // remove two nodes involved
+            removeNode(p);
+            removeNode(p->next);
+
+            p = start = b;
+        }
+        p = p->next;
+    } while (p != start);
+
+    return filterPoints(p);
+}
+
+// try splitting polygon into two and triangulate them independently
+template <typename N>
+void Earcut<N>::splitEarcut(Node* start) {
+    // look for a valid diagonal that divides the polygon into two
+    Node* a = start;
+    do {
+        Node* b = a->next->next;
+        while (b != a->prev) {
+            if (a->i != b->i && isValidDiagonal(a, b)) {
+                // split the polygon in two by the diagonal
+                Node* c = splitPolygon(a, b);
+
+                // filter colinear points around the cuts
+                a = filterPoints(a, a->next);
+                c = filterPoints(c, c->next);
+
+                // run earcut on each half
+                earcutLinked(a);
+                earcutLinked(c);
+                return;
+            }
+            b = b->next;
+        }
+        a = a->next;
+    } while (a != start);
+}
+
+// link every hole into the outer loop, producing a single-ring polygon without holes
+template <typename N> template <typename Polygon>
+typename Earcut<N>::Node*
+Earcut<N>::eliminateHoles(const Polygon& points, Node* outerNode) {
+    const size_t len = points.size();
+
+    std::vector<Node*> queue;
+    for (size_t i = 1; i < len; i++) {
+        Node* list = linkedList(points[i], false);
+        if (list) {
+            if (list == list->next) list->steiner = true;
+            queue.push_back(getLeftmost(list));
+        }
+    }
+    std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) {
+        return a->x < b->x;
+    });
+
+    // process holes from left to right
+    for (size_t i = 0; i < queue.size(); i++) {
+        outerNode = eliminateHole(queue[i], outerNode);
+        outerNode = filterPoints(outerNode, outerNode->next);
+    }
+
+    return outerNode;
+}
+
+// find a bridge between vertices that connects hole with an outer ring and and link it
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::eliminateHole(Node* hole, Node* outerNode) {
+    Node* bridge = findHoleBridge(hole, outerNode);
+    if (!bridge) {
+        return outerNode;
+    }
+
+    Node* bridgeReverse = splitPolygon(bridge, hole);
+
+    // filter collinear points around the cuts
+    Node* filteredBridge = filterPoints(bridge, bridge->next);
+    filterPoints(bridgeReverse, bridgeReverse->next);
+
+    // Check if input node was removed by the filtering
+    return outerNode == bridge ? filteredBridge : outerNode;
+}
+
+// David Eberly's algorithm for finding a bridge between hole and outer polygon
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::findHoleBridge(Node* hole, Node* outerNode) {
+    Node* p = outerNode;
+    double hx = hole->x;
+    double hy = hole->y;
+    double qx = -std::numeric_limits<double>::infinity();
+    Node* m = nullptr;
+
+    // find a segment intersected by a ray from the hole's leftmost Vertex to the left;
+    // segment's endpoint with lesser x will be potential connection Vertex
+    do {
+        if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) {
+          double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y);
+          if (x <= hx && x > qx) {
+            qx = x;
+            if (x == hx) {
+                if (hy == p->y) return p;
+                if (hy == p->next->y) return p->next;
+            }
+            m = p->x < p->next->x ? p : p->next;
+          }
+        }
+        p = p->next;
+    } while (p != outerNode);
+
+    if (!m) return 0;
+
+    if (hx == qx) return m; // hole touches outer segment; pick leftmost endpoint
+
+    // look for points inside the triangle of hole Vertex, segment intersection and endpoint;
+    // if there are no points found, we have a valid connection;
+    // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex
+
+    const Node* stop = m;
+    double tanMin = std::numeric_limits<double>::infinity();
+    double tanCur = 0;
+
+    p = m;
+    double mx = m->x;
+    double my = m->y;
+
+    do {
+        if (hx >= p->x && p->x >= mx && hx != p->x &&
+            pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) {
+
+            tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential
+
+            if (locallyInside(p, hole) &&
+                (tanCur < tanMin || (tanCur == tanMin && (p->x > m->x || sectorContainsSector(m, p))))) {
+                m = p;
+                tanMin = tanCur;
+            }
+        }
+
+        p = p->next;
+    } while (p != stop);
+
+    return m;
+}
+
+// whether sector in vertex m contains sector in vertex p in the same coordinates
+template <typename N>
+bool Earcut<N>::sectorContainsSector(const Node* m, const Node* p) {
+    return area(m->prev, m, p->prev) < 0 && area(p->next, m, m->next) < 0;
+}
+
+// interlink polygon nodes in z-order
+template <typename N>
+void Earcut<N>::indexCurve(Node* start) {
+    assert(start);
+    Node* p = start;
+
+    do {
+        p->z = p->z ? p->z : zOrder(p->x, p->y);
+        p->prevZ = p->prev;
+        p->nextZ = p->next;
+        p = p->next;
+    } while (p != start);
+
+    p->prevZ->nextZ = nullptr;
+    p->prevZ = nullptr;
+
+    sortLinked(p);
+}
+
+// Simon Tatham's linked list merge sort algorithm
+// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::sortLinked(Node* list) {
+    assert(list);
+    Node* p;
+    Node* q;
+    Node* e;
+    Node* tail;
+    int i, numMerges, pSize, qSize;
+    int inSize = 1;
+
+    for (;;) {
+        p = list;
+        list = nullptr;
+        tail = nullptr;
+        numMerges = 0;
+
+        while (p) {
+            numMerges++;
+            q = p;
+            pSize = 0;
+            for (i = 0; i < inSize; i++) {
+                pSize++;
+                q = q->nextZ;
+                if (!q) break;
+            }
+
+            qSize = inSize;
+
+            while (pSize > 0 || (qSize > 0 && q)) {
+
+                if (pSize == 0) {
+                    e = q;
+                    q = q->nextZ;
+                    qSize--;
+                } else if (qSize == 0 || !q) {
+                    e = p;
+                    p = p->nextZ;
+                    pSize--;
+                } else if (p->z <= q->z) {
+                    e = p;
+                    p = p->nextZ;
+                    pSize--;
+                } else {
+                    e = q;
+                    q = q->nextZ;
+                    qSize--;
+                }
+
+                if (tail) tail->nextZ = e;
+                else list = e;
+
+                e->prevZ = tail;
+                tail = e;
+            }
+
+            p = q;
+        }
+
+        tail->nextZ = nullptr;
+
+        if (numMerges <= 1) return list;
+
+        inSize *= 2;
+    }
+}
+
+// z-order of a Vertex given coords and size of the data bounding box
+template <typename N>
+int32_t Earcut<N>::zOrder(const double x_, const double y_) {
+    // coords are transformed into non-negative 15-bit integer range
+    int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size);
+    int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size);
+
+    x = (x | (x << 8)) & 0x00FF00FF;
+    x = (x | (x << 4)) & 0x0F0F0F0F;
+    x = (x | (x << 2)) & 0x33333333;
+    x = (x | (x << 1)) & 0x55555555;
+
+    y = (y | (y << 8)) & 0x00FF00FF;
+    y = (y | (y << 4)) & 0x0F0F0F0F;
+    y = (y | (y << 2)) & 0x33333333;
+    y = (y | (y << 1)) & 0x55555555;
+
+    return x | (y << 1);
+}
+
+// find the leftmost node of a polygon ring
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::getLeftmost(Node* start) {
+    Node* p = start;
+    Node* leftmost = start;
+    do {
+        if (p->x < leftmost->x || (p->x == leftmost->x && p->y < leftmost->y))
+            leftmost = p;
+        p = p->next;
+    } while (p != start);
+
+    return leftmost;
+}
+
+// check if a point lies within a convex triangle
+template <typename N>
+bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const {
+    return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
+           (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
+           (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
+}
+
+// check if a diagonal between two polygon nodes is valid (lies in polygon interior)
+template <typename N>
+bool Earcut<N>::isValidDiagonal(Node* a, Node* b) {
+    return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) && // dones't intersect other edges
+           ((locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) && // locally visible
+            (area(a->prev, a, b->prev) != 0.0 || area(a, b->prev, b) != 0.0)) || // does not create opposite-facing sectors
+            (equals(a, b) && area(a->prev, a, a->next) > 0 && area(b->prev, b, b->next) > 0)); // special zero-length case
+}
+
+// signed area of a triangle
+template <typename N>
+double Earcut<N>::area(const Node* p, const Node* q, const Node* r) const {
+    return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y);
+}
+
+// check if two points are equal
+template <typename N>
+bool Earcut<N>::equals(const Node* p1, const Node* p2) {
+    return p1->x == p2->x && p1->y == p2->y;
+}
+
+// check if two segments intersect
+template <typename N>
+bool Earcut<N>::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) {
+    int o1 = sign(area(p1, q1, p2));
+    int o2 = sign(area(p1, q1, q2));
+    int o3 = sign(area(p2, q2, p1));
+    int o4 = sign(area(p2, q2, q1));
+
+    if (o1 != o2 && o3 != o4) return true; // general case
+
+    if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and p2 are collinear and p2 lies on p1q1
+    if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p1, q1 and q2 are collinear and q2 lies on p1q1
+    if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and p1 are collinear and p1 lies on p2q2
+    if (o4 == 0 && onSegment(p2, q1, q2)) return true; // p2, q2 and q1 are collinear and q1 lies on p2q2
+
+    return false;
+}
+
+// for collinear points p, q, r, check if point q lies on segment pr
+template <typename N>
+bool Earcut<N>::onSegment(const Node* p, const Node* q, const Node* r) {
+    return q->x <= std::max<double>(p->x, r->x) &&
+        q->x >= std::min<double>(p->x, r->x) &&
+        q->y <= std::max<double>(p->y, r->y) &&
+        q->y >= std::min<double>(p->y, r->y);
+}
+
+template <typename N>
+int Earcut<N>::sign(double val) {
+    return (0.0 < val) - (val < 0.0);
+}
+
+// check if a polygon diagonal intersects any polygon segments
+template <typename N>
+bool Earcut<N>::intersectsPolygon(const Node* a, const Node* b) {
+    const Node* p = a;
+    do {
+        if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i &&
+                intersects(p, p->next, a, b)) return true;
+        p = p->next;
+    } while (p != a);
+
+    return false;
+}
+
+// check if a polygon diagonal is locally inside the polygon
+template <typename N>
+bool Earcut<N>::locallyInside(const Node* a, const Node* b) {
+    return area(a->prev, a, a->next) < 0 ?
+        area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 :
+        area(a, b, a->prev) < 0 || area(a, a->next, b) < 0;
+}
+
+// check if the middle Vertex of a polygon diagonal is inside the polygon
+template <typename N>
+bool Earcut<N>::middleInside(const Node* a, const Node* b) {
+    const Node* p = a;
+    bool inside = false;
+    double px = (a->x + b->x) / 2;
+    double py = (a->y + b->y) / 2;
+    do {
+        if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y &&
+                (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x))
+            inside = !inside;
+        p = p->next;
+    } while (p != a);
+
+    return inside;
+}
+
+// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits
+// polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a
+// single ring
+template <typename N>
+typename Earcut<N>::Node*
+Earcut<N>::splitPolygon(Node* a, Node* b) {
+    Node* a2 = nodes.construct(a->i, a->x, a->y);
+    Node* b2 = nodes.construct(b->i, b->x, b->y);
+    Node* an = a->next;
+    Node* bp = b->prev;
+
+    a->next = b;
+    b->prev = a;
+
+    a2->next = an;
+    an->prev = a2;
+
+    b2->next = a2;
+    a2->prev = b2;
+
+    bp->next = b2;
+    b2->prev = bp;
+
+    return b2;
+}
+
+// create a node and util::optionally link it with previous one (in a circular doubly linked list)
+template <typename N> template <typename Point>
+typename Earcut<N>::Node*
+Earcut<N>::insertNode(std::size_t i, const Point& pt, Node* last) {
+    Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt));
+
+    if (!last) {
+        p->prev = p;
+        p->next = p;
+
+    } else {
+        assert(last);
+        p->next = last->next;
+        p->prev = last;
+        last->next->prev = p;
+        last->next = p;
+    }
+    return p;
+}
+
+template <typename N>
+void Earcut<N>::removeNode(Node* p) {
+    p->next->prev = p->prev;
+    p->prev->next = p->next;
+
+    if (p->prevZ) p->prevZ->nextZ = p->nextZ;
+    if (p->nextZ) p->nextZ->prevZ = p->prevZ;
+}
+}
+
+template <typename N = uint32_t, typename Polygon>
+std::vector<N> earcut(const Polygon& poly) {
+    mapbox::detail::Earcut<N> earcut;
+    earcut(poly);
+    return std::move(earcut.indices);
+}
+}
diff --git a/python/README.md b/python/README.md
index b6e2872..913668f 100644
--- a/python/README.md
+++ b/python/README.md
@@ -83,7 +83,7 @@ $ python setup.py build
 
 ## License
 
-MIT license.
+MIT(tinyobjloader) and ISC(mapbox earcut) license.
 
 ## TODO
  * [ ] Writer saver
diff --git a/python/setup.py b/python/setup.py
index 8a9b69c..df53136 100644
--- a/python/setup.py
+++ b/python/setup.py
@@ -1,6 +1,8 @@
 import setuptools
 import platform
 
+from distutils.command.build_ext import build_ext
+
 with open("README.md", "r") as fh:
     long_description = fh.read()
 
@@ -45,8 +47,26 @@ class get_pybind_include(object):
             return interpreter_include_path
 
 
-ext_compile_args = ["-std=c++11"]
-ext_link_args = []
+# unix = default compiler name?
+copt = {"unix": ["-std=c++11"], "gcc": ["-std=c++11"], "clang": ["std=c++11"]}
+# TODO: set C++ version for msvc? {'msvc': ["/std:c++14"] }
+
+# ext_compile_args = ["-std=c++11"]
+# ext_link_args = []
+
+# https://stackoverflow.com/questions/724664/python-distutils-how-to-get-a-compiler-that-is-going-to-be-used
+class build_ext_subclass(build_ext):
+    def build_extensions(self):
+        c = self.compiler.compiler_type
+        if c in copt:
+            for e in self.extensions:
+                e.extra_compile_args = copt[c]
+
+        # if lopt.has_key(c):
+        #    for e in self.extensions:
+        #        e.extra_link_args = lopt[ c ]
+        build_ext.build_extensions(self)
+
 
 # Developer option
 #
@@ -61,8 +81,8 @@ ext_link_args = []
 # `tiny_obj_loader.cc` contains implementation of tiny_obj_loader.
 m = setuptools.Extension(
     "tinyobjloader",
-    extra_compile_args=ext_compile_args,
-    extra_link_args=ext_link_args,
+    # extra_compile_args=ext_compile_args,
+    # extra_link_args=ext_link_args,
     sources=["bindings.cc", "tiny_obj_loader.cc"],
     include_dirs=[
         # Support `build_ext` finding tinyobjloader (without first running
@@ -100,10 +120,11 @@ setuptools.setup(
         "Topic :: Artistic Software",
         "Topic :: Multimedia :: Graphics :: 3D Modeling",
         "Topic :: Scientific/Engineering :: Visualization",
-        "License :: OSI Approved :: MIT License",
+        "License :: OSI Approved :: MIT License(ISC License for mapbox earcut.hpp)",
         "Operating System :: OS Independent",
         "Programming Language :: Python :: 3",
     ],
     packages=setuptools.find_packages(),
     ext_modules=[m],
+    cmdclass={"build_ext": build_ext_subclass},
 )
diff --git a/tiny_obj_loader.h b/tiny_obj_loader.h
index 1a15e1d..77f86b2 100644
--- a/tiny_obj_loader.h
+++ b/tiny_obj_loader.h
@@ -663,866 +663,23 @@ bool ParseTextureNameAndOption(std::string *texname, texture_option_t *texopt,
 
 #ifdef TINYOBJLOADER_USE_MAPBOX_EARCUT
 
-#include <algorithm>
-#include <array>
-
-/*
-ISC License
-
-Copyright (c) 2015, Mapbox
-
-Permission to use, copy, modify, and/or distribute this software for any purpose
-with or without fee is hereby granted, provided that the above copyright notice
-and this permission notice appear in all copies.
-
-THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
-REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
-FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
-INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
-OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
-TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
-THIS SOFTWARE.
-*/
-
-namespace mapbox {
-
-namespace util {
-
-template <std::size_t I, typename T>
-struct nth {
-  inline static typename std::tuple_element<I, T>::type get(const T &t) {
-    return std::get<I>(t);
-  };
-};
-
-}  // namespace util
-
-namespace detail {
-
-template <typename N = uint32_t>
-class Earcut {
- public:
-  std::vector<N> indices;
-  std::size_t vertices = 0;
-
-  template <typename Polygon>
-  void operator()(const Polygon &points);
-
- private:
-  struct Node {
-    Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {}
-    Node(const Node &) = delete;
-    Node &operator=(const Node &) = delete;
-    Node(Node &&) = delete;
-    Node &operator=(Node &&) = delete;
-
-    const N i;
-    const double x;
-    const double y;
-
-    // previous and next vertice nodes in a polygon ring
-    Node *prev = nullptr;
-    Node *next = nullptr;
-
-    // z-order curve value
-    int32_t z = 0;
-
-    // previous and next nodes in z-order
-    Node *prevZ = nullptr;
-    Node *nextZ = nullptr;
-
-    // indicates whether this is a steiner point
-    bool steiner = false;
-  };
-
-  template <typename Ring>
-  Node *linkedList(const Ring &points, const bool clockwise);
-  Node *filterPoints(Node *start, Node *end = nullptr);
-  void earcutLinked(Node *ear, int pass = 0);
-  bool isEar(Node *ear);
-  bool isEarHashed(Node *ear);
-  Node *cureLocalIntersections(Node *start);
-  void splitEarcut(Node *start);
-  template <typename Polygon>
-  Node *eliminateHoles(const Polygon &points, Node *outerNode);
-  void eliminateHole(Node *hole, Node *outerNode);
-  Node *findHoleBridge(Node *hole, Node *outerNode);
-  bool sectorContainsSector(const Node *m, const Node *p);
-  void indexCurve(Node *start);
-  Node *sortLinked(Node *list);
-  int32_t zOrder(const double x_, const double y_);
-  Node *getLeftmost(Node *start);
-  bool pointInTriangle(double ax, double ay, double bx, double by, double cx,
-                       double cy, double px, double py) const;
-  bool isValidDiagonal(Node *a, Node *b);
-  double area(const Node *p, const Node *q, const Node *r) const;
-  bool equals(const Node *p1, const Node *p2);
-  bool intersects(const Node *p1, const Node *q1, const Node *p2,
-                  const Node *q2);
-  bool onSegment(const Node *p, const Node *q, const Node *r);
-  int sign(double val);
-  bool intersectsPolygon(const Node *a, const Node *b);
-  bool locallyInside(const Node *a, const Node *b);
-  bool middleInside(const Node *a, const Node *b);
-  Node *splitPolygon(Node *a, Node *b);
-  template <typename Point>
-  Node *insertNode(std::size_t i, const Point &p, Node *last);
-  void removeNode(Node *p);
-
-  bool hashing;
-  double minX, maxX;
-  double minY, maxY;
-  double inv_size = 0;
-
-  template <typename T, typename Alloc = std::allocator<T> >
-  class ObjectPool {
-   public:
-    ObjectPool() {}
-    ObjectPool(std::size_t blockSize_) { reset(blockSize_); }
-    ~ObjectPool() { clear(); }
-    template <typename... Args>
-    T *construct(Args &&... args) {
-      if (currentIndex >= blockSize) {
-        currentBlock = alloc_traits::allocate(alloc, blockSize);
-        allocations.emplace_back(currentBlock);
-        currentIndex = 0;
-      }
-      T *object = &currentBlock[currentIndex++];
-      alloc_traits::construct(alloc, object, std::forward<Args>(args)...);
-      return object;
-    }
-    void reset(std::size_t newBlockSize) {
-      for (auto allocation : allocations) {
-        alloc_traits::deallocate(alloc, allocation, blockSize);
-      }
-      allocations.clear();
-      blockSize = std::max<std::size_t>(1, newBlockSize);
-      currentBlock = nullptr;
-      currentIndex = blockSize;
-    }
-    void clear() { reset(blockSize); }
-
-   private:
-    T *currentBlock = nullptr;
-    std::size_t currentIndex = 1;
-    std::size_t blockSize = 1;
-    std::vector<T *> allocations;
-    Alloc alloc;
-    typedef typename std::allocator_traits<Alloc> alloc_traits;
-  };
-  ObjectPool<Node> nodes;
-};
-
-template <typename N>
-template <typename Polygon>
-void Earcut<N>::operator()(const Polygon &points) {
-  // reset
-  indices.clear();
-  vertices = 0;
-
-  if (points.empty()) return;
-
-  double x;
-  double y;
-  int threshold = 80;
-  std::size_t len = 0;
-
-  for (size_t i = 0; threshold >= 0 && i < points.size(); i++) {
-    threshold -= static_cast<int>(points[i].size());
-    len += points[i].size();
-  }
-
-  // estimate size of nodes and indices
-  nodes.reset(len * 3 / 2);
-  indices.reserve(len + points[0].size());
-
-  Node *outerNode = linkedList(points[0], true);
-  if (!outerNode || outerNode->prev == outerNode->next) return;
-
-  if (points.size() > 1) outerNode = eliminateHoles(points, outerNode);
-
-  // if the shape is not too simple, we'll use z-order curve hash later;
-  // calculate polygon bbox
-  hashing = threshold < 0;
-  if (hashing) {
-    Node *p = outerNode->next;
-    minX = maxX = outerNode->x;
-    minY = maxY = outerNode->y;
-    do {
-      x = p->x;
-      y = p->y;
-      minX = std::min<double>(minX, x);
-      minY = std::min<double>(minY, y);
-      maxX = std::max<double>(maxX, x);
-      maxY = std::max<double>(maxY, y);
-      p = p->next;
-    } while (p != outerNode);
-
-    // minX, minY and size are later used to transform coords into integers for
-    // z-order calculation
-    inv_size = std::max<double>(maxX - minX, maxY - minY);
-    inv_size = inv_size != .0 ? (1. / inv_size) : .0;
-  }
-
-  earcutLinked(outerNode);
-
-  nodes.clear();
-}
-
-// create a circular doubly linked list from polygon points in the specified
-// winding order
-template <typename N>
-template <typename Ring>
-typename Earcut<N>::Node *Earcut<N>::linkedList(const Ring &points,
-                                                const bool clockwise) {
-  using Point = typename Ring::value_type;
-  double sum = 0;
-  const std::size_t len = points.size();
-  std::size_t i, j;
-  Node *last = nullptr;
-
-  // calculate original winding order of a polygon ring
-  for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) {
-    const auto &p1 = points[i];
-    const auto &p2 = points[j];
-    const double p20 = util::nth<0, Point>::get(p2);
-    const double p10 = util::nth<0, Point>::get(p1);
-    const double p11 = util::nth<1, Point>::get(p1);
-    const double p21 = util::nth<1, Point>::get(p2);
-    sum += (p20 - p10) * (p11 + p21);
-  }
-
-  // link points into circular doubly-linked list in the specified winding order
-  if (clockwise == (sum > 0)) {
-    for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last);
-  } else {
-    for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last);
-  }
-
-  if (last && equals(last, last->next)) {
-    removeNode(last);
-    last = last->next;
-  }
-
-  vertices += len;
-
-  return last;
-}
-
-// eliminate colinear or duplicate points
-template <typename N>
-typename Earcut<N>::Node *Earcut<N>::filterPoints(Node *start, Node *end) {
-  if (!end) end = start;
-
-  Node *p = start;
-  bool again;
-  do {
-    again = false;
-
-    if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) {
-      removeNode(p);
-      p = end = p->prev;
-
-      if (p == p->next) break;
-      again = true;
-
-    } else {
-      p = p->next;
-    }
-  } while (again || p != end);
-
-  return end;
-}
-
-// main ear slicing loop which triangulates a polygon (given as a linked list)
-template <typename N>
-void Earcut<N>::earcutLinked(Node *ear, int pass) {
-  if (!ear) return;
-
-  // interlink polygon nodes in z-order
-  if (!pass && hashing) indexCurve(ear);
-
-  Node *stop = ear;
-  Node *prev;
-  Node *next;
-
-  int iterations = 0;
-
-  // iterate through ears, slicing them one by one
-  while (ear->prev != ear->next) {
-    iterations++;
-    prev = ear->prev;
-    next = ear->next;
-
-    if (hashing ? isEarHashed(ear) : isEar(ear)) {
-      // cut off the triangle
-      indices.emplace_back(prev->i);
-      indices.emplace_back(ear->i);
-      indices.emplace_back(next->i);
-
-      removeNode(ear);
-
-      // skipping the next vertice leads to less sliver triangles
-      ear = next->next;
-      stop = next->next;
-
-      continue;
-    }
-
-    ear = next;
-
-    // if we looped through the whole remaining polygon and can't find any more
-    // ears
-    if (ear == stop) {
-      // try filtering points and slicing again
-      if (!pass) earcutLinked(filterPoints(ear), 1);
-
-      // if this didn't work, try curing all small self-intersections locally
-      else if (pass == 1) {
-        ear = cureLocalIntersections(filterPoints(ear));
-        earcutLinked(ear, 2);
-
-        // as a last resort, try splitting the remaining polygon into two
-      } else if (pass == 2)
-        splitEarcut(ear);
-
-      break;
-    }
-  }
-}
-
-// check whether a polygon node forms a valid ear with adjacent nodes
-template <typename N>
-bool Earcut<N>::isEar(Node *ear) {
-  const Node *a = ear->prev;
-  const Node *b = ear;
-  const Node *c = ear->next;
-
-  if (area(a, b, c) >= 0) return false;  // reflex, can't be an ear
-
-  // now make sure we don't have other points inside the potential ear
-  Node *p = ear->next->next;
-
-  while (p != ear->prev) {
-    if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
-        area(p->prev, p, p->next) >= 0)
-      return false;
-    p = p->next;
-  }
-
-  return true;
-}
-
-template <typename N>
-bool Earcut<N>::isEarHashed(Node *ear) {
-  const Node *a = ear->prev;
-  const Node *b = ear;
-  const Node *c = ear->next;
-
-  if (area(a, b, c) >= 0) return false;  // reflex, can't be an ear
-
-  // triangle bbox; min & max are calculated like this for speed
-  const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x));
-  const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y));
-  const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x));
-  const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y));
-
-  // z-order range for the current triangle bbox;
-  const int32_t minZ = zOrder(minTX, minTY);
-  const int32_t maxZ = zOrder(maxTX, maxTY);
-
-  // first look for points inside the triangle in increasing z-order
-  Node *p = ear->nextZ;
-
-  while (p && p->z <= maxZ) {
-    if (p != ear->prev && p != ear->next &&
-        pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
-        area(p->prev, p, p->next) >= 0)
-      return false;
-    p = p->nextZ;
-  }
-
-  // then look for points in decreasing z-order
-  p = ear->prevZ;
-
-  while (p && p->z >= minZ) {
-    if (p != ear->prev && p != ear->next &&
-        pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
-        area(p->prev, p, p->next) >= 0)
-      return false;
-    p = p->prevZ;
-  }
-
-  return true;
-}
-
-// go through all polygon nodes and cure small local self-intersections
-template <typename N>
-typename Earcut<N>::Node *Earcut<N>::cureLocalIntersections(Node *start) {
-  Node *p = start;
-  do {
-    Node *a = p->prev;
-    Node *b = p->next->next;
-
-    // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
-    if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) &&
-        locallyInside(b, a)) {
-      indices.emplace_back(a->i);
-      indices.emplace_back(p->i);
-      indices.emplace_back(b->i);
-
-      // remove two nodes involved
-      removeNode(p);
-      removeNode(p->next);
-
-      p = start = b;
-    }
-    p = p->next;
-  } while (p != start);
-
-  return filterPoints(p);
-}
-
-// try splitting polygon into two and triangulate them independently
-template <typename N>
-void Earcut<N>::splitEarcut(Node *start) {
-  // look for a valid diagonal that divides the polygon into two
-  Node *a = start;
-  do {
-    Node *b = a->next->next;
-    while (b != a->prev) {
-      if (a->i != b->i && isValidDiagonal(a, b)) {
-        // split the polygon in two by the diagonal
-        Node *c = splitPolygon(a, b);
-
-        // filter colinear points around the cuts
-        a = filterPoints(a, a->next);
-        c = filterPoints(c, c->next);
-
-        // run earcut on each half
-        earcutLinked(a);
-        earcutLinked(c);
-        return;
-      }
-      b = b->next;
-    }
-    a = a->next;
-  } while (a != start);
-}
-
-// link every hole into the outer loop, producing a single-ring polygon without
-// holes
-template <typename N>
-template <typename Polygon>
-typename Earcut<N>::Node *Earcut<N>::eliminateHoles(const Polygon &points,
-                                                    Node *outerNode) {
-  const size_t len = points.size();
-
-  std::vector<Node *> queue;
-  for (size_t i = 1; i < len; i++) {
-    Node *list = linkedList(points[i], false);
-    if (list) {
-      if (list == list->next) list->steiner = true;
-      queue.push_back(getLeftmost(list));
-    }
-  }
-  std::sort(queue.begin(), queue.end(),
-            [](const Node *a, const Node *b) { return a->x < b->x; });
-
-  // process holes from left to right
-  for (size_t i = 0; i < queue.size(); i++) {
-    eliminateHole(queue[i], outerNode);
-    outerNode = filterPoints(outerNode, outerNode->next);
-  }
-
-  return outerNode;
-}
-
-// find a bridge between vertices that connects hole with an outer ring and and
-// link it
-template <typename N>
-void Earcut<N>::eliminateHole(Node *hole, Node *outerNode) {
-  outerNode = findHoleBridge(hole, outerNode);
-  if (outerNode) {
-    Node *b = splitPolygon(outerNode, hole);
-
-    // filter out colinear points around cuts
-    filterPoints(outerNode, outerNode->next);
-    filterPoints(b, b->next);
-  }
-}
-
-// David Eberly's algorithm for finding a bridge between hole and outer polygon
-template <typename N>
-typename Earcut<N>::Node *Earcut<N>::findHoleBridge(Node *hole,
-                                                    Node *outerNode) {
-  Node *p = outerNode;
-  double hx = hole->x;
-  double hy = hole->y;
-  double qx = -std::numeric_limits<double>::infinity();
-  Node *m = nullptr;
-
-  // find a segment intersected by a ray from the hole's leftmost Vertex to the
-  // left; segment's endpoint with lesser x will be potential connection Vertex
-  do {
-    if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) {
-      double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y);
-      if (x <= hx && x > qx) {
-        qx = x;
-        if (x == hx) {
-          if (hy == p->y) return p;
-          if (hy == p->next->y) return p->next;
-        }
-        m = p->x < p->next->x ? p : p->next;
-      }
-    }
-    p = p->next;
-  } while (p != outerNode);
-
-  if (!m) return 0;
-
-  if (hx == qx) return m;  // hole touches outer segment; pick leftmost endpoint
-
-  // look for points inside the triangle of hole Vertex, segment intersection
-  // and endpoint; if there are no points found, we have a valid connection;
-  // otherwise choose the Vertex of the minimum angle with the ray as connection
-  // Vertex
-
-  const Node *stop = m;
-  double tanMin = std::numeric_limits<double>::infinity();
-  double tanCur = 0;
-
-  p = m;
-  double mx = m->x;
-  double my = m->y;
-
-  do {
-    if (hx >= p->x && p->x >= mx && hx != p->x &&
-        pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy,
-                        p->x, p->y)) {
-      tanCur = std::abs(hy - p->y) / (hx - p->x);  // tangential
-
-      if (locallyInside(p, hole) &&
-          (tanCur < tanMin ||
-           (tanCur == tanMin && (p->x > m->x || sectorContainsSector(m, p))))) {
-        m = p;
-        tanMin = tanCur;
-      }
-    }
-
-    p = p->next;
-  } while (p != stop);
-
-  return m;
-}
-
-// whether sector in vertex m contains sector in vertex p in the same
-// coordinates
-template <typename N>
-bool Earcut<N>::sectorContainsSector(const Node *m, const Node *p) {
-  return area(m->prev, m, p->prev) < 0 && area(p->next, m, m->next) < 0;
-}
-
-// interlink polygon nodes in z-order
-template <typename N>
-void Earcut<N>::indexCurve(Node *start) {
-  assert(start);
-  Node *p = start;
-
-  do {
-    p->z = p->z ? p->z : zOrder(p->x, p->y);
-    p->prevZ = p->prev;
-    p->nextZ = p->next;
-    p = p->next;
-  } while (p != start);
-
-  p->prevZ->nextZ = nullptr;
-  p->prevZ = nullptr;
-
-  sortLinked(p);
-}
-
-// Simon Tatham's linked list merge sort algorithm
-// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
-template <typename N>
-typename Earcut<N>::Node *Earcut<N>::sortLinked(Node *list) {
-  assert(list);
-  Node *p;
-  Node *q;
-  Node *e;
-  Node *tail;
-  int i, numMerges, pSize, qSize;
-  int inSize = 1;
-
-  for (;;) {
-    p = list;
-    list = nullptr;
-    tail = nullptr;
-    numMerges = 0;
-
-    while (p) {
-      numMerges++;
-      q = p;
-      pSize = 0;
-      for (i = 0; i < inSize; i++) {
-        pSize++;
-        q = q->nextZ;
-        if (!q) break;
-      }
-
-      qSize = inSize;
-
-      while (pSize > 0 || (qSize > 0 && q)) {
-        if (pSize == 0) {
-          e = q;
-          q = q->nextZ;
-          qSize--;
-        } else if (qSize == 0 || !q) {
-          e = p;
-          p = p->nextZ;
-          pSize--;
-        } else if (p->z <= q->z) {
-          e = p;
-          p = p->nextZ;
-          pSize--;
-        } else {
-          e = q;
-          q = q->nextZ;
-          qSize--;
-        }
-
-        if (tail)
-          tail->nextZ = e;
-        else
-          list = e;
-
-        e->prevZ = tail;
-        tail = e;
-      }
-
-      p = q;
-    }
-
-    tail->nextZ = nullptr;
-
-    if (numMerges <= 1) return list;
-
-    inSize *= 2;
-  }
-}
-
-// z-order of a Vertex given coords and size of the data bounding box
-template <typename N>
-int32_t Earcut<N>::zOrder(const double x_, const double y_) {
-  // coords are transformed into non-negative 15-bit integer range
-  int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size);
-  int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size);
-
-  x = (x | (x << 8)) & 0x00FF00FF;
-  x = (x | (x << 4)) & 0x0F0F0F0F;
-  x = (x | (x << 2)) & 0x33333333;
-  x = (x | (x << 1)) & 0x55555555;
-
-  y = (y | (y << 8)) & 0x00FF00FF;
-  y = (y | (y << 4)) & 0x0F0F0F0F;
-  y = (y | (y << 2)) & 0x33333333;
-  y = (y | (y << 1)) & 0x55555555;
-
-  return x | (y << 1);
-}
-
-// find the leftmost node of a polygon ring
-template <typename N>
-typename Earcut<N>::Node *Earcut<N>::getLeftmost(Node *start) {
-  Node *p = start;
-  Node *leftmost = start;
-  do {
-    if (p->x < leftmost->x || (p->x == leftmost->x && p->y < leftmost->y))
-      leftmost = p;
-    p = p->next;
-  } while (p != start);
-
-  return leftmost;
-}
-
-// check if a point lies within a convex triangle
-template <typename N>
-bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by,
-                                double cx, double cy, double px,
-                                double py) const {
-  return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
-         (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
-         (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
-}
-
-// check if a diagonal between two polygon nodes is valid (lies in polygon
-// interior)
-template <typename N>
-bool Earcut<N>::isValidDiagonal(Node *a, Node *b) {
-  return a->next->i != b->i && a->prev->i != b->i &&
-         !intersectsPolygon(a, b) &&  // dones't intersect other edges
-         ((locallyInside(a, b) && locallyInside(b, a) &&
-           middleInside(a, b) &&  // locally visible
-           (area(a->prev, a, b->prev) != 0.0 ||
-            area(a, b->prev, b) !=
-                0.0)) ||  // does not create opposite-facing sectors
-          (equals(a, b) && area(a->prev, a, a->next) > 0 &&
-           area(b->prev, b, b->next) > 0));  // special zero-length case
-}
-
-// signed area of a triangle
-template <typename N>
-double Earcut<N>::area(const Node *p, const Node *q, const Node *r) const {
-  return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y);
-}
-
-// check if two points are equal
-template <typename N>
-bool Earcut<N>::equals(const Node *p1, const Node *p2) {
-  return p1->x == p2->x && p1->y == p2->y;
-}
-
-// check if two segments intersect
-template <typename N>
-bool Earcut<N>::intersects(const Node *p1, const Node *q1, const Node *p2,
-                           const Node *q2) {
-  int o1 = sign(area(p1, q1, p2));
-  int o2 = sign(area(p1, q1, q2));
-  int o3 = sign(area(p2, q2, p1));
-  int o4 = sign(area(p2, q2, q1));
-
-  if (o1 != o2 && o3 != o4) return true;  // general case
-
-  if (o1 == 0 && onSegment(p1, p2, q1))
-    return true;  // p1, q1 and p2 are collinear and p2 lies on p1q1
-  if (o2 == 0 && onSegment(p1, q2, q1))
-    return true;  // p1, q1 and q2 are collinear and q2 lies on p1q1
-  if (o3 == 0 && onSegment(p2, p1, q2))
-    return true;  // p2, q2 and p1 are collinear and p1 lies on p2q2
-  if (o4 == 0 && onSegment(p2, q1, q2))
-    return true;  // p2, q2 and q1 are collinear and q1 lies on p2q2
-
-  return false;
-}
-
-// for collinear points p, q, r, check if point q lies on segment pr
-template <typename N>
-bool Earcut<N>::onSegment(const Node *p, const Node *q, const Node *r) {
-  return q->x <= std::max<double>(p->x, r->x) &&
-         q->x >= std::min<double>(p->x, r->x) &&
-         q->y <= std::max<double>(p->y, r->y) &&
-         q->y >= std::min<double>(p->y, r->y);
-}
-
-template <typename N>
-int Earcut<N>::sign(double val) {
-  return (0.0 < val) - (val < 0.0);
-}
-
-// check if a polygon diagonal intersects any polygon segments
-template <typename N>
-bool Earcut<N>::intersectsPolygon(const Node *a, const Node *b) {
-  const Node *p = a;
-  do {
-    if (p->i != a->i && p->next->i != a->i && p->i != b->i &&
-        p->next->i != b->i && intersects(p, p->next, a, b))
-      return true;
-    p = p->next;
-  } while (p != a);
-
-  return false;
-}
-
-// check if a polygon diagonal is locally inside the polygon
-template <typename N>
-bool Earcut<N>::locallyInside(const Node *a, const Node *b) {
-  return area(a->prev, a, a->next) < 0
-             ? area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0
-             : area(a, b, a->prev) < 0 || area(a, a->next, b) < 0;
-}
-
-// check if the middle Vertex of a polygon diagonal is inside the polygon
-template <typename N>
-bool Earcut<N>::middleInside(const Node *a, const Node *b) {
-  const Node *p = a;
-  bool inside = false;
-  double px = (a->x + b->x) / 2;
-  double py = (a->y + b->y) / 2;
-  do {
-    if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y &&
-        (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x))
-      inside = !inside;
-    p = p->next;
-  } while (p != a);
-
-  return inside;
-}
-
-// link two polygon vertices with a bridge; if the vertices belong to the same
-// ring, it splits polygon into two; if one belongs to the outer ring and
-// another to a hole, it merges it into a single ring
-template <typename N>
-typename Earcut<N>::Node *Earcut<N>::splitPolygon(Node *a, Node *b) {
-  Node *a2 = nodes.construct(a->i, a->x, a->y);
-  Node *b2 = nodes.construct(b->i, b->x, b->y);
-  Node *an = a->next;
-  Node *bp = b->prev;
-
-  a->next = b;
-  b->prev = a;
-
-  a2->next = an;
-  an->prev = a2;
-
-  b2->next = a2;
-  a2->prev = b2;
-
-  bp->next = b2;
-  b2->prev = bp;
-
-  return b2;
-}
-
-// create a node and util::optionally link it with previous one (in a circular
-// doubly linked list)
-template <typename N>
-template <typename Point>
-typename Earcut<N>::Node *Earcut<N>::insertNode(std::size_t i, const Point &pt,
-                                                Node *last) {
-  Node *p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt),
-                            util::nth<1, Point>::get(pt));
-
-  if (!last) {
-    p->prev = p;
-    p->next = p;
+#ifdef TINYOBJLOADER_DONOT_INCLUDE_MAPBOX_EARCUT
+// Assume earcut.hpp is included outside of tiny_obj_loader.h
+#else
 
-  } else {
-    assert(last);
-    p->next = last->next;
-    p->prev = last;
-    last->next->prev = p;
-    last->next = p;
-  }
-  return p;
-}
+#ifdef __clang__
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Weverything"
+#endif
 
-template <typename N>
-void Earcut<N>::removeNode(Node *p) {
-  p->next->prev = p->prev;
-  p->prev->next = p->next;
+#include <array>
+#include "mapbox/earcut.hpp"
 
-  if (p->prevZ) p->prevZ->nextZ = p->nextZ;
-  if (p->nextZ) p->nextZ->prevZ = p->prevZ;
-}
-}  // namespace detail
+#ifdef __clang__
+#pragma clang diagnostic pop
+#endif
 
-template <typename N = uint32_t, typename Polygon>
-std::vector<N> earcut(const Polygon &poly) {
-  mapbox::detail::Earcut<N> earcut;
-  earcut(poly);
-  return std::move(earcut.indices);
-}
-}  // namespace mapbox
+#endif
 
 #endif  // TINYOBJLOADER_USE_MAPBOX_EARCUT