Geometry2D.IsPointInPolygon incorrectly reports point inside of polygon

[mlychagin]

Godot version

4.1.1-stable [bd6af8e]

System information

Godot v4.1.1.stable.mono (bd6af8e) - Ubuntu 22.04.3 LTS 22.04 - Vulkan (Forward+) - dedicated NVIDIA GeForce RTX 4080 () - AMD Ryzen 9 5900X 12-Core Processor (24 Threads)

Issue description

Geometry2D.IsPointInPolygon incorrectly reports a point lies inside of a polygon, when it clearly lies outside of it.

Here is the perimeter of the polygon:

Here I have printed out the result of Geometry2D.IsPointInPolygon() for all points within a range:

As you can see, there is a rogue pixel in the top left quadrant.

Steps to reproduce

I've created the following repro. Simply attach this script to a Node2D and it will fail with: "Error found in Geometry2D.IsPointInPolygon". Note: I'm generating all the vertices (there are around 250), but I can also provide a text file with each individual vertex if necessary.

using System;
using System.Collections.Generic;
using Godot;

public partial class Repro : Node2D
{
    public override void _Ready() {
        int radius = 40;
        int height = 100;
        Vector2 center = new(radius, height * 0.5f);
        var vertices = Capsule(center, radius, height);

        if (Geometry2D.IsPointInPolygon(new Vector2(29, 16), vertices)) {
            throw new Exception("Error found in Geometry2D.IsPointInPolygon");
        }
    }

    private static Vector2[] Capsule(Vector2 center, float radius, float height) {
        int vertexCount = (int)Math.Ceiling(Math.PI * radius);
        var vertices = new List<Vector2>();

        // Bottom of the capsule
        for (int i = 0; i <= vertexCount; ++i) {
            double phi = Math.PI / vertexCount * i;
            Vector2 v = new Vector2((float)Math.Cos(phi), (float)Math.Sin(phi)) * radius;
            v.Y += center.Y + height * 0.5f;
            v.X += center.X;
            vertices.Add(v);
        }

        // Top half-circle of the capsule
        for (int i = vertexCount; i >= 0; --i) {
            double phi = -Math.PI / vertexCount * i;
            Vector2 v = new Vector2((float)Math.Cos(phi), (float)Math.Sin(phi)) * radius;
            v.Y += center.Y - height * 0.5f + 2 * radius;
            v.X += center.X;
            vertices.Add(v);
        }

        return vertices.ToArray();
    }
}

[AThousandShips]

Please provide the code in GDScript as well, the code isn't too complicated to convert, but most people who investigate issues do not have a mono version available, and since you know what it is supposed to do you are best suited to make that version so no one else introduces new errors

[mlychagin]

Unfortunately, due to differences in floating point arithmetic, I wasn't able to get a repro using my vertex generation on GDScript. However, I was able to reproduce the issue by porting all my vertexes over into a GDScript.

Here is the project:
Repro.zip

[kleonc]

The cause seems to be same as in #70823, specifically intersections of the from-point-ray with the polygon edges are counted incorrectly (#70823 (comment)). I'll look into fixing this.

[0xafbf]

If it is related to that issue, then maybe the fix I did can help. #74699

[kleonc]

If it is related to that issue, then maybe the fix I did can help. #74699

@0xafbf I've noticed your PR before your comment, got in on my radar. Regarding relation to this specific issue I think about simplifying Geometry2D::is_point_in_polygon to not use Geometry2D::segment_intersects_segment at all. The checks could be possibly done against an arbitrary ray, e.g. a horizontal one and such assumption should allow to simplify the intersection calculation (specific case vs general case handled by segment_intersects_segment). In such case your PR will be unrelated. Still thanks for the info/update. 🙂

[0xafbf]

I faced this one today although it is different. I am comparing latitude/longitude coordinates and sometimes the difference between positions is in the range of millionths of a unit. this means that it would tell me that I was in the border of the polygon when I really wasn't
My previously mentioned PR in addition to this did fix the issue for me:

diff --git a/core/math/geometry_2d.h b/core/math/geometry_2d.h
index 097aad9cd5..732781db4b 100644
--- a/core/math/geometry_2d.h
+++ b/core/math/geometry_2d.h
@@ -369,7 +369,7 @@ public:
 			Vector2 res;
 			if (segment_intersects_segment(v1, v2, p_point, further_away, &res)) {
 				intersections++;
-				if (res.is_equal_approx(p_point)) {
+				if (res == p_point) {
 					// Point is in one of the polygon edges.
 					return true;
 				}

Overall I think the use of "approximately equal" in functions and comparisons should be discouraged because otherwise we'll keep finding things like these.