Geometry2D Union generates invalid Polygon2D/Self-intersection Transitivity

[RobertBColton]

Tested versions

Reproducible in 4.3 and back in 3.x

System information

Godot v4.3.stable - Windows 10.0.22631 - GLES3 (Compatibility) - NVIDIA GeForce RTX 4050 Laptop GPU (NVIDIA; 32.0.15.6070) - Intel(R) Core(TM) Ultra 7 155H (22 Threads)

Issue description

So I've been experimenting with Polygon2D in the editor and managed to create some shapes that will disappear.
I'm not quite sure what the issue is since the polygon does not intersect itself, but if we move any of the points then it will reappear.

Steps to reproduce

Copy these points into a Polygon2D and notice it doesn't render:

polygon = PackedVector2Array(450, 300, 550, 300, 550, 450, 600, 450, 600, 300, 550, 300, 550, 250, 700.68, 249, 700, 450, 700.68, 506, 449.68, 500)

Minimal reproduction project (MRP)

I gave the points to the Polygon2D in reproduce steps.

[smix8]

Polygon2D is a single outline with no holes that gets converted to a "real" polygon afterward.
That outline is invalid because vertex1 and vertex5 overlap / cause self intersection / hole creation.

[RobertBColton]

@smix8 Here, I can provide a mini unit test with the input shape data I made as well to explain what's wrong with merge_polygons. Plops this in a game somewhere and call it.

The test verifies that the two input shapes are non-intersecting and can be triangulated independently. Geometry2D is able to successfully merge them together (size() = 1). It fails when trying to triangulate the merged result of them though.

I get this message when I run it:

FAILURE: merged poly can not be triangulated

The result I think users expect is:

FAILURE: cant merge polys due to holes

func _my_unit_test() -> void:
	var first_poly: PackedVector2Array = [
		Vector2(650, 350), Vector2(800, 350),  Vector2(800, 300),
		Vector2(900, 300), Vector2(900, 400),  Vector2(950, 400),
		Vector2(950, 450), Vector2(900, 450),  Vector2(900, 550),
		Vector2(850, 550), Vector2(850, 600),  Vector2(950, 600),
		Vector2(950, 450), Vector2(1000, 450), Vector2(1000, 650),
		Vector2(550, 650), Vector2(550, 600),  Vector2(600, 600),
		Vector2(600, 500), Vector2(650, 500),  Vector2(650, 550),
		Vector2(800, 550), Vector2(800, 500),  Vector2(850, 500),
		Vector2(850, 450), Vector2(800, 450),  Vector2(800, 400),
		Vector2(850, 400), Vector2(850, 350),  Vector2(800, 350),
		Vector2(800, 400), Vector2(750, 400),  Vector2(750, 450),
		Vector2(700, 450), Vector2(700, 500),  Vector2(650, 500),
		Vector2(650, 400), Vector2(550, 400),  Vector2(550, 300),
		Vector2(650, 300)
	]
	var second_poly: PackedVector2Array = [
		Vector2(900, 300), Vector2(950, 300), Vector2(950, 350), Vector2(900, 350)
	]

	var indices1 = Geometry2D.triangulate_polygon(first_poly)
	if indices1.is_empty():
		print("FAILURE: first poly can not be triangulated")
		return
	var indices2 = Geometry2D.triangulate_polygon(second_poly)
	if indices2.is_empty():
		print("FAILURE: second poly can not be triangulated")
		return
		
	var merged_poly = Geometry2D.merge_polygons(first_poly, second_poly)
	if merged_poly.size() != 1:
		print("FAILURE: cant merge polys due to holes")
		return
	var indices3 = Geometry2D.triangulate_polygon(merged_poly)
	if indices3.is_empty():
		print("FAILURE: merged poly can not be triangulated")
		return
	var indices4 = Geometry2D.triangulate_delaunay(merged_poly)
	if indices4.is_empty():
		print("FAILURE: merged poly can not be delaunay triangulated")
		return
	
	print("SUCCESS able to triangulate merged polys")

Here is a visualization of the two shapes being merged: