Geometry2D.is_polygon_clockwise always returns false for some triangles.

[km19809]

Tested versions

• Reproducible in: 4.2.1.stable, 4.2.2.stable

System information

Godot v4.2.1.stable - Windows 10.0.19045 - Vulkan (Forward+) - dedicated NVIDIA GeForce GTX 1080 (NVIDIA; 31.0.15.4633) - Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz (8 Threads)

Issue description

Description

I am using Geometry2d.is_polygon_clockwise to detect a clockwise polygon.

Because my polygons are simple (i.e. they are not self-intersecting), they should be clockwise or counterclockwise.

However, even in a triangle case, Geometry2d.is_polygon_clockwise returns false in any polygon order.
In other words, the function says my triangle is always counterclockwise, even if I reverse its order.

I met this issue only for specific polygons.
But, I was unable to figure out the exact reason.
So please check my minimum reproducible script.

Expected behavior

The return value should change if the array is reversed.

Before reverse():
is clockwise (Geometry2D): false
After reverse():
is clockwise (Geometry2D but in GDScript): true

Additional note

This is a different issue from #49716.
The function returns false in any order of vertices, not the opposite of the expected.

Steps to reproduce

Here is my minimum reproducible code.

extends Node2D


# Called when the node enters the scene tree for the first time.
func _ready():
	var polygon = PackedVector2Array([Vector2(652.0707, 106.6666), 
	Vector2(612.0706, 146.6666), 
	Vector2(609.7679, 148.9693)])
	
        # If you use the polygon below,  
        #`is_polygon_clockwise` will work as expected.
        # var polygon = PackedVector2Array([Vector2(705.4008, 93.46715), Vector2(645.4006, 153.4671), Vector2(642.697, 156.1708)])

        # These functions should return the same results.
	print("is clockwise (Geometry2D): ", Geometry2D.is_polygon_clockwise(polygon))
	print("is clockwise (Determinant): ", compute_area_determinant(polygon) < 0)
	print("is clockwise (Geometry2D but in GDScript): ", compute_area_godot(polygon)>0)
	polygon.reverse()	
	print("is clockwise (Geometry2D): ", Geometry2D.is_polygon_clockwise(polygon))
	print("is clockwise (Determinant): ", compute_area_determinant(polygon) < 0)
	print("is clockwise (Geometry2D but in GDScript): ", compute_area_godot(polygon)>0)
	
func compute_area_determinant(polygon:PackedVector2Array)->float:
        # This function is based on the shoelace formula
        # Source: https://en.wikipedia.org/wiki/Shoelace_formula
        # Note that the sign of the return value 
        # is the opposite of Godot's approach.
	var new_double_area = 0.0
	for i in len(polygon):
		var current = polygon[i]
		var next = polygon[(i+1)%len(polygon)]
		new_double_area += current.x * next.y - next.x * current.y
	return new_double_area / 2 

func compute_area_godot(polygon:PackedVector2Array)->float:
       # This is a GDScript port of Godot engine's C++ implementation.
       # Source:  https://github.com/godotengine/godot/blob/b09f793f564a6c95dc76acc654b390e68441bd01/core/math/geometry_2d.h#L327
	var new_double_area = 0.0
	for i in len(polygon):
		var current = polygon[i]
		var next = polygon[(i+1)%len(polygon)]
		new_double_area +=  (next.x - current.x) * (next.y + current.y)
	return new_double_area / 2 

1. Copy my code above.
2. Attach the script to any new node on the scene tree.
3. Press start to see the results.

My results are:

is clockwise (Geometry2D): false
is clockwise (Determinant): false
is clockwise (Geometry2D but in GDScript): false
is clockwise (Geometry2D): false
is clockwise (Determinant): true
is clockwise (Geometry2D but in GDScript): true

Minimal reproduction project (MRP)

MRP.zip

[lawnjelly]

This also occurs in 3.x.

I debugged it, and it looks like the triangle is very near zero area (i.e. colinear points), so the results are unreliable and liable to float error. sum comes out to zero in both cases in the c++.

The differences between c++ and gdscript are likely between 32 bit / 64 bit math (64 bit in gdscript versus 32 bit in the c++).

Indeed if you print out the areas returned by your formula you get:

area determinant: 0.000531
area godot: -0.000531

(before flipping, your methods seem to return opposite sign)

The results not being opposite is understandable if the triangle is degenerate - neither clockwise or anti-clockwise.

As to whether this is actionable, it would be nice if routine like this would return clockwise, anti-clockwise or failure. For failure it looks like it might be able to just test for 0 sum.

However the binding system for functions makes it difficult to return multiple values. This is often a pain. So you'd currently need to run another test to calculate area before calling is_polygon_clockwise() if your input might contain degenerate and this would be a problem.

• An alternative would be to return a signed area and have the user perform the zero / more than / less than test.
• Or to return an enum, but that would be compat breaking.
• You could even call is_polygon_clockwise() twice after flipping, and if the result was the same, then maybe by definition the polygon is degenerate. Although this is a little ugly. 😀

I don't actually know offhand whether any of the triangle area functions are bound...

[km19809]

Thank you for the investigation.
I missed that its area is nearly zero.
I may ignore the triangle if the area of it is smaller than a certain threshold.

Also, I prefer this option:

An alternative would be to return a signed area and have the user perform the zero / more than / less than test.

Because is_polygon_clockwise() calculates the area already, I think there can also be a function like get_polygon_area().
The function will also be beneficial for certain games (Qix-like or cleaning?).