Revert "Add some optimizations to PolyUtils"

This reverts commit 8bb0db3d07450880d346d808018708416c928657.

Reason for revert: Breaking Google3.

Original change's description:
> Add some optimizations to PolyUtils
> 
> * Switch inset/offset code to use a linked list rather than an array
> * Use std::set to store active edge list for IsSimplePolygon rather than array
> * Pre-alloc the priority queue for IsSimplePolygon
> * When adding radial curves, expand the array all at once rather than pushing
> one at a time.
> 
> Bug: skia:
> Change-Id: I692f8c29c500c41ec1d1be39d924d8a752676bf4
> Reviewed-on: https://skia-review.googlesource.com/140787
> Reviewed-by: Robert Phillips <robertphillips@google.com>
> Commit-Queue: Jim Van Verth <jvanverth@google.com>

TBR=jvanverth@google.com,bsalomon@google.com,robertphillips@google.com

Change-Id: Ie8afecd899fa9bd79d22fdf46ec82a0c9e94e893
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: skia:
Reviewed-on: https://skia-review.googlesource.com/141980
Reviewed-by: Jim Van Verth <jvanverth@google.com>
Commit-Queue: Jim Van Verth <jvanverth@google.com>

4 files changed, 219 insertions, 325 deletions

diff --git a/bench/PolyUtilsBench.cpp b/bench/PolyUtilsBench.cpp
index e03c51cf8d..1b987fa038 100644
--- a/bench/PolyUtilsBench.cpp
+++ b/bench/PolyUtilsBench.cpp
@@ -9,12 +9,12 @@
 #include "SkPolyUtils.h"
 
 class PolyUtilsBench : public Benchmark {
-public:
     // Evaluate SkTriangulateSimplePolygon's performance (via derived classes) on:
     //   a non-self-intersecting star, a circle of tiny line segments and a self-intersecting star
-    enum class Type { kConvexCheck, kSimpleCheck, kInsetConvex, kOffsetSimple, kTessellateSimple };
 
-    PolyUtilsBench(Type type) : fType(type) {}
+    SkString           fName;
+public:
+    PolyUtilsBench() {}
 
     virtual void appendName(SkString*) = 0;
     virtual void makePoly(SkTDArray<SkPoint>* poly) = 0;
@@ -24,84 +24,32 @@ protected:
     const char* onGetName() override {
         fName = "poly_utils_";
         this->appendName(&fName);
-        switch (fType) {
-        case Type::kConvexCheck:
-            fName.append("_c");
-            break;
-        case Type::kSimpleCheck:
-            fName.append("_s");
-            break;
-        case Type::kInsetConvex:
-            fName.append("_i");
-            break;
-        case Type::kOffsetSimple:
-            fName.append("_o");
-            break;
-        case Type::kTessellateSimple:
-            fName.append("_t");
-            break;
-        }
         return fName.c_str();
     }
 
     void onDraw(int loops, SkCanvas* canvas) override {
         SkTDArray<SkPoint> poly;
         this->makePoly(&poly);
-        switch (fType) {
-            case Type::kConvexCheck:
-                for (int i = 0; i < loops; i++) {
-                    (void)SkIsConvexPolygon(poly.begin(), poly.count());
-                }
-                break;
-            case Type::kSimpleCheck:
-                for (int i = 0; i < loops; i++) {
-                    (void)SkIsSimplePolygon(poly.begin(), poly.count());
-                }
-                break;
-            case Type::kInsetConvex:
-                if (SkIsConvexPolygon(poly.begin(), poly.count())) {
-                    SkTDArray<SkPoint> result;
-                    for (int i = 0; i < loops; i++) {
-                        (void)SkInsetConvexPolygon(poly.begin(), poly.count(), 10, &result);
-                        (void)SkInsetConvexPolygon(poly.begin(), poly.count(), 40, &result);
-                    }
-                }
-                break;
-            case Type::kOffsetSimple:
-                if (SkIsSimplePolygon(poly.begin(), poly.count())) {
-                    SkTDArray<SkPoint> result;
-                    for (int i = 0; i < loops; i++) {
-                        (void)SkOffsetSimplePolygon(poly.begin(), poly.count(), 10, &result);
-                        (void)SkOffsetSimplePolygon(poly.begin(), poly.count(), -10, &result);
-                    }
-                }
-                break;
-            case Type::kTessellateSimple:
-                if (SkIsSimplePolygon(poly.begin(), poly.count())) {
-                    SkAutoSTMalloc<64, uint16_t> indexMap(poly.count());
-                    for (int i = 0; i < poly.count(); ++i) {
-                        indexMap[i] = i;
-                    }
-                    SkTDArray<uint16_t> triangleIndices;
-                    for (int i = 0; i < loops; i++) {
-                        SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
-                                                   &triangleIndices);
-                    }
-                }
-                break;
+        SkAutoSTMalloc<64, uint16_t> indexMap(poly.count());
+        for (int i = 0; i < poly.count(); ++i) {
+            indexMap[i] = i;
+        }
+        SkTDArray<uint16_t> triangleIndices;
+        for (int i = 0; i < loops; i++) {
+            if (SkIsSimplePolygon(poly.begin(), poly.count())) {
+                SkTriangulateSimplePolygon(poly.begin(), indexMap, poly.count(),
+                                           &triangleIndices);
+            }
         }
     }
 
 private:
-    SkString           fName;
-    Type               fType;
-
     typedef Benchmark INHERITED;
 };
 
 class StarPolyUtilsBench : public PolyUtilsBench {
 public:
-    StarPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {}
+    StarPolyUtilsBench() {}
 
     void appendName(SkString* name) override {
         name->append("star");
@@ -129,7 +77,7 @@ private:
 
 class CirclePolyUtilsBench : public PolyUtilsBench {
 public:
-    CirclePolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {}
+    CirclePolyUtilsBench() {}
 
     void appendName(SkString* name) override {
         name->append("circle");
@@ -153,7 +101,7 @@ private:
 
 class IntersectingPolyUtilsBench : public PolyUtilsBench {
 public:
-    IntersectingPolyUtilsBench(PolyUtilsBench::Type type) : INHERITED(type) {}
+    IntersectingPolyUtilsBench() {}
 
     void appendName(SkString* name) override {
         name->append("intersecting");
@@ -177,18 +125,6 @@ private:
     typedef PolyUtilsBench INHERITED;
 };
 
-DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);)
-DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);)
-DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);)
-DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);)
-DEF_BENCH(return new StarPolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);)
-DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);)
-DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);)
-DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);)
-DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);)
-DEF_BENCH(return new CirclePolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);)
-DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kConvexCheck);)
-DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kSimpleCheck);)
-DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kInsetConvex);)
-DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kOffsetSimple);)
-DEF_BENCH(return new IntersectingPolyUtilsBench(PolyUtilsBench::Type::kTessellateSimple);)
+DEF_BENCH(return new StarPolyUtilsBench();)
+DEF_BENCH(return new CirclePolyUtilsBench();)
+DEF_BENCH(return new IntersectingPolyUtilsBench();)
diff --git a/src/core/SkTDPQueue.h b/src/core/SkTDPQueue.h
index 6e2a09ca8a..5dca4910ed 100644
--- a/src/core/SkTDPQueue.h
+++ b/src/core/SkTDPQueue.h
@@ -30,7 +30,6 @@ template <typename T,
 class SkTDPQueue {
 public:
     SkTDPQueue() {}
-    SkTDPQueue(int reserve) { fArray.setReserve(reserve); }
 
     SkTDPQueue(SkTDPQueue&&) = default;
     SkTDPQueue& operator =(SkTDPQueue&&) = default;
diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp
index e80e12f446..b76d270d15 100644
--- a/src/utils/SkPolyUtils.cpp
+++ b/src/utils/SkPolyUtils.cpp
@@ -7,7 +7,6 @@
 
 #include "SkPolyUtils.h"
 
-#include <set>
 #include "SkPointPriv.h"
 #include "SkTArray.h"
 #include "SkTemplates.h"
@@ -299,32 +298,34 @@ bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) {
     return true;
 }
 
