VectorUtil: Add experimental isSelfIntersecting1() with O(n*n) complexity

This doesn't bring reliable results for Graph and also is pretty expensive.

1 files changed, 69 insertions, 0 deletions

diff --git a/src/jogl/classes/com/jogamp/math/VectorUtil.java b/src/jogl/classes/com/jogamp/math/VectorUtil.java
index 804ed3594..b18af39e8 100644
--- a/src/jogl/classes/com/jogamp/math/VectorUtil.java
+++ b/src/jogl/classes/com/jogamp/math/VectorUtil.java
@@ -1333,4 +1333,73 @@ public final class VectorUtil {
         //  This is a convex polygon.
         return true;
     }
+
+    /**
+     * Returns whether the given {@code polyline} is self-intersecting shape (crossing over) with O(n*n) complexity.
+     */
+    public static boolean isSelfIntersecting1(final List<Vertex> polyline) {
+        final int polysz = polyline.size();
+        if (polysz < 4) {
+            return false;
+        }
+        final boolean keepOffCurve = true;
+
+        for (int i = 0; i < polysz-1; i++) {
+            Vertex p0, p1;
+            if( keepOffCurve ) {
+                p0 = polyline.get(i);
+                p1 = polyline.get(i+1);
+            } else {
+                do {
+                    p0 = polyline.get(i++);
+                } while( !p0.isOnCurve() && i < polysz-1 );
+                if( i >= polysz-1 ) {
+                    return false;
+                }
+                {
+                    int i2 = i;
+                    do {
+                        p1 = polyline.get(i2++);
+                    } while( !p1.isOnCurve() && i2 < polysz );
+                    i = i2 - 1;
+                    if( i2 >= polysz ) {
+                        return false;
+                    }
+                }
+            }
+            for (int j = i+2; j < polysz; j++) {
+                // Eliminate combinations already checked or not valid
+                if ((i == 0) && ( j == (polysz-1))) {
+                    continue;
+                }
+                Vertex q0, q1;
+                if( keepOffCurve ) {
+                    q0 = polyline.get(j);
+                    q1 = polyline.get((j+1)%polysz);
+                } else {
+                    do {
+                        q0 = polyline.get(j++);
+                    } while( !q0.isOnCurve() && j < polysz );
+                    if( i >= polysz-1 ) {
+                        return false;
+                    }
+                    {
+                        int j2 = j;
+                        do {
+                            q1 = polyline.get(j2++%polysz);
+                        } while( !q1.isOnCurve() && j2 < polysz+1 );
+                        j = j2 - 1;
+                        if( j2 >= polysz+1 ) {
+                            return false;
+                        }
+                    }
+                }
+
+                if( VectorUtil.testSeg2SegIntersection(p0, p1, q0, q1, 0, false) ) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
 }