SkPolyUtils.h File Reference

#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include <cstdint>

Go to the source code of this file.

Functions
bool	SkInsetConvexPolygon (const SkPoint *inputPolygonVerts, int inputPolygonSize, SkScalar inset, SkTDArray< SkPoint > *insetPolygon)
bool	SkOffsetSimplePolygon (const SkPoint *inputPolygonVerts, int inputPolygonSize, const SkRect &bounds, SkScalar offset, SkTDArray< SkPoint > *offsetPolygon, SkTDArray< int > *polygonIndices=nullptr)
bool	SkComputeRadialSteps (const SkVector &offset0, const SkVector &offset1, SkScalar offset, SkScalar *rotSin, SkScalar *rotCos, int *n)
int	SkGetPolygonWinding (const SkPoint *polygonVerts, int polygonSize)
bool	SkIsConvexPolygon (const SkPoint *polygonVerts, int polygonSize)
bool	SkIsSimplePolygon (const SkPoint *polygonVerts, int polygonSize)
bool	SkTriangulateSimplePolygon (const SkPoint *polygonVerts, uint16_t *indexMap, int polygonSize, SkTDArray< uint16_t > *triangleIndices)

Function Documentation

SkComputeRadialSteps()

bool SkComputeRadialSteps	(	const SkVector &	offset0,
		const SkVector &	offset1,
		SkScalar	offset,
		SkScalar *	rotSin,
		SkScalar *	rotCos,
		int *	n
	)

Compute the number of points needed for a circular join when offsetting a vertex. The lengths of offset0 and offset1 don't have to equal |offset| – only the direction matters. The segment lengths will be approximately four pixels.

Parameters

offset0	Starting offset vector direction.
offset1	Ending offset vector direction.
offset	Offset value (can be negative).
rotSin	Sine of rotation delta per step.
rotCos	Cosine of rotation delta per step.
n	Number of steps to fill out the arc.

Returns

true for success, false otherwise

Definition at line 490 of file SkPolyUtils.cpp.

                                                                      {
    const SkScalar kRecipPixelsPerArcSegment = 0.25f;
 
    SkScalar rCos = v1.dot(v2);
    if (!SkIsFinite(rCos)) {
        return false;
    }
    SkScalar rSin = v1.cross(v2);
    if (!SkIsFinite(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);
    // Our offset may be so large that we end up with a tiny dTheta, in which case we
    // lose precision when computing rotSin and rotCos.
    if (steps > 0 && (*rotSin == 0 || *rotCos == 1)) {
        return false;
    }
    *n = steps;
    return true;
}

SkGetPolygonWinding()

int SkGetPolygonWinding	(	const SkPoint *	polygonVerts,
		int	polygonSize
	)

Determine winding direction for a polygon. The input polygon must be simple or the result will be meaningless.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
polygonSize	Number of vertices in the polygon.

Returns

1 for cw, -1 for ccw, and 0 if zero signed area (either degenerate or self-intersecting). The y-axis is assumed to be pointing down.

Definition at line 57 of file SkPolyUtils.cpp.

                                                                      {
    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;
}

SkInsetConvexPolygon()

bool SkInsetConvexPolygon	(	const SkPoint *	inputPolygonVerts,
		int	inputPolygonSize,
		SkScalar	inset,
		SkTDArray< SkPoint > *	insetPolygon
	)

Generates a polygon that is inset a constant from the boundary of a given convex polygon. The input polygon is expected to have values clamped to the nearest 1/16th.

Parameters

inputPolygonVerts	Array of points representing the vertices of the original polygon. It should be convex and have no coincident points.
inputPolygonSize	Number of vertices in the original polygon.
inset	How far we wish to inset the polygon. This should be a positive value.
insetPolygon	The resulting inset polygon, if any.

Returns

true if an inset polygon exists, false otherwise.

Definition at line 338 of file SkPolyUtils.cpp.

                                                                            {
    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 || !SkIsFinite(inset)) {
        return false;
    }
 
    // insetting close to zero just returns the original poly
    if (inset <= SK_ScalarNearlyZero) {
        for (int i = 0; i < inputPolygonSize; ++i) {
            *insetPolygon->append() = inputPolygonVerts[i];
        }
        return true;
    }
 
    // get winding direction
    int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
    if (0 == winding) {
        return false;
    }
 
    // set up
    AutoSTMalloc<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->reserve(insetVertexCount);
    }
    int currIndex = 0;
    *insetPolygon->append() = head->fIntersection;
    currEdge = head->fNext;
    while (currEdge != head) {
        if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
                                                (*insetPolygon)[currIndex],
                                                kCleanupTolerance)) {
            *insetPolygon->append() = 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_back();
    }
 
    return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->size());
}

SkIsConvexPolygon()

bool SkIsConvexPolygon	(	const SkPoint *	polygonVerts,
		int	polygonSize
	)

Determine whether a polygon is convex or not.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
polygonSize	Number of vertices in the polygon.

Returns

true if the polygon is convex, false otherwise.

