Add a function to Geometry to check if a polygon is self-intersecting (ie. simple/non-simple)

[Av3r3tt]

Describe the project you are working on:
When working with Polygon2Ds and polygons in general as used by the Geometry singleton, ie. as PoolVector2Arrays, there does not seem to be a function to check whether a polygon is valid for drawing (i.e. "simple" in geometrical terms -- a polygon that does not self-intersect). Godot quietly fails to render it if that is the case. This feature proposal follows the discussion mentioned in
https://godotforums.org/discussion/comment/41222#Comment_41222

Describe the problem or limitation you are having in your project:
I'm currently working on creating simple polygon primitives whose edges are subsequently turned into "noise", to give them squiggly edges, such as is often the case for land masses or islands in maps, or for "fuzzy" edges of medieval scroll paper, by inserting additional points into the polygon. Even the best noise algorithms might accidentally create overlapping edges, turning polygons accidentally from simple ones into non-simple (self intersecting) ones. As hinted above, Godot does not give feedback if a polygon is "illegal" (ie non-simple) for drawing, and just fails in the process. A simple code function to check whether a polygon is valid would be needed.

Describe the feature / enhancement and how it helps to overcome the problem or limitation:
I propose to add a function to Geometry which could yield a boolean to check whether a polygon is "simple" or not. A non-simple polygon cannot be rendered, and a simple hint in the documentation, together with this function, would alleviate the problem as it would allow developers to catch such polygons before attempting to use them.

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams:
The Geometry should take this function:
func polygonIsSimple(polygon: PoolVector2Array/PackedVector2Array) -> bool
so that developers can write:

if !Geometry.polygonIsSimple(myPolygon):
[repair polygon]
...
[render polygon]

Actual algorithms and code for this are freely available in C++. For this function, usage of the Shamos-Hoey Algorithm (using a SweepLine algorithm implementation) would be ideal.

Code for an implementation in C++ can be found here:
http://geomalgorithms.com/a09-_avl_code.html

If this enhancement will not be used often, can it be worked around with a few lines of script?:
While there might be, I have not found one that works well in GDscript.A brute force solution (of o(n2) computing time) could be achieved in GDScript by checking all polygon segments of a polygon p against all others; or by implementing a sweep line algorithm in GDscript; but these are presumably slow options, especially if the code wishes to deal with dozens or hundreds of such polygons.

Is there a reason why this should be core and not an add-on in the asset library?:
As a fundamental geometrical function, it would be logical to add in the Geometry singleton, as similar functions for polygons like clipping can be found there, too.

[Av3r3tt]

Here is a O(n2) function in GDscript: as soon as a polygon has 200 polygons, it needs to do ~40,000 checks and gets incredibly slow:

func polygonIsSimple(polgon: PoolVector2Array) -> bool:
	var s = polgon.size() - 1
	for i in range(0,s):
		var p1: Vector2 = polgon[i]
		var p2: Vector2 = polgon[i+1 % s]
		for j in range(0,s):
			var p1a: Vector2 = polgon[j]
			var p2a: Vector2 = polgon[j+1 % s]
			var intersect = Geometry.segment_intersects_segment_2d(p1,p2,p1a,p2a)
			if intersect != null: 
				return false
	return true

It is obvious we need a Geometry-function in C++ with smart (sweep line) algorithm, using a binary tree. The Shamos-Hoey algorithm implementation mentioned above does the job with only O(n) space and runs in O(n log n) time.

[Xrayez]

See godotengine/godot#40911 with suggested workaround. Geometry.merge_polygons_2d can also be used to simplify polygons implicitly. I'm not sure whether that's a case of "better do than check" performance-wise. It won't always work because strictly_simple is inaccessible with current API. See also my proposal for implementing this in #913.

But I think the rendering issue could also be solved by addressing godotengine/godot#16423 (use monotone triangulation over ear-clipping). I haven't worked on this because I've already come up with some in-house solutions, but I could likely work on this from the blessing of core devs if deemed necessary.

[Av3r3tt]

@Xrayez : Thank you for this Andrii -- I fully support #913.

[DavidJVitale]

I know this is a dead topic but it still shows up high on google searches. While we wait for an eventual optimized self-intersecting algorithm, here is a modified C# brute-force algorithm slightly improved from the above in this thread. O(n^2)

public static class GeometryAlgos{
    public static Boolean PolygonIsSelfIntersecting(Vector2[] polygon){
        var s = polygon.Length-1;
        for(int i=0;i<s;i++){
            var p1 = polygon[i];
            var p2 = polygon[i+1];
            for(int j=0; j<s;j++){
                var p1a = polygon[j];
                var p2a = polygon[j+1];
                if((new HashSet<Vector2>(){p1,p2,p1a,p2a}).Count != 4){
                    // don't detect intersection when any two points are the same
                    continue;
                }
                var intersect = Geometry.SegmentIntersectsSegment2d(p1,p2,p1a,p2a);
                if(intersect != null){
                    return true;
                }
            }
        }
        return false;
    }
}

I needed a simple way to detect if a polygon was self intersecting for an in-game level editor. I don't want users to place invalid ploygons, so I use the above function to detect self-intersection. If so, modulate red and don't allow placement. If not, normal modulate. I'd love an O(n log n) Shamos-Hoey Algorithm but this is good enough for now!

[EntranceJew]

does math work yet

[ArcMember]

Checked this topic for a solution, but did it this way after all:

// Check if polygon is simple
int[] result = Geometry2D.TriangulatePolygon(points);
return result.Length > 0;

TriangulatePolygon function does not triangulate self-intersecting polygons to my knowledge.

[AThousandShips]

The triangulate method isn't guaranteed, it can triangulate invalid geometry by accident and fail to triangulate valid input, as far as I've seen

[RobertBColton]

Going further, I think a bigger issue is that transitively the logic is actually broke.
godotengine/godot#99745 (comment)

merge_polygons will actually report success (size() = 1) even if both of its inputs could be triangulated and rendered instead of simply returning the failure case (should return the zero-area holes).

[RobertBColton]

@Av3r3tt and @Xrayez if Shamos-Hoey or Bentley–Ottmann is added to the engine, I would like to see it exposed more generally.

Currently I am building a self-intersecting road editor on top of AStar2D graph. One of the problems I am trying to solve is to check if a line I am drawing will intersect the AStar2D network and where so I can splice and create an intersection.

It would be super helpful to have one of those line sweeping algorithms exposed on the AStar2D classes too.