Geometry2D.segment_intersects_segment() returns wrong value leading to inconsistent results

[cskwrd]

Tested versions

Found in: v4.3.stable.arch_linux

System information

Godot v4.3.stable unknown - EndeavourOS #1 SMP PREEMPT_DYNAMIC Sat, 18 Jan 2025 02:26:57 +0000 - Wayland - GLES3 (Compatibility) - NVIDIA GeForce RTX 2060 SUPER (nvidia; 565.77) - AMD Ryzen 9 3900X 12-Core Processor (24 Threads)

Issue description

It seems a floating point issue causes Geometry2D.segment_intersects_segment() to return the wrong intersecting value leading to confusing results when working with consecutive/connected line segments.

I am trying to bisect a polygon. Let's say ABCD and the bisecting line segment (PQ) intersects with AB extremely close to B. Geometry2D.segment_intersects_segment() correctly indicates that an intersection exists. However, unexpectedly, the function returns the point B as the intersection instead of the real intersection extremely close to B. In isolation, that is fine, but when considering a second segment BC its confusing. Geometry2D.segment_intersects_segment() does NOT indicate an intersection with BC. That is technically correct, but inconsistent with the previous result.

I believe the issue is the wrong value is returned when determining if AB intersects with PQ.

Steps to reproduce

Attach this script provided here to a Node2D scene and run. It has assertions that trigger based on whether the bug is present.

Minimal reproduction project (MRP)

extends Node2D

func _ready() -> void:
	# To set the scene...
	# Imagine [from_b -> to_b] is a line segment bisecting a polygon,
	# and [from_a_1 -> to_a_1] and [from_a_2 -> to_a_2] are line segments
	# representing 2 consecutive sides of this polygon (in CCW orientation)
	
	var from_b := Vector2(202.727264, 50.000000)
	var to_b := Vector2(1969.999878, 1130.000000)
	
	var from_a_1 := Vector2(50.000000, 1130.000000)
	var to_a_1 := Vector2(1970.000000, 1130.000000)
	var has_intersection_with_segment_end: Variant = Geometry2D.segment_intersects_segment(
		from_a_1,
		to_a_1, # this value is returned
		from_b,
		to_b
	)

	assert(has_intersection_with_segment_end == to_a_1, "rounding/point handling bug NOT present")

	var from_a_2 := Vector2(1970.000000, 1130.000000)
	var to_a_2 := Vector2(1970.000000, 50.000000)
	var has_intersection_with_segment_start: Variant = Geometry2D.segment_intersects_segment(
		from_a_2, # this value is NOT returned even though you would think it should based on the previous check
		to_a_2,
		from_b,
		to_b # this value isn't returned bc the line segments don't intersect
	)

	assert(has_intersection_with_segment_start == has_intersection_with_segment_end, "rounding/point handling bug present")

[AThousandShips]

Sounds like:

• Geometry2D.is_point_in_polygon() give inconsistent result on exactly boundary points #81042

[lawnjelly]

Although it is possible the routine could be improved, with floating point, be aware you are nearly always going to get inconsistencies like this.

This is why geometry libraries often use fixed point math, or solutions that work around float error. Often, >95% development effort goes into working around float error.