experimental alternative isconvex
Bug: skia:
Change-Id: I55175a95d37aad9a656cd211fc6c7238bdb7d674
Reviewed-on: https://skia-review.googlesource.com/c/173361
Commit-Queue: Mike Reed <reed@google.com>
Reviewed-by: Mike Reed <reed@google.com>
diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp
index 7ec4e46..cea76fc 100644
--- a/src/utils/SkPolyUtils.cpp
+++ b/src/utils/SkPolyUtils.cpp
@@ -1691,3 +1691,116 @@
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;
+}
+