-struct OffsetEdge {
-    OffsetEdge*   fPrev;
-    OffsetEdge*   fNext;
+struct EdgeData {
     OffsetSegment fInset;
     SkPoint       fIntersection;
     SkScalar      fTValue;
+    uint16_t      fStart;
     uint16_t      fEnd;
     uint16_t      fIndex;
+    bool          fValid;
 
-    void init(uint16_t start = 0, uint16_t end = 0) {
+    void init() {
         fIntersection = fInset.fP0;
         fTValue = SK_ScalarMin;
+        fStart = 0;
+        fEnd = 0;
+        fIndex = 0;
+        fValid = true;
+    }
+
+    void init(uint16_t start, uint16_t end) {
+        fIntersection = fInset.fP0;
+        fTValue = SK_ScalarMin;
+        fStart = start;
         fEnd = end;
         fIndex = start;
+        fValid = true;
     }
 };
 
-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
@@ -353,118 +354,116 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize
     }
 
     // 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()) {
+    SkAutoSTMalloc<64, EdgeData> edgeData(inputPolygonSize);
+    for (int i = 0; i < inputPolygonSize; ++i) {
+        int j = (i + 1) % inputPolygonSize;
+        int k = (i + 2) % inputPolygonSize;
+        if (!inputPolygonVerts[i].isFinite()) {
             return false;
         }
         // check for convexity just to be sure
-        if (compute_side(inputPolygonVerts[prev], inputPolygonVerts[curr],
-                         inputPolygonVerts[next])*winding < 0) {
+        if (compute_side(inputPolygonVerts[i], inputPolygonVerts[j],
+                         inputPolygonVerts[k])*winding < 0) {
             return false;
         }
-        edgeData[curr].fPrev = &edgeData[prev];
-        edgeData[curr].fNext = &edgeData[next];
-        if (!SkOffsetSegment(inputPolygonVerts[curr], inputPolygonVerts[next],
-                             insetDistanceFunc(inputPolygonVerts[curr]),
-                             insetDistanceFunc(inputPolygonVerts[next]),
+        if (!SkOffsetSegment(inputPolygonVerts[i], inputPolygonVerts[j],
+                             insetDistanceFunc(inputPolygonVerts[i]),
+                             insetDistanceFunc(inputPolygonVerts[j]),
                              winding,
-                             &edgeData[curr].fInset.fP0, &edgeData[curr].fInset.fP1)) {
+                             &edgeData[i].fInset.fP0, &edgeData[i].fInset.fP1)) {
             return false;
         }
-        edgeData[curr].init();
+        edgeData[i].init();
     }
 
-    OffsetEdge* head = &edgeData[0];
-    OffsetEdge* currEdge = head;
-    OffsetEdge* prevEdge = currEdge->fPrev;
+    int prevIndex = inputPolygonSize - 1;
+    int currIndex = 0;
     int insetVertexCount = inputPolygonSize;
     int iterations = 0;
-    while (head && prevEdge != currEdge) {
+    while (prevIndex != currIndex) {
         ++iterations;
         // we should check each edge against each other edge at most once
         if (iterations > inputPolygonSize*inputPolygonSize) {
             return false;
         }
 
+        if (!edgeData[prevIndex].fValid) {
+            prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
+            continue;
+        }
+
         SkScalar s, t;
         SkPoint intersection;
-        if (compute_intersection(prevEdge->fInset, currEdge->fInset,
+        if (compute_intersection(edgeData[prevIndex].fInset, edgeData[currIndex].fInset,
                                  &intersection, &s, &t)) {
             // if new intersection is further back on previous inset from the prior intersection
-            if (s < prevEdge->fTValue) {
+            if (s < edgeData[prevIndex].fTValue) {
                 // no point in considering this one again
-                remove_node(prevEdge, &head);
+                edgeData[prevIndex].fValid = false;
                 --insetVertexCount;
                 // go back one segment
-                prevEdge = prevEdge->fPrev;
+                prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
             // we've already considered this intersection, we're done
-            } else if (currEdge->fTValue > SK_ScalarMin &&
+            } else if (edgeData[currIndex].fTValue > SK_ScalarMin &&
                        SkPointPriv::EqualsWithinTolerance(intersection,
-                                                          currEdge->fIntersection,
+                                                          edgeData[currIndex].fIntersection,
                                                           1.0e-6f)) {
                 break;
             } else {
                 // add intersection
-                currEdge->fIntersection = intersection;
-                currEdge->fTValue = t;
+                edgeData[currIndex].fIntersection = intersection;
+                edgeData[currIndex].fTValue = t;
 
                 // go to next segment
-                prevEdge = currEdge;
-                currEdge = currEdge->fNext;
+                prevIndex = currIndex;
+                currIndex = (currIndex + 1) % inputPolygonSize;
             }
         } else {
             // if prev to right side of curr
-            int side = winding*compute_side(currEdge->fInset.fP0,
-                                            currEdge->fInset.fP1,
-                                            prevEdge->fInset.fP1);
-            if (side < 0 && side == winding*compute_side(currEdge->fInset.fP0,
-                                                         currEdge->fInset.fP1,
-                                                         prevEdge->fInset.fP0)) {
+            int side = winding*compute_side(edgeData[currIndex].fInset.fP0,
+                                            edgeData[currIndex].fInset.fP1,
+                                            edgeData[prevIndex].fInset.fP1);
+            if (side < 0 && side == winding*compute_side(edgeData[currIndex].fInset.fP0,
+                                                         edgeData[currIndex].fInset.fP1,
+                                                         edgeData[prevIndex].fInset.fP0)) {
                 // no point in considering this one again
-                remove_node(prevEdge, &head);
+                edgeData[prevIndex].fValid = false;
                 --insetVertexCount;
                 // go back one segment
-                prevEdge = prevEdge->fPrev;
+                prevIndex = (prevIndex + inputPolygonSize - 1) % inputPolygonSize;
             } else {
                 // move to next segment
-                remove_node(currEdge, &head);
+                edgeData[currIndex].fValid = false;
                 --insetVertexCount;
-                currEdge = currEdge->fNext;
+                currIndex = (currIndex + 1) % inputPolygonSize;
             }
         }
     }
 
     // store all the valid intersections that aren't nearly coincident
     // TODO: look at the main algorithm and see if we can detect these better
+    static constexpr SkScalar kCleanupTolerance = 0.01f;
+
     insetPolygon->reset();
-    if (head) {
-        static constexpr SkScalar kCleanupTolerance = 0.01f;
-        if (insetVertexCount >= 0) {
-            insetPolygon->setReserve(insetVertexCount);
-        }
-        int currIndex = 0;
-        OffsetEdge* currEdge = head;
-        *insetPolygon->push() = currEdge->fIntersection;
-        currEdge = currEdge->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();
+    if (insetVertexCount >= 0) {
+        insetPolygon->setReserve(insetVertexCount);
+    }
+    currIndex = -1;
+    for (int i = 0; i < inputPolygonSize; ++i) {
+        if (edgeData[i].fValid && (currIndex == -1 ||
+            !SkPointPriv::EqualsWithinTolerance(edgeData[i].fIntersection,
+                                                (*insetPolygon)[currIndex],
+                                                kCleanupTolerance))) {
+            *insetPolygon->push() = edgeData[i].fIntersection;
+            currIndex++;
         }
     }
+    // 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());
 }
@@ -505,7 +504,6 @@ 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
@@ -519,14 +517,9 @@ enum VertexFlags {
     kNextLeft_VertexFlag = 0x2,
 };
 
-struct ActiveEdge {
-    ActiveEdge(const SkPoint& p0, const SkPoint& p1, int32_t index0, int32_t index1)
-        : fSegment({p0, p1})
-        , fIndex0(index0)
-        , fIndex1(index1) {}
-
+struct Edge {
     // returns true if "this" is above "that"
-    bool above(const ActiveEdge& that, SkScalar tolerance = SK_ScalarNearlyZero) const {
+    bool above(const Edge& that, SkScalar tolerance = SK_ScalarNearlyZero) {
         SkASSERT(this->fSegment.fP0.fX < that.fSegment.fP0.fX ||
                  SkScalarNearlyEqual(this->fSegment.fP0.fX, that.fSegment.fP0.fX, tolerance));
         // The idea here is that if the vector between the origins of the two segments (dv)
@@ -544,26 +537,10 @@ struct ActiveEdge {
         // 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".
         dv = that.fSegment.fP1 - this->fSegment.fP0;
-        if (dv.cross(u) > tolerance) {
-            return true;
-        }
-        // If the previous check fails, the two segments are nearly collinear
-        // If this segment starts to the left of that one,
-        // just need to check y-coord of 1st endpoint
-        if (this->fSegment.fP0.fX < that.fSegment.fP0.fX) {
-            return (this->fSegment.fP0.fY >= that.fSegment.fP0.fY);
-        } else if (this->fSegment.fP0.fY > that.fSegment.fP0.fY) {
-            return true;
-        }
-        // Otherwise the first endpoints are effectively the same, so check the other endpoint
-        if (this->fSegment.fP1.fX < that.fSegment.fP1.fX) {
-            return (this->fSegment.fP1.fY >= that.fSegment.fP1.fY);
-        } else {
-            return (this->fSegment.fP1.fY > that.fSegment.fP1.fY);
-        }
+        return (dv.cross(u) > tolerance);
     }
 
-    bool intersect(const ActiveEdge& that) const {
+    bool intersect(const Edge& that) const {
         SkPoint intersection;
         SkScalar s, t;
         // check first to see if these edges are neighbors in the polygon
@@ -574,73 +551,78 @@ struct ActiveEdge {
         return compute_intersection(this->fSegment, that.fSegment, &intersection, &s, &t);
     }
 
-    bool operator==(const ActiveEdge& that) const {
+    bool operator==(const Edge& that) const {
         return (this->fIndex0 == that.fIndex0 && this->fIndex1 == that.fIndex1);
     }
 
-    bool operator!=(const ActiveEdge& that) const {
+    bool operator!=(const Edge& that) const {
         return !operator==(that);
     }
 
-    bool operator<(const ActiveEdge& that) const {
-        // this may not be necessary
-        if (this->fIndex0 == that.fIndex0 && this->fIndex1 == that.fIndex1) {
-            return false;
-        }
-        if (this->fSegment.fP0.fX > that.fSegment.fP0.fX) {
-            return !that.above(*this);
-        }
-        return this->above(that);
-    }
-
     OffsetSegment fSegment;
     int32_t fIndex0;   // indices for previous and next vertex
     int32_t fIndex1;
 };
 
-class ActiveEdgeList {
+class EdgeList {
 public:
-    void reserve(int count) { }
+    void reserve(int count) { fEdges.reserve(count); }
 
-    bool insert(const SkPoint& p0, const SkPoint& p1, int32_t index0, int32_t index1) {
-        std::pair<Iterator, bool> result = fEdgeTree.emplace(p0, p1, index0, index1);
-        if (!result.second) {
-            return false;
+    bool insert(const Edge& newEdge) {
+        // linear search for now (expected case is very few active edges)
+        int insertIndex = 0;
+        while (insertIndex < fEdges.count() && fEdges[insertIndex].above(newEdge)) {
+            ++insertIndex;
         }
-
-        Iterator& curr = result.first;
-        if (curr != fEdgeTree.begin() && curr->intersect(*std::prev(curr))) {
+        // if we intersect with the existing edge above or below us
+        // then we know this polygon is not simple, so don't insert, just fail
+        if (insertIndex > 0 && newEdge.intersect(fEdges[insertIndex - 1])) {
             return false;
         }
-        Iterator next = std::next(curr);
-        if (next != fEdgeTree.end() && curr->intersect(*next)) {
+        if (insertIndex < fEdges.count() && newEdge.intersect(fEdges[insertIndex])) {
             return false;
         }
 
+        fEdges.push_back();
+        for (int i = fEdges.count() - 1; i > insertIndex; --i) {
+            fEdges[i] = fEdges[i - 1];
+        }
+        fEdges[insertIndex] = newEdge;
+
         return true;
     }
 
-    bool remove(const ActiveEdge& edge) {
-        auto element = fEdgeTree.find(edge);
-        // this better not happen
-        if (element == fEdgeTree.end()) {
-            return false;
+    bool remove(const Edge& edge) {
+        SkASSERT(fEdges.count() > 0);
+
+        // linear search for now (expected case is very few active edges)
+        int removeIndex = 0;
+        while (removeIndex < fEdges.count() && fEdges[removeIndex] != edge) {
+            ++removeIndex;
         }
-        if (element != fEdgeTree.begin() && element->intersect(*std::prev(element))) {
+        // we'd better find it or something is wrong
+        SkASSERT(removeIndex < fEdges.count());
+
+        // if we intersect with the edge above or below us
+        // then we know this polygon is not simple, so don't remove, just fail
+        if (removeIndex > 0 && fEdges[removeIndex].intersect(fEdges[removeIndex - 1])) {
             return false;
         }
-        Iterator next = std::next(element);
-        if (next != fEdgeTree.end() && element->intersect(*next)) {
-            return false;
+        if (removeIndex < fEdges.count() - 1) {
+            if (fEdges[removeIndex].intersect(fEdges[removeIndex + 1])) {
+                return false;
+            }
+            // copy over the old entry
+            memmove(&fEdges[removeIndex], &fEdges[removeIndex + 1],
+                    sizeof(Edge)*(fEdges.count() - removeIndex - 1));
         }
 
-        fEdgeTree.erase(element);
+        fEdges.pop_back();
         return true;
     }
 
 private:
-    std::set<ActiveEdge> fEdgeTree;
-    typedef std::set<ActiveEdge>::iterator Iterator;
+    SkSTArray<1, Edge> fEdges;
 };
 
 // Here we implement a sweep line algorithm to determine whether the provided points
@@ -654,7 +636,10 @@ bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
         return false;
     }
 
-    SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize);
+    SkTDPQueue <Vertex, Vertex::Left> vertexQueue;
+    EdgeList sweepLine;
+
+    sweepLine.reserve(polygonSize);
     for (int i = 0; i < polygonSize; ++i) {
         Vertex newVertex;
         if (!polygon[i].isFinite()) {
@@ -676,31 +661,31 @@ bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
 
     // pop each vertex from the queue and generate events depending on
     // where it lies relative to its neighboring edges
-    ActiveEdgeList sweepLine;
-    sweepLine.reserve(polygonSize);
     while (vertexQueue.count() > 0) {
         const Vertex& v = vertexQueue.peek();
 
         // check edge to previous vertex
         if (v.fFlags & kPrevLeft_VertexFlag) {
-            ActiveEdge edge(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex);
+            Edge edge{ { polygon[v.fPrevIndex], v.fPosition }, v.fPrevIndex, v.fIndex };
             if (!sweepLine.remove(edge)) {
                 break;
             }
         } else {
-            if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) {
+            Edge edge{ { v.fPosition, polygon[v.fPrevIndex] }, v.fIndex, v.fPrevIndex };
+            if (!sweepLine.insert(edge)) {
                 break;
             }
         }
 
         // check edge to next vertex
         if (v.fFlags & kNextLeft_VertexFlag) {
-            ActiveEdge edge(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex);
+            Edge edge{ { polygon[v.fNextIndex], v.fPosition }, v.fNextIndex, v.fIndex };
             if (!sweepLine.remove(edge)) {
                 break;
             }
         } else {
-            if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) {
+            Edge edge{ { v.fPosition, polygon[v.fNextIndex] }, v.fIndex, v.fNextIndex };
+            if (!sweepLine.insert(edge)) {
                 break;
             }
         }
@@ -713,15 +698,6 @@ bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
 
 ///////////////////////////////////////////////////////////////////////////////////////////
 
-// helper function for SkOffsetSimplePolygon
-static void setup_offset_edge(OffsetEdge* currEdge,
-                              const SkPoint& endpoint0, const SkPoint& endpoint1,
-                              int startIndex, int endIndex) {
-    currEdge->fInset.fP0 = endpoint0;
-    currEdge->fInset.fP1 = endpoint1;
-    currEdge->init(startIndex, endIndex);
-}
-
 bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
                            std::function<SkScalar(const SkPoint&)> offsetDistanceFunc,
                            SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) {
@@ -760,7 +736,7 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz
     }
 
     // build initial offset edge list
-    SkSTArray<64, OffsetEdge> edgeData(inputPolygonSize);
+    SkSTArray<64, EdgeData> edgeData(inputPolygonSize);
     int prevIndex = inputPolygonSize - 1;
     int currIndex = 0;
     int nextIndex = 1;
@@ -778,143 +754,126 @@ bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSiz
                                       &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);
+                EdgeData& edge = edgeData.push_back();
+                edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal;
+                edge.fInset.fP1 = inputPolygonVerts[currIndex] + currNormal;
+                edge.init(currIndex, currIndex);
                 prevNormal = currNormal;
-                ++currEdge;
             }
-            setup_offset_edge(currEdge,
-                              inputPolygonVerts[currIndex] + prevNormal,
-                              inputPolygonVerts[currIndex] + normal0[currIndex],
-                              currIndex, currIndex);
-            ++currEdge;
-
+            EdgeData& edge = edgeData.push_back();
+            edge.fInset.fP0 = inputPolygonVerts[currIndex] + prevNormal;
+            edge.fInset.fP1 = inputPolygonVerts[currIndex] + normal0[currIndex];
+            edge.init(currIndex, currIndex);
         }
 
         // Add the edge
-        auto edge = edgeData.push_back_n(1);
-        setup_offset_edge(edge,
-                          inputPolygonVerts[currIndex] + normal0[currIndex],
-                          inputPolygonVerts[nextIndex] + normal1[nextIndex],
-                          currIndex, nextIndex);
+        EdgeData& edge = edgeData.push_back();
+        edge.fInset.fP0 = inputPolygonVerts[currIndex] + normal0[currIndex];
+        edge.fInset.fP1 = inputPolygonVerts[nextIndex] + normal1[nextIndex];
+        edge.init(currIndex, nextIndex);
 
         prevIndex = currIndex;
         currIndex++;
         nextIndex = (nextIndex + 1) % inputPolygonSize;
     }
 
-    // build linked list
-    // we have to do this as a post-process step because we might have reallocated
-    // the array when adding fans for reflex verts
-    prevIndex = edgeData.count()-1;
-    for (int currIndex = 0; currIndex < edgeData.count(); prevIndex = currIndex, ++currIndex) {
-        int nextIndex = (currIndex + 1) % edgeData.count();
-        edgeData[currIndex].fPrev = &edgeData[prevIndex];
-        edgeData[currIndex].fNext = &edgeData[nextIndex];
-    }
-
-    // now clip edges
     int edgeDataSize = edgeData.count();
-    auto head = &edgeData[0];
-    auto currEdge = head;
-    auto prevEdge = currEdge->fPrev;
-    int offsetVertexCount = edgeDataSize;
+    prevIndex = edgeDataSize - 1;
+    currIndex = 0;
+    int insetVertexCount = edgeDataSize;
     int iterations = 0;
-    while (head && prevEdge != currEdge) {
+    while (prevIndex != currIndex) {
         ++iterations;
         // we should check each edge against each other edge at most once
         if (iterations > edgeDataSize*edgeDataSize) {
             return false;
         }
 
+        if (!edgeData[prevIndex].fValid) {
+            prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
+            continue;
+        }
+        if (!edgeData[currIndex].fValid) {
+            currIndex = (currIndex + 1) % edgeDataSize;
+            continue;
+        }
+
         SkScalar s, t;
         SkPoint intersection;
-        if (compute_intersection(prevEdge->fInset, currEdge->fInset,
+        if (compute_intersection(edgeData[prevIndex].fInset, edgeData[currIndex].fInset,
                                  &intersection, &s, &t)) {
             // if new intersection is further back on previous inset from the prior intersection
-            if (s < prevEdge->fTValue) {
+            if (s < edgeData[prevIndex].fTValue) {
                 // no point in considering this one again
-                remove_node(prevEdge, &head);
-                --offsetVertexCount;
+                edgeData[prevIndex].fValid = false;
+                --insetVertexCount;
                 // go back one segment
-                prevEdge = prevEdge->fPrev;
+                prevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
                 // we've already considered this intersection, we're done
-            } else if (currEdge->fTValue > SK_ScalarMin &&
+            } else if (edgeData[currIndex].fTValue > SK_ScalarMin &&
                        SkPointPriv::EqualsWithinTolerance(intersection,
-                                                          currEdge->fIntersection,
+                                                          edgeData[currIndex].fIntersection,
                                                           1.0e-6f)) {
                 break;
             } else {
                 // add intersection
-                currEdge->fIntersection = intersection;
-                currEdge->fTValue = t;
-                currEdge->fIndex = prevEdge->fEnd;
+                edgeData[currIndex].fIntersection = intersection;
+                edgeData[currIndex].fTValue = t;
+                edgeData[currIndex].fIndex = edgeData[prevIndex].fEnd;
 
                 // go to next segment
-                prevEdge = currEdge;
-                currEdge = currEdge->fNext;
+                prevIndex = currIndex;
+                currIndex = (currIndex + 1) % edgeDataSize;
             }
         } 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 = compute_crossing_distance(currEdge->fInset,
-                                                       prevPrevEdge->fInset);
-            SkScalar dist1 = compute_crossing_distance(prevEdge->fInset,
-                                                       currNextEdge->fInset);
+            SkScalar prevPrevIndex = (prevIndex + edgeDataSize - 1) % edgeDataSize;
+            SkScalar currNextIndex = (currIndex + 1) % edgeDataSize;
+            SkScalar dist0 = compute_crossing_distance(edgeData[currIndex].fInset,
+                                                       edgeData[prevPrevIndex].fInset);
+            SkScalar dist1 = compute_crossing_distance(edgeData[prevIndex].fInset,
+                                                       edgeData[currNextIndex].fInset);
             if (dist0 < dist1) {
-                remove_node(prevEdge, &head);
-                prevEdge = prevPrevEdge;
+                edgeData[prevIndex].fValid = false;
+                prevIndex = prevPrevIndex;
             } else {
-                remove_node(currEdge, &head);
-                currEdge = currNextEdge;
+                edgeData[currIndex].fValid = false;
+                currIndex = currNextIndex;
             }
-            --offsetVertexCount;
+            --insetVertexCount;
         }
     }
 
     // store all the valid intersections that aren't nearly coincident
     // TODO: look at the main algorithm and see if we can detect these better
+    static constexpr SkScalar kCleanupTolerance = 0.01f;
+
     offsetPolygon->reset();
-    if (head) {
-        static constexpr SkScalar kCleanupTolerance = 0.01f;
-        if (offsetVertexCount >= 0) {
-            offsetPolygon->setReserve(offsetVertexCount);
-        }
-        int currIndex = 0;
-        OffsetEdge* currEdge = head;
-        *offsetPolygon->push() = currEdge->fIntersection;
-        if (polygonIndices) {
-            *polygonIndices->push() = currEdge->fIndex;
-        }
-        currEdge = currEdge->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();
+    offsetPolygon->setReserve(insetVertexCount);
+    currIndex = -1;
+    for (int i = 0; i < edgeData.count(); ++i) {
+        if (edgeData[i].fValid && (currIndex == -1 ||
+                                   !SkPointPriv::EqualsWithinTolerance(edgeData[i].fIntersection,
+                                                                       (*offsetPolygon)[currIndex],
+                                                                       kCleanupTolerance))) {
+            *offsetPolygon->push() = edgeData[i].fIntersection;
             if (polygonIndices) {
-                polygonIndices->pop();
+                *polygonIndices->push() = edgeData[i].fIndex;
             }
+            currIndex++;
+        }
+    }
+    // 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();
         }
     }
 
diff --git a/tests/InsetConvexPolyTest.cpp b/tests/InsetConvexPolyTest.cpp
index aaaf591620..facabb76fa 100644
--- a/tests/InsetConvexPolyTest.cpp
+++ b/tests/InsetConvexPolyTest.cpp
@@ -65,7 +65,7 @@ DEF_TEST(InsetConvexPoly, reporter) {
     // past full inset
     result = SkInsetConvexPolygon(rrectPoly.begin(), rrectPoly.count(), 75, &insetPoly);
     REPORTER_ASSERT(reporter, !result);
-    REPORTER_ASSERT(reporter, insetPoly.count() == 1);
+    REPORTER_ASSERT(reporter, insetPoly.count() == 0);
 
     // troublesome case
     SkTDArray<SkPoint> clippedRRectPoly;