Geometry.is_point_in_polygon() fails when points are clockwise

[SteveSmith16384]

Godot version

3.5.1

System information

Linux Mint

Issue description

Geometry.is_point_in_polygon() returns an incorrect result in the example below where the polygon points are clockwise, but works if I invert the points.

Steps to reproduce

I'm running the following code:-

var polygon : PoolVector2Array 
polygon.append(Vector2(0, 20)) 
polygon.append(Vector2(100, 20)) 
polygon.append(Vector2(100, 0)) 
polygon.append(Vector2(0, 0))  
# Returns false:- 
var result = Geometry.is_point_in_polygon(Vector2(0,1), polygon) 

As far as I can see, "result" should be true since (0, 1) is inside this polygon (which is just a rectangle) but it returns false.

If I add:-

polygon.invert()
var result2 = Geometry.is_point_in_polygon(Vector2(0,1), polygon) 

It now returns true, which is correct.

Minimal reproduction project

n/a - See example code above

[TheDuriel]

This was solved on reddit. A careful look at the coordinates reveals that this is an anticlockwise polygon. It thus considers the point, which is on the exact edge (adding to the confusion), to be outside the inverted polygon.

[SteveSmith16384]

Thanks. IMHO, the documentation should be updated though; AFAICS it makes no mention of clockwise or anticlockwise or that they are even a thing to know about.

[kleonc]

This was solved on reddit. A careful look at the coordinates reveals that this is an anticlockwise polygon. It thus considers the point, which is on the exact edge (adding to the confusion), to be outside the inverted polygon.

For reference: reddit thread.

@TheDuriel It's not solved. Even if it's intended to consider the edges to be a part of / not be a part of the polygon based on the winding order then it still seems to be bugged for the corners/vertices:

Test script:

tool
extends EditorScript

func _run() -> void:
	var results_format_string := "  %10s: %5s %5s"

	for rect in [
		Rect2(0, 0, 5, 5),
		Rect2(0, 0, 10, 20),
		Rect2(0, 0, 7, 13),
		Rect2(0, 0, 111, 11),
		Rect2(0, 0, 45, 3),
		Rect2(231, 351, 5, 87),
		Rect2(0, 0, 100, 20),
	]:
		print()
		print("Rect: %s" % [rect])

		var polygon := PoolVector2Array([
			rect.position,
			rect.position + rect.size * Vector2(1, 0),
			rect.position + rect.size * Vector2(1, 1),
			rect.position + rect.size * Vector2(0, 1),
		])

		var polygon_inv = polygon
		polygon_inv.invert()

#		print(" Inside points:")
		for y in range(rect.position.y + 1, rect.end.y):
			for x in range(rect.position.x + 1, rect.end.x):
				var point := Vector2(x, y)
				var r1 = Geometry.is_point_in_polygon(point, polygon)
				var r2 = Geometry.is_point_in_polygon(point, polygon_inv)
				if !r1 or !r2: # Assumption: these should always be considered inside.
					print(results_format_string % [point, r1, r2])

#		print(" Edge points:")
		for y in range(rect.position.y + 1, rect.end.y):
			for x in [rect.position.x, rect.end.x]:
				var point := Vector2(x, y)
				var r1 = Geometry.is_point_in_polygon(point, polygon)
				var r2 = Geometry.is_point_in_polygon(point, polygon_inv)
				if r1 == r2: # Assumption: these should differ based on the winding order.
					print(results_format_string % [point, r1, r2])

		for y in [rect.position.y, rect.end.y]:
			for x in range(rect.position.x + 1, rect.end.x):
				var point := Vector2(x, y)
				var r1 = Geometry.is_point_in_polygon(point, polygon)
				var r2 = Geometry.is_point_in_polygon(point, polygon_inv)
				if r1 == r2: # Assumption: these should differ based on the winding order.
					print(results_format_string % [point, r1, r2])

		print(" Corner points:")

		for point in polygon:
			var r1 = Geometry.is_point_in_polygon(point, polygon)
			var r2 = Geometry.is_point_in_polygon(point, polygon_inv)
	#		if r1 == r2: # Assumption: these should differ based on the winding order.
			# But let's print all of them for showcase:
			print(results_format_string % [point, r1, r2])

Results (v3.5.1.stable.official [6fed1ff]):

Rect: (0, 0, 5, 5)
 Corner points:
      (0, 0):  True  True
      (5, 0):  True  True
      (5, 5): False False
      (0, 5):  True  True

Rect: (0, 0, 10, 20)
 Corner points:
      (0, 0):  True  True
     (10, 0):  True  True
    (10, 20): False False
     (0, 20):  True  True

Rect: (0, 0, 7, 13)
 Corner points:
      (0, 0):  True  True
      (7, 0):  True  True
     (7, 13): False False
     (0, 13):  True  True

Rect: (0, 0, 111, 11)
 Corner points:
      (0, 0):  True  True
    (111, 0):  True  True
   (111, 11):  True False
     (0, 11):  True  True

Rect: (0, 0, 45, 3)
 Corner points:
      (0, 0):  True  True
     (45, 0):  True  True
     (45, 3): False False
      (0, 3):  True  True

Rect: (231, 351, 5, 87)
 Corner points:
  (231, 351):  True  True
  (236, 351):  True  True
  (236, 438): False False
  (231, 438):  True  True

Rect: (0, 0, 100, 20)
 Corner points:
      (0, 0):  True  True
    (100, 0):  True  True
   (100, 20): False False
     (0, 20):  True False

Hence it's not just a matter of documenting it.

---

It's a 3.x-only issue. In master (v4.0.beta7.official [0bb1e89]) all points on the edges (including corners/vertices) seem to properly be considered as inside the polygon. It was changed as a part of #52110, and intentionally no backported to 3.x to avoid potential regressions.