Definition at line 196 of file SkPolyUtils.cpp.

                                                                     {
    if (polygonSize < 3) {
        return false;
    }
 
    SkScalar lastPerpDot = 0;
    int xSignChangeCount = 0;
    int ySignChangeCount = 0;
 
    int prevIndex = polygonSize - 1;
    int currIndex = 0;
    int nextIndex = 1;
    SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex];
    SkScalar lastVx = v0.fX;
    SkScalar lastVy = v0.fY;
    SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
    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;
        }
 
        // Check that the signs of the edge vectors don't change more than twice per coordinate
        if (lastVx*v1.fX < 0) {
            xSignChangeCount++;
        }
        if (lastVy*v1.fY < 0) {
            ySignChangeCount++;
        }
        if (xSignChangeCount > 2 || ySignChangeCount > 2) {
            return false;
        }
        prevIndex = currIndex;
        currIndex = nextIndex;
        nextIndex = (currIndex + 1) % polygonSize;
        if (v1.fX != 0) {
            lastVx = v1.fX;
        }
        if (v1.fY != 0) {
            lastVy = v1.fY;
        }
        v0 = v1;
        v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
    }
 
    return true;
}

SkIsSimplePolygon()

bool SkIsSimplePolygon	(	const SkPoint *	polygonVerts,
		int	polygonSize
	)

Determine whether a polygon is simple (i.e., not self-intersecting) or not. The input polygon must have no coincident vertices or the test will fail. The polygon is also expected to have values clamped to the nearest 1/16th.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
polygonSize	Number of vertices in the polygon.

Returns

true if the polygon is simple, false otherwise.

Definition at line 1092 of file SkPolyUtils.cpp.

                                                                {
    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;
        // The two edges adjacent to this vertex are the same, so polygon is not simple
        if (polygon[newVertex.fPrevIndex] == polygon[newVertex.fNextIndex]) {
            return false;
        }
        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);
}

SkOffsetSimplePolygon()

bool SkOffsetSimplePolygon	(	const SkPoint *	inputPolygonVerts,
		int	inputPolygonSize,
		const SkRect &	bounds,
		SkScalar	offset,
		SkTDArray< SkPoint > *	offsetPolygon,
		SkTDArray< int > *	polygonIndices = nullptr
	)

Generates a simple polygon (if possible) that is offset a constant distance from the boundary of a given simple polygon. The input polygon must be simple, have no coincident vertices or collinear edges, and have values clamped to the nearest 1/16th.

Parameters

inputPolygonVerts	Array of points representing the vertices of the original polygon.
inputPolygonSize	Number of vertices in the original polygon.
bounds	Bounding rectangle for the original polygon.
offset	How far we wish to offset the polygon. Positive values indicate insetting, negative values outsetting.
offsetPolgon	The resulting offset polygon, if any.
polygonIndices	The indices of the original polygon that map to the new one.

Returns

true if an offset simple polygon exists, false otherwise.

Definition at line 1195 of file SkPolyUtils.cpp.

                                                                                              {
    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 (!SkIsFinite(offset)) {
        return false;
    }
 
    // can't inset more than the half bounds of the polygon
    if (offset > std::min(SkTAbs(SkRectPriv::HalfWidth(bounds)),
                          SkTAbs(SkRectPriv::HalfHeight(bounds)))) {
        return false;
    }
 
    // offsetting close to zero just returns the original poly
    if (SkScalarNearlyZero(offset)) {
        for (int i = 0; i < inputPolygonSize; ++i) {
            *offsetPolygon->append() = inputPolygonVerts[i];
            if (polygonIndices) {
                *polygonIndices->append() = i;
            }
        }
        return true;
    }
 
    // get winding direction
    int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
    if (0 == winding) {
        return false;
    }
 
    // build normals
    AutoSTMalloc<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 += std::max(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 += std::max(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
    STArray<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(std::max(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.size() == (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->reserve(offsetVertexCount);
    int currIndex = 0;
    *offsetPolygon->append() = head->fIntersection;
    if (polygonIndices) {
        *polygonIndices->append() = head->fIndex;
    }
    currEdge = head->fNext;
    while (currEdge != head) {
        if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
                                                (*offsetPolygon)[currIndex],
                                                kCleanupTolerance)) {
            *offsetPolygon->append() = currEdge->fIntersection;
            if (polygonIndices) {
                *polygonIndices->append() = 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_back();
        if (polygonIndices) {
            polygonIndices->pop_back();
        }
    }
 
    // check winding of offset polygon (it should be same as the original polygon)
    SkScalar offsetWinding = SkGetPolygonWinding(offsetPolygon->begin(), offsetPolygon->size());
 
    return (winding*offsetWinding > 0 &&
            SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->size()));
}

SkTriangulateSimplePolygon()

bool SkTriangulateSimplePolygon	(	const SkPoint *	polygonVerts,
		uint16_t *	indexMap,
		int	polygonSize,
		SkTDArray< uint16_t > *	triangleIndices
	)

Compute indices to triangulate the given polygon. The input polygon must be simple (i.e. it is not self-intersecting) and have no coincident vertices or collinear edges.

Parameters

polygonVerts	Array of points representing the vertices of the polygon.
indexMap	Mapping from index in the given array to the final index in the triangulation.
polygonSize	Number of vertices in the polygon.
triangleIndices	Indices of the resulting triangulation.

Returns

true if successful, false otherwise.

Definition at line 1632 of file SkPolyUtils.cpp.

                                                                      {
    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
    AutoSTArray<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;
 
        triangulationVertices[currIndex] = 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->reserve(triangleIndices->size() + 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->append() = indexMap[vertex->fIndex];
    }
 
    return true;
}