src/utils/SkPolyUtils.cpp

/*
 * Copyright 2017 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "src/utils/SkPolyUtils.h"

#include <limits>

#include "include/private/SkNx.h"
#include "include/private/SkTArray.h"
#include "include/private/SkTemplates.h"
#include "src/core/SkPointPriv.h"
#include "src/core/SkTDPQueue.h"
#include "src/core/SkTInternalLList.h"

//////////////////////////////////////////////////////////////////////////////////
// Helper data structures and functions

struct OffsetSegment {
    SkPoint fP0;
    SkVector fV;
};

constexpr SkScalar kCrossTolerance = SK_ScalarNearlyZero * SK_ScalarNearlyZero;

// Computes perpDot for point p compared to segment defined by origin p0 and vector v.
// A positive value means the point is to the left of the segment,
// negative is to the right, 0 is collinear.
static int compute_side(const SkPoint& p0, const SkVector& v, const SkPoint& p) {
    SkVector w = p - p0;
    SkScalar perpDot = v.cross(w);
    if (!SkScalarNearlyZero(perpDot, kCrossTolerance)) {
        return ((perpDot > 0) ? 1 : -1);
    }

    return 0;
}

// Returns 1 for cw, -1 for ccw and 0 if zero signed area (either degenerate or self-intersecting)
int SkGetPolygonWinding(const SkPoint* polygonVerts, int polygonSize) {
    if (polygonSize < 3) {
        return 0;
    }

    // compute area and use sign to determine winding
    SkScalar quadArea = 0;
    SkVector v0 = polygonVerts[1] - polygonVerts[0];
    for (int curr = 2; curr < polygonSize; ++curr) {
        SkVector v1 = polygonVerts[curr] - polygonVerts[0];
        quadArea += v0.cross(v1);
        v0 = v1;
    }
    if (SkScalarNearlyZero(quadArea, kCrossTolerance)) {
        return 0;
    }
    // 1 == ccw, -1 == cw
    return (quadArea > 0) ? 1 : -1;
}

// Compute difference vector to offset p0-p1 'offset' units in direction specified by 'side'
bool compute_offset_vector(const SkPoint& p0, const SkPoint& p1, SkScalar offset, int side,
                           SkPoint* vector) {
    SkASSERT(side == -1 || side == 1);
    // if distances are equal, can just outset by the perpendicular
    SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX);
    if (!perp.setLength(offset*side)) {
        return false;
    }
    *vector = perp;
    return true;
}

// check interval to see if intersection is in segment
static inline bool outside_interval(SkScalar numer, SkScalar denom, bool denomPositive) {
    return (denomPositive && (numer < 0 || numer > denom)) ||
           (!denomPositive && (numer > 0 || numer < denom));
}

// Compute the intersection 'p' between segments s0 and s1, if any.
// 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'.
// Returns false if there is no intersection.
static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s1,
                                 SkPoint* p, SkScalar* s, SkScalar* t) {
    const SkVector& v0 = s0.fV;
    const SkVector& v1 = s1.fV;
    SkVector w = s1.fP0 - s0.fP0;
    SkScalar denom = v0.cross(v1);
    bool denomPositive = (denom > 0);
    SkScalar sNumer, tNumer;
    if (SkScalarNearlyZero(denom, kCrossTolerance)) {
        // segments are parallel, but not collinear
        if (!SkScalarNearlyZero(w.cross(v0), kCrossTolerance) ||
            !SkScalarNearlyZero(w.cross(v1), kCrossTolerance)) {
            return false;
        }

        // Check for zero-length segments
        if (!SkPointPriv::CanNormalize(v0.fX, v0.fY)) {
            // Both are zero-length
            if (!SkPointPriv::CanNormalize(v1.fX, v1.fY)) {
                // Check if they're the same point
                if (!SkPointPriv::CanNormalize(w.fX, w.fY)) {
                    *p = s0.fP0;
                    *s = 0;
                    *t = 0;
                    return true;
                } else {
                    return false;
                }
            }
            // Otherwise project segment0's origin onto segment1
            tNumer = v1.dot(-w);
            denom = v1.dot(v1);
            if (outside_interval(tNumer, denom, true)) {
                return false;
            }
            sNumer = 0;
        } else {
            // Project segment1's endpoints onto segment0
            sNumer = v0.dot(w);
            denom = v0.dot(v0);
            tNumer = 0;
            if (outside_interval(sNumer, denom, true)) {
                // The first endpoint doesn't lie on segment0
                // If segment1 is degenerate, then there's no collision
                if (!SkPointPriv::CanNormalize(v1.fX, v1.fY)) {
                    return false;
                }

                // Otherwise try the other one
                SkScalar oldSNumer = sNumer;
                sNumer = v0.dot(w + v1);
                tNumer = denom;
                if (outside_interval(sNumer, denom, true)) {
                    // it's possible that segment1's interval surrounds segment0
                    // this is false if params have the same signs, and in that case no collision
                    if (sNumer*oldSNumer > 0) {
                        return false;
                    }
                    // otherwise project segment0's endpoint onto segment1 instead
                    sNumer = 0;
                    tNumer = v1.dot(-w);
                    denom = v1.dot(v1);
                }
            }
        }
    } else {
        sNumer = w.cross(v1);
        if (outside_interval(sNumer, denom, denomPositive)) {
            return false;
        }
        tNumer = w.cross(v0);
        if (outside_interval(tNumer, denom, denomPositive)) {
            return false;
        }
    }

    SkScalar localS = sNumer/denom;
    SkScalar localT = tNumer/denom;

    *p = s0.fP0 + v0*localS;
    *s = localS;
    *t = localT;

    return true;
}

bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) {
    if (polygonSize < 3) {
        return false;
    }

    SkScalar lastArea = 0;
    SkScalar lastPerpDot = 0;

    int prevIndex = polygonSize - 1;
    int currIndex = 0;
    int nextIndex = 1;
    SkPoint origin = polygonVerts[0];
    SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex];
    SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
    SkVector w0 = polygonVerts[currIndex] - origin;
    SkVector w1 = polygonVerts[nextIndex] - origin;
    for (int i = 0; i < polygonSize; ++i) {
        if (!polygonVerts[i].isFinite()) {
            return false;
        }

        // Check that winding direction is always the same (otherwise we have a reflex vertex)
        SkScalar perpDot = v0.cross(v1);
        if (lastPerpDot*perpDot < 0) {
            return false;
        }
        if (0 != perpDot) {
            lastPerpDot = perpDot;
        }

        // If the signed area ever flips it's concave
        // TODO: see if we can verify convexity only with signed area
        SkScalar quadArea = w0.cross(w1);
        if (quadArea*lastArea < 0) {
            return false;
        }
        if (0 != quadArea) {
            lastArea = quadArea;
        }

        prevIndex = currIndex;
        currIndex = nextIndex;
        nextIndex = (currIndex + 1) % polygonSize;
        v0 = v1;
        v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
        w0 = w1;
        w1 = polygonVerts[nextIndex] - origin;
    }

    return true;
}

struct OffsetEdge {
    OffsetEdge*   fPrev;
    OffsetEdge*   fNext;
    OffsetSegment fOffset;
    SkPoint       fIntersection;
    SkScalar      fTValue;
    uint16_t      fIndex;
    uint16_t      fEnd;

    void init(uint16_t start = 0, uint16_t end = 0) {
        fIntersection = fOffset.fP0;
        fTValue = SK_ScalarMin;
        fIndex = start;
        fEnd = end;
    }

    // special intersection check that looks for endpoint intersection
    bool checkIntersection(const OffsetEdge* that,
                           SkPoint* p, SkScalar* s, SkScalar* t) {
        if (this->fEnd == that->fIndex) {
            SkPoint p1 = this->fOffset.fP0 + this->fOffset.fV;
            if (SkPointPriv::EqualsWithinTolerance(p1, that->fOffset.fP0)) {
                *p = p1;
                *s = SK_Scalar1;
                *t = 0;
                return true;
            }
        }

        return compute_intersection(this->fOffset, that->fOffset, p, s, t);
    }

    // computes the line intersection and then the "distance" from that to this
    // this is really a signed squared distance, where negative means that
    // the intersection lies inside this->fOffset
    SkScalar computeCrossingDistance(const OffsetEdge* that) {
        const OffsetSegment& s0 = this->fOffset;
        const OffsetSegment& s1 = that->fOffset;
        const SkVector& v0 = s0.fV;
        const SkVector& v1 = s1.fV;

        SkScalar denom = v0.cross(v1);
        if (SkScalarNearlyZero(denom, kCrossTolerance)) {
            // segments are parallel
            return SK_ScalarMax;
        }

        SkVector w = s1.fP0 - s0.fP0;
        SkScalar localS = w.cross(v1) / denom;
        if (localS < 0) {
            localS = -localS;
        } else {
            localS -= SK_Scalar1;
        }

        localS *= SkScalarAbs(localS);
        localS *= v0.dot(v0);

        return localS;
    }

};

static void remove_node(const OffsetEdge* node, OffsetEdge** head) {
    // remove from linked list
    node->fPrev->fNext = node->fNext;
    node->fNext->fPrev = node->fPrev;
    if (node == *head) {
        *head = (node->fNext == node) ? nullptr : node->fNext;
    }
}

//////////////////////////////////////////////////////////////////////////////////

// The objective here is to inset all of the edges by the given distance, and then
// remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
// we should only be making left-hand turns (for cw polygons, we use the winding
// parameter to reverse this). We detect this by checking whether the second intersection
// on an edge is closer to its tail than the first one.
//
// We might also have the case that there is no intersection between two neighboring inset edges.
// In this case, one edge will lie to the right of the other and should be discarded along with
// its previous intersection (if any).
//
// Note: the assumption is that inputPolygon is convex and has no coincident points.
//
bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
                          SkScalar inset, SkTDArray<SkPoint>* insetPolygon) {
    if (inputPolygonSize < 3) {
        return false;
    }

    // restrict this to match other routines
    // practically we don't want anything bigger than this anyway
    if (inputPolygonSize > std::numeric_limits<uint16_t>::max()) {
        return false;
    }

    // can't inset by a negative or non-finite amount
    if (inset < -SK_ScalarNearlyZero || !SkScalarIsFinite(inset)) {
        return false;
    }

    // insetting close to zero just returns the original poly
    if (inset <= SK_ScalarNearlyZero) {
        for (int i = 0; i < inputPolygonSize; ++i) {
            *insetPolygon->push() = inputPolygonVerts[i];
        }
        return true;
    }

    // get winding direction
    int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
    if (0 == winding) {
        return false;
    }

    // set up
    SkAutoSTMalloc<64, OffsetEdge> edgeData(inputPolygonSize);
    int prev = inputPolygonSize - 1;
    for (int curr = 0; curr < inputPolygonSize; prev = curr, ++curr) {
        int next = (curr + 1) % inputPolygonSize;
        if (!inputPolygonVerts[curr].isFinite()) {
            return false;
        }
        // check for convexity just to be sure
        if (compute_side(inputPolygonVerts[prev], inputPolygonVerts[curr] - inputPolygonVerts[prev],
                         inputPolygonVerts[next])*winding < 0) {
            return false;
        }
        SkVector v = inputPolygonVerts[next] - inputPolygonVerts[curr];
        SkVector perp = SkVector::Make(-v.fY, v.fX);
        perp.setLength(inset*winding);
        edgeData[curr].fPrev = &edgeData[prev];
        edgeData[curr].fNext = &edgeData[next];
        edgeData[curr].fOffset.fP0 = inputPolygonVerts[curr] + perp;
        edgeData[curr].fOffset.fV = v;
        edgeData[curr].init();
    }

    OffsetEdge* head = &edgeData[0];
    OffsetEdge* currEdge = head;
    OffsetEdge* prevEdge = currEdge->fPrev;
    int insetVertexCount = inputPolygonSize;
    unsigned int iterations = 0;
    unsigned int maxIterations = inputPolygonSize * inputPolygonSize;
    while (head && prevEdge != currEdge) {
        ++iterations;
        // we should check each edge against each other edge at most once
        if (iterations > maxIterations) {
            return false;
        }

        SkScalar s, t;
        SkPoint intersection;
        if (compute_intersection(prevEdge->fOffset, currEdge->fOffset,
                                 &intersection, &s, &t)) {
            // if new intersection is further back on previous inset from the prior intersection
            if (s < prevEdge->fTValue) {
                // no point in considering this one again
                remove_node(prevEdge, &head);
                --insetVertexCount;
                // go back one segment
                prevEdge = prevEdge->fPrev;
            // we've already considered this intersection, we're done
            } else if (currEdge->fTValue > SK_ScalarMin &&
                       SkPointPriv::EqualsWithinTolerance(intersection,
                                                          currEdge->fIntersection,
                                                          1.0e-6f)) {
                break;
            } else {
                // add intersection
                currEdge->fIntersection = intersection;
                currEdge->fTValue = t;

                // go to next segment
                prevEdge = currEdge;
                currEdge = currEdge->fNext;
            }
        } else {
            // if prev to right side of curr
            int side = winding*compute_side(currEdge->fOffset.fP0,
                                            currEdge->fOffset.fV,
                                            prevEdge->fOffset.fP0);
            if (side < 0 &&
                side == winding*compute_side(currEdge->fOffset.fP0,
                                             currEdge->fOffset.fV,
                                             prevEdge->fOffset.fP0 + prevEdge->fOffset.fV)) {
                // no point in considering this one again
                remove_node(prevEdge, &head);
                --insetVertexCount;
                // go back one segment
                prevEdge = prevEdge->fPrev;
            } else {
                // move to next segment
                remove_node(currEdge, &head);
                --insetVertexCount;
                currEdge = currEdge->fNext;
            }
        }
    }

    // store all the valid intersections that aren't nearly coincident
    // TODO: look at the main algorithm and see if we can detect these better
    insetPolygon->reset();
    if (!head) {
        return false;
    }

    static constexpr SkScalar kCleanupTolerance = 0.01f;
    if (insetVertexCount >= 0) {
        insetPolygon->setReserve(insetVertexCount);
    }
    int currIndex = 0;
    *insetPolygon->push() = head->fIntersection;
    currEdge = head->fNext;
    while (currEdge != head) {
        if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
                                                (*insetPolygon)[currIndex],
                                                kCleanupTolerance)) {
            *insetPolygon->push() = currEdge->fIntersection;
            currIndex++;
        }
        currEdge = currEdge->fNext;
    }
    // make sure the first and last points aren't coincident
    if (currIndex >= 1 &&
        SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex],
                                            kCleanupTolerance)) {
        insetPolygon->pop();
    }

    return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->count());
}

///////////////////////////////////////////////////////////////////////////////////////////

// compute the number of points needed for a circular join when offsetting a reflex vertex
bool SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar offset,
                          SkScalar* rotSin, SkScalar* rotCos, int* n) {
    const SkScalar kRecipPixelsPerArcSegment = 0.25f;

    SkScalar rCos = v1.dot(v2);
    if (!SkScalarIsFinite(rCos)) {
        return false;
    }
    SkScalar rSin = v1.cross(v2);
    if (!SkScalarIsFinite(rSin)) {
        return false;
    }
    SkScalar theta = SkScalarATan2(rSin, rCos);

    SkScalar floatSteps = SkScalarAbs(offset*theta*kRecipPixelsPerArcSegment);
    // limit the number of steps to at most max uint16_t (that's all we can index)
    // knock one value off the top to account for rounding
    if (floatSteps >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }
    int steps = SkScalarRoundToInt(floatSteps);

    SkScalar dTheta = steps > 0 ? theta / steps : 0;
    *rotSin = SkScalarSin(dTheta);
    *rotCos = SkScalarCos(dTheta);
    *n = steps;
    return true;
}

///////////////////////////////////////////////////////////////////////////////////////////

// a point is "left" to another if its x-coord is less, or if equal, its y-coord is greater
static bool left(const SkPoint& p0, const SkPoint& p1) {
    return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY > p1.fY);
}

// a point is "right" to another if its x-coord is greater, or if equal, its y-coord is less
static bool right(const SkPoint& p0, const SkPoint& p1) {
    return p0.fX > p1.fX || (!(p0.fX < p1.fX) && p0.fY < p1.fY);
}

struct Vertex {
    static bool Left(const Vertex& qv0, const Vertex& qv1) {
        return left(qv0.fPosition, qv1.fPosition);
    }

    // packed to fit into 16 bytes (one cache line)
    SkPoint  fPosition;
    uint16_t fIndex;       // index in unsorted polygon
    uint16_t fPrevIndex;   // indices for previous and next vertex in unsorted polygon
    uint16_t fNextIndex;
    uint16_t fFlags;
};

enum VertexFlags {
    kPrevLeft_VertexFlag = 0x1,
    kNextLeft_VertexFlag = 0x2,
};

struct ActiveEdge {
    ActiveEdge() : fChild{ nullptr, nullptr }, fAbove(nullptr), fBelow(nullptr), fRed(false) {}
    ActiveEdge(const SkPoint& p0, const SkVector& v, uint16_t index0, uint16_t index1)
        : fSegment({ p0, v })
        , fIndex0(index0)
        , fIndex1(index1)
        , fAbove(nullptr)
        , fBelow(nullptr)
        , fRed(true) {
        fChild[0] = nullptr;
        fChild[1] = nullptr;
    }

    // Returns true if "this" is above "that", assuming this->p0 is to the left of that->p0
    // This is only used to verify the edgelist -- the actual test for insertion/deletion is much
    // simpler because we can make certain assumptions then.
    bool aboveIfLeft(const ActiveEdge* that) const {
        const SkPoint& p0 = this->fSegment.fP0;
        const SkPoint& q0 = that->fSegment.fP0;
        SkASSERT(p0.fX <= q0.fX);
        SkVector d = q0 - p0;
        const SkVector& v = this->fSegment.fV;
        const SkVector& w = that->fSegment.fV;
        // The idea here is that if the vector between the origins of the two segments (d)
        // rotates counterclockwise up to the vector representing the "this" segment (v),
        // then we know that "this" is above "that". If the result is clockwise we say it's below.
        if (this->fIndex0 != that->fIndex0) {
            SkScalar cross = d.cross(v);
            if (cross > kCrossTolerance) {
                return true;
            } else if (cross < -kCrossTolerance) {
                return false;
            }
        } else if (this->fIndex1 == that->fIndex1) {
            return false;
        }
        // At this point either the two origins are nearly equal or the origin of "that"
        // lies on dv. So then we try the same for the vector from the tail of "this"
        // to the head of "that". Again, ccw means "this" is above "that".
        // d = that.P1 - this.P0
        //   = that.fP0 + that.fV - this.fP0
        //   = that.fP0 - this.fP0 + that.fV
        //   = old_d + that.fV
        d += w;
        SkScalar cross = d.cross(v);
        if (cross > kCrossTolerance) {
            return true;
        } else if (cross < -kCrossTolerance) {
            return false;
        }
        // If the previous check fails, the two segments are nearly collinear
        // First check y-coord of first endpoints
        if (p0.fX < q0.fX) {
            return (p0.fY >= q0.fY);
        } else if (p0.fY > q0.fY) {
            return true;
        } else if (p0.fY < q0.fY) {
            return false;
        }
        // The first endpoints are the same, so check the other endpoint
        SkPoint p1 = p0 + v;
        SkPoint q1 = q0 + w;
        if (p1.fX < q1.fX) {
            return (p1.fY >= q1.fY);
        } else {
            return (p1.fY > q1.fY);
        }
    }

    // same as leftAndAbove(), but generalized
    bool above(const ActiveEdge* that) const {
        const SkPoint& p0 = this->fSegment.fP0;
        const SkPoint& q0 = that->fSegment.fP0;
        if (right(p0, q0)) {
            return !that->aboveIfLeft(this);
        } else {
            return this->aboveIfLeft(that);
        }
    }

    bool intersect(const SkPoint& q0, const SkVector& w, uint16_t index0, uint16_t index1) const {
        // check first to see if these edges are neighbors in the polygon
        if (this->fIndex0 == index0 || this->fIndex1 == index0 ||
            this->fIndex0 == index1 || this->fIndex1 == index1) {
            return false;
        }

        // We don't need the exact intersection point so we can do a simpler test here.
        const SkPoint& p0 = this->fSegment.fP0;
        const SkVector& v = this->fSegment.fV;
        SkPoint p1 = p0 + v;
        SkPoint q1 = q0 + w;

        // We assume some x-overlap due to how the edgelist works
        // This allows us to simplify our test
        // We need some slop here because storing the vector and recomputing the second endpoint
        // doesn't necessary give us the original result in floating point.
        // TODO: Store vector as double? Store endpoint as well?
        SkASSERT(q0.fX <= p1.fX + SK_ScalarNearlyZero);

        // if each segment straddles the other (i.e., the endpoints have different sides)
        // then they intersect
        bool result;
        if (p0.fX < q0.fX) {
            if (q1.fX < p1.fX) {
                result = (compute_side(p0, v, q0)*compute_side(p0, v, q1) < 0);
            } else {
                result = (compute_side(p0, v, q0)*compute_side(q0, w, p1) > 0);
            }
        } else {
            if (p1.fX < q1.fX) {
                result = (compute_side(q0, w, p0)*compute_side(q0, w, p1) < 0);
            } else {
                result = (compute_side(q0, w, p0)*compute_side(p0, v, q1) > 0);
            }
        }
        return result;
    }

    bool intersect(const ActiveEdge* edge) {
        return this->intersect(edge->fSegment.fP0, edge->fSegment.fV, edge->fIndex0, edge->fIndex1);
    }

    bool lessThan(const ActiveEdge* that) const {
        SkASSERT(!this->above(this));
        SkASSERT(!that->above(that));
        SkASSERT(!(this->above(that) && that->above(this)));
        return this->above(that);
    }

    bool equals(uint16_t index0, uint16_t index1) const {
        return (this->fIndex0 == index0 && this->fIndex1 == index1);
    }

    OffsetSegment fSegment;
    uint16_t fIndex0;   // indices for previous and next vertex in polygon
    uint16_t fIndex1;
    ActiveEdge* fChild[2];
    ActiveEdge* fAbove;
    ActiveEdge* fBelow;
    int32_t  fRed;
};

class ActiveEdgeList {
public:
    ActiveEdgeList(int maxEdges) {
        fAllocation = (char*) sk_malloc_throw(sizeof(ActiveEdge)*maxEdges);
        fCurrFree = 0;
        fMaxFree = maxEdges;
    }
    ~ActiveEdgeList() {
        fTreeHead.fChild[1] = nullptr;
        sk_free(fAllocation);
    }

    bool insert(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
        SkVector v = p1 - p0;
        if (!v.isFinite()) {
            return false;
        }
        // empty tree case -- easy
        if (!fTreeHead.fChild[1]) {
            ActiveEdge* root = fTreeHead.fChild[1] = this->allocate(p0, v, index0, index1);
            SkASSERT(root);
            if (!root) {
                return false;
            }
            root->fRed = false;
            return true;
        }

        // set up helpers
        ActiveEdge* top = &fTreeHead;
        ActiveEdge *grandparent = nullptr;
        ActiveEdge *parent = nullptr;
        ActiveEdge *curr = top->fChild[1];
        int dir = 0;
        int last = 0; // ?
        // predecessor and successor, for intersection check
        ActiveEdge* pred = nullptr;
        ActiveEdge* succ = nullptr;

        // search down the tree
        while (true) {
            if (!curr) {
                // check for intersection with predecessor and successor
                if ((pred && pred->intersect(p0, v, index0, index1)) ||
                    (succ && succ->intersect(p0, v, index0, index1))) {
                    return false;
                }
                // insert new node at bottom
                parent->fChild[dir] = curr = this->allocate(p0, v, index0, index1);
                SkASSERT(curr);
                if (!curr) {
                    return false;
                }
                curr->fAbove = pred;
                curr->fBelow = succ;
                if (pred) {
                    pred->fBelow = curr;
                }
                if (succ) {
                    succ->fAbove = curr;
                }
                if (IsRed(parent)) {
                    int dir2 = (top->fChild[1] == grandparent);
                    if (curr == parent->fChild[last]) {
                        top->fChild[dir2] = SingleRotation(grandparent, !last);
                    } else {
                        top->fChild[dir2] = DoubleRotation(grandparent, !last);
                    }
                }
                break;
            } else if (IsRed(curr->fChild[0]) && IsRed(curr->fChild[1])) {
                // color flip
                curr->fRed = true;
                curr->fChild[0]->fRed = false;
                curr->fChild[1]->fRed = false;
                if (IsRed(parent)) {
                    int dir2 = (top->fChild[1] == grandparent);
                    if (curr == parent->fChild[last]) {
                        top->fChild[dir2] = SingleRotation(grandparent, !last);
                    } else {
                        top->fChild[dir2] = DoubleRotation(grandparent, !last);
                    }
                }
            }

            last = dir;
            int side;
            // check to see if segment is above or below
            if (curr->fIndex0 == index0) {
                side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
            } else {
                side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
            }
            if (0 == side) {
                return false;
            }
            dir = (side < 0);

            if (0 == dir) {
                succ = curr;
            } else {
                pred = curr;
            }

            // update helpers
            if (grandparent) {
                top = grandparent;
            }
            grandparent = parent;
            parent = curr;
            curr = curr->fChild[dir];
        }

        // update root and make it black
        fTreeHead.fChild[1]->fRed = false;

        SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));

        return true;
    }

    // replaces edge p0p1 with p1p2
    bool replace(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
                 uint16_t index0, uint16_t index1, uint16_t index2) {
        if (!fTreeHead.fChild[1]) {
            return false;
        }

        SkVector v = p2 - p1;
        ActiveEdge* curr = &fTreeHead;
        ActiveEdge* found = nullptr;
        int dir = 1;

        // search
        while (curr->fChild[dir] != nullptr) {
            // update helpers
            curr = curr->fChild[dir];
            // save found node
            if (curr->equals(index0, index1)) {
                found = curr;
                break;
            } else {
                // check to see if segment is above or below
                int side;
                if (curr->fIndex1 == index1) {
                    side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
                } else {
                    side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
                }
                if (0 == side) {
                    return false;
                }
                dir = (side < 0);
            }
        }

        if (!found) {
            return false;
        }

        // replace if found
        ActiveEdge* pred = found->fAbove;
        ActiveEdge* succ = found->fBelow;
        // check deletion and insert intersection cases
        if (pred && (pred->intersect(found) || pred->intersect(p1, v, index1, index2))) {
            return false;
        }
        if (succ && (succ->intersect(found) || succ->intersect(p1, v, index1, index2))) {
            return false;
        }
        found->fSegment.fP0 = p1;
        found->fSegment.fV = v;
        found->fIndex0 = index1;
        found->fIndex1 = index2;
        // above and below should stay the same

        SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));

        return true;
    }

    bool remove(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
        if (!fTreeHead.fChild[1]) {
            return false;
        }

        ActiveEdge* curr = &fTreeHead;
        ActiveEdge* parent = nullptr;
        ActiveEdge* grandparent = nullptr;
        ActiveEdge* found = nullptr;
        int dir = 1;

        // search and push a red node down
        while (curr->fChild[dir] != nullptr) {
            int last = dir;

            // update helpers
            grandparent = parent;
            parent = curr;
            curr = curr->fChild[dir];
            // save found node
            if (curr->equals(index0, index1)) {
                found = curr;
                dir = 0;
            } else {
                // check to see if segment is above or below
                int side;
                if (curr->fIndex1 == index1) {
                    side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
                } else {
                    side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
                }
                if (0 == side) {
                    return false;
                }
                dir = (side < 0);
            }

            // push the red node down
            if (!IsRed(curr) && !IsRed(curr->fChild[dir])) {
                if (IsRed(curr->fChild[!dir])) {
                    parent = parent->fChild[last] = SingleRotation(curr, dir);
                } else {
                    ActiveEdge *s = parent->fChild[!last];

                    if (s != NULL) {
                        if (!IsRed(s->fChild[!last]) && !IsRed(s->fChild[last])) {
                            // color flip
                            parent->fRed = false;
                            s->fRed = true;
                            curr->fRed = true;
                        } else {
                            int dir2 = (grandparent->fChild[1] == parent);

                            if (IsRed(s->fChild[last])) {
                                grandparent->fChild[dir2] = DoubleRotation(parent, last);
                            } else if (IsRed(s->fChild[!last])) {
                                grandparent->fChild[dir2] = SingleRotation(parent, last);
                            }

                            // ensure correct coloring
                            curr->fRed = grandparent->fChild[dir2]->fRed = true;
                            grandparent->fChild[dir2]->fChild[0]->fRed = false;
                            grandparent->fChild[dir2]->fChild[1]->fRed = false;
                        }
                    }
                }
            }
        }

        // replace and remove if found
        if (found) {
            ActiveEdge* pred = found->fAbove;
            ActiveEdge* succ = found->fBelow;
            if ((pred && pred->intersect(found)) || (succ && succ->intersect(found))) {
                return false;
            }
            if (found != curr) {
                found->fSegment = curr->fSegment;
                found->fIndex0 = curr->fIndex0;
                found->fIndex1 = curr->fIndex1;
                found->fAbove = curr->fAbove;
                pred = found->fAbove;
                // we don't need to set found->fBelow here
            } else {
                if (succ) {
                    succ->fAbove = pred;
                }
            }
            if (pred) {
                pred->fBelow = curr->fBelow;
            }
            parent->fChild[parent->fChild[1] == curr] = curr->fChild[!curr->fChild[0]];

            // no need to delete
            curr->fAbove = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
            curr->fBelow = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
            if (fTreeHead.fChild[1]) {
                fTreeHead.fChild[1]->fRed = false;
            }
        }

        // update root and make it black
        if (fTreeHead.fChild[1]) {
            fTreeHead.fChild[1]->fRed = false;
        }

        SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));

        return true;
    }

private:
    // allocator
    ActiveEdge * allocate(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
        if (fCurrFree >= fMaxFree) {
            return nullptr;
        }
        char* bytes = fAllocation + sizeof(ActiveEdge)*fCurrFree;
        ++fCurrFree;
        return new(bytes) ActiveEdge(p0, p1, index0, index1);
    }

    ///////////////////////////////////////////////////////////////////////////////////
    // Red-black tree methods
    ///////////////////////////////////////////////////////////////////////////////////
    static bool IsRed(const ActiveEdge* node) {
        return node && node->fRed;
    }

    static ActiveEdge* SingleRotation(ActiveEdge* node, int dir) {
        ActiveEdge* tmp = node->fChild[!dir];

        node->fChild[!dir] = tmp->fChild[dir];
        tmp->fChild[dir] = node;

        node->fRed = true;
        tmp->fRed = false;

        return tmp;
    }

    static ActiveEdge* DoubleRotation(ActiveEdge* node, int dir) {
        node->fChild[!dir] = SingleRotation(node->fChild[!dir], !dir);

        return SingleRotation(node, dir);
    }

    // returns black link count
    static int VerifyTree(const ActiveEdge* tree) {
        if (!tree) {
            return 1;
        }

        const ActiveEdge* left = tree->fChild[0];
        const ActiveEdge* right = tree->fChild[1];

        // no consecutive red links
        if (IsRed(tree) && (IsRed(left) || IsRed(right))) {
            SkASSERT(false);
            return 0;
        }

        // check secondary links
        if (tree->fAbove) {
            SkASSERT(tree->fAbove->fBelow == tree);
            SkASSERT(tree->fAbove->lessThan(tree));
        }
        if (tree->fBelow) {
            SkASSERT(tree->fBelow->fAbove == tree);
            SkASSERT(tree->lessThan(tree->fBelow));
        }

        // violates binary tree order
        if ((left && tree->lessThan(left)) || (right && right->lessThan(tree))) {
            SkASSERT(false);
            return 0;
        }

        int leftCount = VerifyTree(left);
        int rightCount = VerifyTree(right);

        // return black link count
        if (leftCount != 0 && rightCount != 0) {
            // black height mismatch
            if (leftCount != rightCount) {
                SkASSERT(false);
                return 0;
            }
            return IsRed(tree) ? leftCount : leftCount + 1;
        } else {
            return 0;
        }
    }

    ActiveEdge fTreeHead;
    char*      fAllocation;
    int        fCurrFree;
    int        fMaxFree;
};

// Here we implement a sweep line algorithm to determine whether the provided points
// represent a simple polygon, i.e., the polygon is non-self-intersecting.
// We first insert the vertices into a priority queue sorting horizontally from left to right.
// Then as we pop the vertices from the queue we generate events which indicate that an edge
// should be added or removed from an edge list. If any intersections are detected in the edge
// list, then we know the polygon is self-intersecting and hence not simple.
bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
    if (polygonSize < 3) {
        return false;
    }

    // If it's convex, it's simple
    if (SkIsConvexPolygon(polygon, polygonSize)) {
        return true;
    }

    // practically speaking, it takes too long to process large polygons
    if (polygonSize > 2048) {
        return false;
    }

    SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize);
    for (int i = 0; i < polygonSize; ++i) {
        Vertex newVertex;
        if (!polygon[i].isFinite()) {
            return false;
        }
        newVertex.fPosition = polygon[i];
        newVertex.fIndex = i;
        newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
        newVertex.fNextIndex = (i + 1) % polygonSize;
        newVertex.fFlags = 0;
        if (left(polygon[newVertex.fPrevIndex], polygon[i])) {
            newVertex.fFlags |= kPrevLeft_VertexFlag;
        }
        if (left(polygon[newVertex.fNextIndex], polygon[i])) {
            newVertex.fFlags |= kNextLeft_VertexFlag;
        }
        vertexQueue.insert(newVertex);
    }

    // pop each vertex from the queue and generate events depending on
    // where it lies relative to its neighboring edges
    ActiveEdgeList sweepLine(polygonSize);
    while (vertexQueue.count() > 0) {
        const Vertex& v = vertexQueue.peek();

        // both to the right -- insert both
        if (v.fFlags == 0) {
            if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) {
                break;
            }
            if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) {
                break;
            }
        // both to the left -- remove both
        } else if (v.fFlags == (kPrevLeft_VertexFlag | kNextLeft_VertexFlag)) {
            if (!sweepLine.remove(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex)) {
                break;
            }
            if (!sweepLine.remove(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex)) {
                break;
            }
        // one to left and right -- replace one with another
        } else {
            if (v.fFlags & kPrevLeft_VertexFlag) {
                if (!sweepLine.replace(polygon[v.fPrevIndex], v.fPosition, polygon[v.fNextIndex],
                                       v.fPrevIndex, v.fIndex, v.fNextIndex)) {
                    break;
                }
            } else {
                SkASSERT(v.fFlags & kNextLeft_VertexFlag);
                if (!sweepLine.replace(polygon[v.fNextIndex], v.fPosition, polygon[v.fPrevIndex],
                                       v.fNextIndex, v.fIndex, v.fPrevIndex)) {
                    break;
                }
            }
        }

        vertexQueue.pop();
    }

    return (vertexQueue.count() == 0);
}

///////////////////////////////////////////////////////////////////////////////////////////

// helper function for SkOffsetSimplePolygon
static void setup_offset_edge(OffsetEdge* currEdge,
                              const SkPoint& endpoint0, const SkPoint& endpoint1,
                              uint16_t startIndex, uint16_t endIndex) {
    currEdge->fOffset.fP0 = endpoint0;
    currEdge->fOffset.fV = endpoint1 - endpoint0;
    currEdge->init(startIndex, endIndex);
}

static bool is_reflex_vertex(const SkPoint* inputPolygonVerts, int winding, SkScalar offset,
                             uint16_t prevIndex, uint16_t currIndex, uint16_t nextIndex) {
    int side = compute_side(inputPolygonVerts[prevIndex],
                            inputPolygonVerts[currIndex] - inputPolygonVerts[prevIndex],
                            inputPolygonVerts[nextIndex]);
    // if reflex point, we need to add extra edges
    return (side*winding*offset < 0);
}

bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
                           const SkRect& bounds, SkScalar offset,
                           SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) {
    if (inputPolygonSize < 3) {
        return false;
    }

    // need to be able to represent all the vertices in the 16-bit indices
    if (inputPolygonSize >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }

    if (!SkScalarIsFinite(offset)) {
        return false;
    }

    // can't inset more than the half bounds of the polygon
    if (offset > SkTMin(SkTAbs(SK_ScalarHalf*bounds.width()),
                        SkTAbs(SK_ScalarHalf*bounds.height()))) {
        return false;
    }

    // offsetting close to zero just returns the original poly
    if (SkScalarNearlyZero(offset)) {
        for (int i = 0; i < inputPolygonSize; ++i) {
            *offsetPolygon->push() = inputPolygonVerts[i];
            if (polygonIndices) {
                *polygonIndices->push() = i;
            }
        }
        return true;
    }

    // get winding direction
    int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
    if (0 == winding) {
        return false;
    }

    // build normals
    SkAutoSTMalloc<64, SkVector> normals(inputPolygonSize);
    unsigned int numEdges = 0;
    for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
         currIndex < inputPolygonSize;
         prevIndex = currIndex, ++currIndex) {
        if (!inputPolygonVerts[currIndex].isFinite()) {
            return false;
        }
        int nextIndex = (currIndex + 1) % inputPolygonSize;
        if (!compute_offset_vector(inputPolygonVerts[currIndex], inputPolygonVerts[nextIndex],
                                   offset, winding, &normals[currIndex])) {
            return false;
        }
        if (currIndex > 0) {
            // if reflex point, we need to add extra edges
            if (is_reflex_vertex(inputPolygonVerts, winding, offset,
                                 prevIndex, currIndex, nextIndex)) {
                SkScalar rotSin, rotCos;
                int numSteps;
                if (!SkComputeRadialSteps(normals[prevIndex], normals[currIndex], offset,
                                          &rotSin, &rotCos, &numSteps)) {
                    return false;
                }
                numEdges += SkTMax(numSteps, 1);
            }
        }
        numEdges++;
    }
    // finish up the edge counting
    if (is_reflex_vertex(inputPolygonVerts, winding, offset, inputPolygonSize-1, 0, 1)) {
        SkScalar rotSin, rotCos;
        int numSteps;
        if (!SkComputeRadialSteps(normals[inputPolygonSize-1], normals[0], offset,
                                  &rotSin, &rotCos, &numSteps)) {
            return false;
        }
        numEdges += SkTMax(numSteps, 1);
    }

    // Make sure we don't overflow the max array count.
    // We shouldn't overflow numEdges, as SkComputeRadialSteps returns a max of 2^16-1,
    // and we have a max of 2^16-1 original vertices.
    if (numEdges > (unsigned int)std::numeric_limits<int32_t>::max()) {
        return false;
    }

    // build initial offset edge list
    SkSTArray<64, OffsetEdge> edgeData(numEdges);
    OffsetEdge* prevEdge = nullptr;
    for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
         currIndex < inputPolygonSize;
         prevIndex = currIndex, ++currIndex) {
        int nextIndex = (currIndex + 1) % inputPolygonSize;
        // if reflex point, fill in curve
        if (is_reflex_vertex(inputPolygonVerts, winding, offset,
                             prevIndex, currIndex, nextIndex)) {
            SkScalar rotSin, rotCos;
            int numSteps;
            SkVector prevNormal = normals[prevIndex];
            if (!SkComputeRadialSteps(prevNormal, normals[currIndex], offset,
                                      &rotSin, &rotCos, &numSteps)) {
                return false;
            }
            auto currEdge = edgeData.push_back_n(SkTMax(numSteps, 1));
            for (int i = 0; i < numSteps - 1; ++i) {
                SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin,
                                                     prevNormal.fY*rotCos + prevNormal.fX*rotSin);
                setup_offset_edge(currEdge,
                                  inputPolygonVerts[currIndex] + prevNormal,
                                  inputPolygonVerts[currIndex] + currNormal,
                                  currIndex, currIndex);
                prevNormal = currNormal;
                currEdge->fPrev = prevEdge;
                if (prevEdge) {
                    prevEdge->fNext = currEdge;
                }
                prevEdge = currEdge;
                ++currEdge;
            }
            setup_offset_edge(currEdge,
                              inputPolygonVerts[currIndex] + prevNormal,
                              inputPolygonVerts[currIndex] + normals[currIndex],
                              currIndex, currIndex);
            currEdge->fPrev = prevEdge;
            if (prevEdge) {
                prevEdge->fNext = currEdge;
            }
            prevEdge = currEdge;
        }

        // Add the edge
        auto currEdge = edgeData.push_back_n(1);
        setup_offset_edge(currEdge,
                          inputPolygonVerts[currIndex] + normals[currIndex],
                          inputPolygonVerts[nextIndex] + normals[currIndex],
                          currIndex, nextIndex);
        currEdge->fPrev = prevEdge;
        if (prevEdge) {
            prevEdge->fNext = currEdge;
        }
        prevEdge = currEdge;
    }
    // close up the linked list
    SkASSERT(prevEdge);
    prevEdge->fNext = &edgeData[0];
    edgeData[0].fPrev = prevEdge;

    // now clip edges
    SkASSERT(edgeData.count() == (int)numEdges);
    auto head = &edgeData[0];
    auto currEdge = head;
    unsigned int offsetVertexCount = numEdges;
    unsigned long long iterations = 0;
    unsigned long long maxIterations = (unsigned long long)(numEdges) * numEdges;
    while (head && prevEdge != currEdge && offsetVertexCount > 0) {
        ++iterations;
        // we should check each edge against each other edge at most once
        if (iterations > maxIterations) {
            return false;
        }

        SkScalar s, t;
        SkPoint intersection;
        if (prevEdge->checkIntersection(currEdge, &intersection, &s, &t)) {
            // if new intersection is further back on previous inset from the prior intersection
            if (s < prevEdge->fTValue) {
                // no point in considering this one again
                remove_node(prevEdge, &head);
                --offsetVertexCount;
                // go back one segment
                prevEdge = prevEdge->fPrev;
                // we've already considered this intersection, we're done
            } else if (currEdge->fTValue > SK_ScalarMin &&
                       SkPointPriv::EqualsWithinTolerance(intersection,
                                                          currEdge->fIntersection,
                                                          1.0e-6f)) {
                break;
            } else {
                // add intersection
                currEdge->fIntersection = intersection;
                currEdge->fTValue = t;
                currEdge->fIndex = prevEdge->fEnd;

                // go to next segment
                prevEdge = currEdge;
                currEdge = currEdge->fNext;
            }
        } else {
            // If there is no intersection, we want to minimize the distance between
            // the point where the segment lines cross and the segments themselves.
            OffsetEdge* prevPrevEdge = prevEdge->fPrev;
            OffsetEdge* currNextEdge = currEdge->fNext;
            SkScalar dist0 = currEdge->computeCrossingDistance(prevPrevEdge);
            SkScalar dist1 = prevEdge->computeCrossingDistance(currNextEdge);
            // if both lead to direct collision
            if (dist0 < 0 && dist1 < 0) {
                // check first to see if either represent parts of one contour
                SkPoint p1 = prevPrevEdge->fOffset.fP0 + prevPrevEdge->fOffset.fV;
                bool prevSameContour = SkPointPriv::EqualsWithinTolerance(p1,
                                                                          prevEdge->fOffset.fP0);
                p1 = currEdge->fOffset.fP0 + currEdge->fOffset.fV;
                bool currSameContour = SkPointPriv::EqualsWithinTolerance(p1,
                                                                         currNextEdge->fOffset.fP0);

                // want to step along contour to find intersections rather than jump to new one
                if (currSameContour && !prevSameContour) {
                    remove_node(currEdge, &head);
                    currEdge = currNextEdge;
                    --offsetVertexCount;
                    continue;
                } else if (prevSameContour && !currSameContour) {
                    remove_node(prevEdge, &head);
                    prevEdge = prevPrevEdge;
                    --offsetVertexCount;
                    continue;
                }
            }

            // otherwise minimize collision distance along segment
            if (dist0 < dist1) {
                remove_node(prevEdge, &head);
                prevEdge = prevPrevEdge;
            } else {
                remove_node(currEdge, &head);
                currEdge = currNextEdge;
            }
            --offsetVertexCount;
        }
    }

    // store all the valid intersections that aren't nearly coincident
    // TODO: look at the main algorithm and see if we can detect these better
    offsetPolygon->reset();
    if (!head || offsetVertexCount == 0 ||
        offsetVertexCount >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }

    static constexpr SkScalar kCleanupTolerance = 0.01f;
    offsetPolygon->setReserve(offsetVertexCount);
    int currIndex = 0;
    *offsetPolygon->push() = head->fIntersection;
    if (polygonIndices) {
        *polygonIndices->push() = head->fIndex;
    }
    currEdge = head->fNext;
    while (currEdge != head) {
        if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
                                                (*offsetPolygon)[currIndex],
                                                kCleanupTolerance)) {
            *offsetPolygon->push() = currEdge->fIntersection;
            if (polygonIndices) {
                *polygonIndices->push() = currEdge->fIndex;
            }
            currIndex++;
        }
        currEdge = currEdge->fNext;
    }
    // make sure the first and last points aren't coincident
    if (currIndex >= 1 &&
        SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex],
                                            kCleanupTolerance)) {
        offsetPolygon->pop();
        if (polygonIndices) {
            polygonIndices->pop();
        }
    }

    // check winding of offset polygon (it should be same as the original polygon)
    SkScalar offsetWinding = SkGetPolygonWinding(offsetPolygon->begin(), offsetPolygon->count());

    return (winding*offsetWinding > 0 &&
            SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->count()));
}

//////////////////////////////////////////////////////////////////////////////////////////

struct TriangulationVertex {
    SK_DECLARE_INTERNAL_LLIST_INTERFACE(TriangulationVertex);

    enum class VertexType { kConvex, kReflex };

    SkPoint    fPosition;
    VertexType fVertexType;
    uint16_t   fIndex;
    uint16_t   fPrevIndex;
    uint16_t   fNextIndex;
};

static void compute_triangle_bounds(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
                                    SkRect* bounds) {
    Sk4s min, max;
    min = max = Sk4s(p0.fX, p0.fY, p0.fX, p0.fY);
    Sk4s xy(p1.fX, p1.fY, p2.fX, p2.fY);
    min = Sk4s::Min(min, xy);
    max = Sk4s::Max(max, xy);
    bounds->setLTRB(SkTMin(min[0], min[2]), SkTMin(min[1], min[3]),
                    SkTMax(max[0], max[2]), SkTMax(max[1], max[3]));
}

// test to see if point p is in triangle p0p1p2.
// for now assuming strictly inside -- if on the edge it's outside
static bool point_in_triangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
                              const SkPoint& p) {
    SkVector v0 = p1 - p0;
    SkVector v1 = p2 - p1;
    SkScalar n = v0.cross(v1);

    SkVector w0 = p - p0;
    if (n*v0.cross(w0) < SK_ScalarNearlyZero) {
        return false;
    }

    SkVector w1 = p - p1;
    if (n*v1.cross(w1) < SK_ScalarNearlyZero) {
        return false;
    }

    SkVector v2 = p0 - p2;
    SkVector w2 = p - p2;
    if (n*v2.cross(w2) < SK_ScalarNearlyZero) {
        return false;
    }

    return true;
}

// Data structure to track reflex vertices and check whether any are inside a given triangle
class ReflexHash {
public:
    bool init(const SkRect& bounds, int vertexCount) {
        fBounds = bounds;
        fNumVerts = 0;
        SkScalar width = bounds.width();
        SkScalar height = bounds.height();
        if (!SkScalarIsFinite(width) || !SkScalarIsFinite(height)) {
            return false;
        }

        // We want vertexCount grid cells, roughly distributed to match the bounds ratio
        SkScalar hCount = SkScalarSqrt(sk_ieee_float_divide(vertexCount*width, height));
        if (!SkScalarIsFinite(hCount)) {
            return false;
        }
        fHCount = SkTMax(SkTMin(SkScalarRoundToInt(hCount), vertexCount), 1);
        fVCount = vertexCount/fHCount;
        fGridConversion.set(sk_ieee_float_divide(fHCount - 0.001f, width),
                            sk_ieee_float_divide(fVCount - 0.001f, height));
        if (!fGridConversion.isFinite()) {
            return false;
        }

        fGrid.setCount(fHCount*fVCount);
        for (int i = 0; i < fGrid.count(); ++i) {
            fGrid[i].reset();
        }

        return true;
    }

    void add(TriangulationVertex* v) {
        int index = hash(v);
        fGrid[index].addToTail(v);
        ++fNumVerts;
    }

    void remove(TriangulationVertex* v) {
        int index = hash(v);
        fGrid[index].remove(v);
        --fNumVerts;
    }

    bool checkTriangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
                       uint16_t ignoreIndex0, uint16_t ignoreIndex1) const {
        if (!fNumVerts) {
            return false;
        }

        SkRect triBounds;
        compute_triangle_bounds(p0, p1, p2, &triBounds);
        int h0 = (triBounds.fLeft - fBounds.fLeft)*fGridConversion.fX;
        int h1 = (triBounds.fRight - fBounds.fLeft)*fGridConversion.fX;
        int v0 = (triBounds.fTop - fBounds.fTop)*fGridConversion.fY;
        int v1 = (triBounds.fBottom - fBounds.fTop)*fGridConversion.fY;

        for (int v = v0; v <= v1; ++v) {
            for (int h = h0; h <= h1; ++h) {
                int i = v * fHCount + h;
                for (SkTInternalLList<TriangulationVertex>::Iter reflexIter = fGrid[i].begin();
                     reflexIter != fGrid[i].end(); ++reflexIter) {
                    TriangulationVertex* reflexVertex = *reflexIter;
                    if (reflexVertex->fIndex != ignoreIndex0 &&
                        reflexVertex->fIndex != ignoreIndex1 &&
                        point_in_triangle(p0, p1, p2, reflexVertex->fPosition)) {
                        return true;
                    }
                }

            }
        }

        return false;
    }

private:
    int hash(TriangulationVertex* vert) const {
        int h = (vert->fPosition.fX - fBounds.fLeft)*fGridConversion.fX;
        int v = (vert->fPosition.fY - fBounds.fTop)*fGridConversion.fY;
        SkASSERT(v*fHCount + h >= 0);
        return v*fHCount + h;
    }

    SkRect fBounds;
    int fHCount;
    int fVCount;
    int fNumVerts;
    // converts distance from the origin to a grid location (when cast to int)
    SkVector fGridConversion;
    SkTDArray<SkTInternalLList<TriangulationVertex>> fGrid;
};

// Check to see if a reflex vertex has become a convex vertex after clipping an ear
static void reclassify_vertex(TriangulationVertex* p, const SkPoint* polygonVerts,
                              int winding, ReflexHash* reflexHash,
                              SkTInternalLList<TriangulationVertex>* convexList) {
    if (TriangulationVertex::VertexType::kReflex == p->fVertexType) {
        SkVector v0 = p->fPosition - polygonVerts[p->fPrevIndex];
        SkVector v1 = polygonVerts[p->fNextIndex] - p->fPosition;
        if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
            p->fVertexType = TriangulationVertex::VertexType::kConvex;
            reflexHash->remove(p);
            p->fPrev = p->fNext = nullptr;
            convexList->addToTail(p);
        }
    }
}

bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, int polygonSize,
                                SkTDArray<uint16_t>* triangleIndices) {
    if (polygonSize < 3) {
        return false;
    }
    // need to be able to represent all the vertices in the 16-bit indices
    if (polygonSize >= std::numeric_limits<uint16_t>::max()) {
        return false;
    }

    // get bounds
    SkRect bounds;
    if (!bounds.setBoundsCheck(polygonVerts, polygonSize)) {
        return false;
    }
    // get winding direction
    // TODO: we do this for all the polygon routines -- might be better to have the client
    // compute it and pass it in
    int winding = SkGetPolygonWinding(polygonVerts, polygonSize);
    if (0 == winding) {
        return false;
    }

    // Set up vertices
    SkAutoSTMalloc<64, TriangulationVertex> triangulationVertices(polygonSize);
    int prevIndex = polygonSize - 1;
    SkVector v0 = polygonVerts[0] - polygonVerts[prevIndex];
    for (int currIndex = 0; currIndex < polygonSize; ++currIndex) {
        int nextIndex = (currIndex + 1) % polygonSize;

        SkDEBUGCODE(memset(&triangulationVertices[currIndex], 0, sizeof(TriangulationVertex)));
        triangulationVertices[currIndex].fPosition = polygonVerts[currIndex];
        triangulationVertices[currIndex].fIndex = currIndex;
        triangulationVertices[currIndex].fPrevIndex = prevIndex;
        triangulationVertices[currIndex].fNextIndex = nextIndex;
        SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
        if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
            triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kConvex;
        } else {
            triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kReflex;
        }

        prevIndex = currIndex;
        v0 = v1;
    }

    // Classify initial vertices into a list of convex vertices and a hash of reflex vertices
    // TODO: possibly sort the convexList in some way to get better triangles
    SkTInternalLList<TriangulationVertex> convexList;
    ReflexHash reflexHash;
    if (!reflexHash.init(bounds, polygonSize)) {
        return false;
    }
    prevIndex = polygonSize - 1;
    for (int currIndex = 0; currIndex < polygonSize; prevIndex = currIndex, ++currIndex) {
        TriangulationVertex::VertexType currType = triangulationVertices[currIndex].fVertexType;
        if (TriangulationVertex::VertexType::kConvex == currType) {
            int nextIndex = (currIndex + 1) % polygonSize;
            TriangulationVertex::VertexType prevType = triangulationVertices[prevIndex].fVertexType;
            TriangulationVertex::VertexType nextType = triangulationVertices[nextIndex].fVertexType;
            // We prioritize clipping vertices with neighboring reflex vertices.
            // The intent here is that it will cull reflex vertices more quickly.
            if (TriangulationVertex::VertexType::kReflex == prevType ||
                TriangulationVertex::VertexType::kReflex == nextType) {
                convexList.addToHead(&triangulationVertices[currIndex]);
            } else {
                convexList.addToTail(&triangulationVertices[currIndex]);
            }
        } else {
            // We treat near collinear vertices as reflex
            reflexHash.add(&triangulationVertices[currIndex]);
        }
    }

    // The general concept: We are trying to find three neighboring vertices where
    // no other vertex lies inside the triangle (an "ear"). If we find one, we clip
    // that ear off, and then repeat on the new polygon. Once we get down to three vertices
    // we have triangulated the entire polygon.
    // In the worst case this is an n^2 algorithm. We can cut down the search space somewhat by
    // noting that only convex vertices can be potential ears, and we only need to check whether
    // any reflex vertices lie inside the ear.
    triangleIndices->setReserve(triangleIndices->count() + 3 * (polygonSize - 2));
    int vertexCount = polygonSize;
    while (vertexCount > 3) {
        bool success = false;
        TriangulationVertex* earVertex = nullptr;
        TriangulationVertex* p0 = nullptr;
        TriangulationVertex* p2 = nullptr;
        // find a convex vertex to clip
        for (SkTInternalLList<TriangulationVertex>::Iter convexIter = convexList.begin();
             convexIter != convexList.end(); ++convexIter) {
            earVertex = *convexIter;
            SkASSERT(TriangulationVertex::VertexType::kReflex != earVertex->fVertexType);

            p0 = &triangulationVertices[earVertex->fPrevIndex];
            p2 = &triangulationVertices[earVertex->fNextIndex];

            // see if any reflex vertices are inside the ear
            bool failed = reflexHash.checkTriangle(p0->fPosition, earVertex->fPosition,
                                                   p2->fPosition, p0->fIndex, p2->fIndex);
            if (failed) {
                continue;
            }

            // found one we can clip
            success = true;
            break;
        }
        // If we can't find any ears to clip, this probably isn't a simple polygon
        if (!success) {
            return false;
        }

        // add indices
        auto indices = triangleIndices->append(3);
        indices[0] = indexMap[p0->fIndex];
        indices[1] = indexMap[earVertex->fIndex];
        indices[2] = indexMap[p2->fIndex];

        // clip the ear
        convexList.remove(earVertex);
        --vertexCount;

        // reclassify reflex verts
        p0->fNextIndex = earVertex->fNextIndex;
        reclassify_vertex(p0, polygonVerts, winding, &reflexHash, &convexList);

        p2->fPrevIndex = earVertex->fPrevIndex;
        reclassify_vertex(p2, polygonVerts, winding, &reflexHash, &convexList);
    }

    // output indices
    for (SkTInternalLList<TriangulationVertex>::Iter vertexIter = convexList.begin();
         vertexIter != convexList.end(); ++vertexIter) {
        TriangulationVertex* vertex = *vertexIter;
        *triangleIndices->push() = indexMap[vertex->fIndex];
    }

    return true;
}

///////////

static double crs(SkVector a, SkVector b) {
    return a.fX * b.fY - a.fY * b.fX;
}

static int sign(SkScalar v) {
    return v < 0 ? -1 : (v > 0);
}

struct SignTracker {
    int fSign;
    int fSignChanges;

    void reset() {
        fSign = 0;
        fSignChanges = 0;
    }

    void init(int s) {
        SkASSERT(fSignChanges == 0);
        SkASSERT(s == 1 || s == -1 || s == 0);
        fSign = s;
        fSignChanges = 1;
    }

    void update(int s) {
        if (s) {
            if (fSign != s) {
                fSignChanges += 1;
                fSign = s;
            }
        }
    }
};

struct ConvexTracker {
    SkVector    fFirst, fPrev;
    SignTracker fDSign, fCSign;
    int         fVecCounter;
    bool        fIsConcave;

    ConvexTracker() { this->reset(); }

    void reset() {
        fPrev = {0, 0};
        fDSign.reset();
        fCSign.reset();
        fVecCounter = 0;
        fIsConcave = false;
    }

    void addVec(SkPoint p1, SkPoint p0) {
        this->addVec(p1 - p0);
    }
    void addVec(SkVector v) {
        if (v.fX == 0 && v.fY == 0) {
            return;
        }

        fVecCounter += 1;
        if (fVecCounter == 1) {
            fFirst = fPrev = v;
            fDSign.update(sign(v.fX));
            return;
        }

        SkScalar d = v.fX;
        SkScalar c = crs(fPrev, v);
        int sign_c;
        if (c) {
            sign_c = sign(c);
        } else {
            if (d >= 0) {
                sign_c = fCSign.fSign;
            } else {
                sign_c = -fCSign.fSign;
            }
        }

        fDSign.update(sign(d));
        fCSign.update(sign_c);
        fPrev = v;

        if (fDSign.fSignChanges > 3 || fCSign.fSignChanges > 1) {
            fIsConcave = true;
        }
    }

    void finalCross() {
        this->addVec(fFirst);
    }
};

bool SkIsPolyConvex_experimental(const SkPoint pts[], int count) {
    if (count <= 3) {
        return true;
    }

    ConvexTracker tracker;

    for (int i = 0; i < count - 1; ++i) {
        tracker.addVec(pts[i + 1], pts[i]);
        if (tracker.fIsConcave) {
            return false;
        }
    }
    tracker.addVec(pts[0], pts[count - 1]);
    tracker.finalCross();
    return !tracker.fIsConcave;
}