From 840ffdf17f7c985f271f080b602bc2426223dcb8 Mon Sep 17 00:00:00 2001 From: Sven Göthel Date: Wed, 14 Feb 2024 20:50:34 +0100 Subject: VectorUtil: Add experimental isSelfIntersecting1() with O(n*n) complexity This doesn't bring reliable results for Graph and also is pretty expensive. --- src/jogl/classes/com/jogamp/math/VectorUtil.java | 69 ++++++++++++++++++++++++ 1 file changed, 69 insertions(+) (limited to 'src/jogl/classes/com/jogamp/math/VectorUtil.java') 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 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; + } } -- cgit v1.2.3