Polygon collision detection returns false

[tmanninger]

Hi,

i have the following polygon:

I check collision on the red point, but it returns false.

My polygon:

[
    {
        "x": 970,
        "y": 270.5033381761426
    },
    {
        "x": 970.0000000000001,
        "y": 420.5033381761426
    },
    {
        "x": 969.0000000000001,
        "y": 420.5033381761426
    },
    {
        "x": 969.0000000000001,
        "y": 530
    },
    {
        "x": 968.7287983217848,
        "y": 530
    },
    {
        "x": 968.7287983217848,
        "y": 531
    },
    {
        "x": 878.7287983217848,
        "y": 531
    },
    {
        "x": 878.7287983217848,
        "y": 530
    },
    {
        "x": 844.9555134337561,
        "y": 530
    },
    {
        "x": 844.9555134337561,
        "y": 531
    },
    {
        "x": 764.9555134337561,
        "y": 531
    },
    {
        "x": 764.9555134337561,
        "y": 530
    },
    {
        "x": 657.0000000000007,
        "y": 530
    },
    {
        "x": 578.5920793286247,
        "y": 451.59207932862427
    },
    {
        "x": 564.4499437048937,
        "y": 465.73421495235533
    },
    {
        "x": 507.8814012099698,
        "y": 409.1656724574315
    },
    {
        "x": 522.0235368337007,
        "y": 395.0235368337006
    },
    {
        "x": 472,
        "y": 345
    },
    {
        "x": 472,
        "y": 344
    },
    {
        "x": 471,
        "y": 344
    },
    {
        "x": 470,
        "y": 343
    },
    {
        "x": 469,
        "y": 344
    },
    {
        "x": 371.93498193881544,
        "y": 344
    },
    {
        "x": 371.93498193881544,
        "y": 345
    },
    {
        "x": 291.93498193881544,
        "y": 345
    },
    {
        "x": 291.93498193881544,
        "y": 344
    },
    {
        "x": 263.00000000000006,
        "y": 344
    },
    {
        "x": 263,
        "y": 225
    },
    {
        "x": 262,
        "y": 225
    },
    {
        "x": 262,
        "y": 75
    },
    {
        "x": 263,
        "y": 75
    },
    {
        "x": 263,
        "y": 70
    },
    {
        "x": 289.2059369307241,
        "y": 70
    },
    {
        "x": 289.2059369307241,
        "y": 50
    },
    {
        "x": 379.2059369307241,
        "y": 50
    },
    {
        "x": 379.2059369307241,
        "y": 70
    },
    {
        "x": 538.640166274238,
        "y": 69.99999999999997
    },
    {
        "x": 538.640166274238,
        "y": 67.99999999999997
    },
    {
        "x": 618.640166274238,
        "y": 68.00000000000001
    },
    {
        "x": 618.640166274238,
        "y": 70.00000000000001
    },
    {
        "x": 823.2657226785277,
        "y": 69.99999999999997
    },
    {
        "x": 823.2657226785277,
        "y": 67.99999999999997
    },
    {
        "x": 913.2657226785277,
        "y": 67.99999999999996
    },
    {
        "x": 913.2657226785277,
        "y": 69.99999999999996
    },
    {
        "x": 969,
        "y": 69.99999999999994
    },
    {
        "x": 969,
        "y": 270.5033381761426
    }
]

Points of the polygon are set with: new Polygon({x: 0, y: 0}, points)

I check the collision of the point: x: 662.8325216009875, y: 262.71592654331613 and should detect a collision (let candidate = new Point({x: x, y: y}))

The collision will be checked with: system.checkCollisionCanditate(Polygon, Point)

Is this the correct way?

Thanks for help!

[tmanninger]

I created an sample: https://codesandbox.io/s/suspicious-stitch-gvddft?file=/src/App.tsx

All circles in the polygon should be red, all outside green. But there are many green circles in the polygon

[tmanninger]

This sandbox shows the issue: https://codesandbox.io/s/modest-dew-b5sx6e

The convex polygons are not calculated correctly.

[Prozi]

I've checked the curious case

this happens because your polygon not only is a non convex polygon, it is not a simple polygon - it has lines that cross each other

@tmanninger simple fix https://codesandbox.io/s/pensive-meadow-wk1l5f?file=/src/App.tsx use Math.round() on your x, y values for polygon points

[Prozi]

feel free to open an issue here https://github.com/schteppe/poly-decomp.js/issues I guess

I've checked that quickDecomp() function gives different results based off are your points rounded or not

see

https://codesandbox.io/s/pedantic-haze-zxg8me?file=/src/App.tsx:596-895

logs the table

(index)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
rounded	4	6	4	4	4	4	4	4	10	4	4	4	4	5	5	5
non rounded	4	4	4	4	4	4	4	3	4	4	4	4	4	5	5	5

[Prozi]

@tmanninger closing as this won't fix on the side of detect-collisions, it might get fixed in poly-decomp, or you can just round your points. good luck

[tmanninger]

Thanks for feedback @Prozi Currently, i only checking if a point is an a polygon. I am using this "hack" in my checkCollision funciton:

        export function isPointInsidePolygon(point, polygon) {
            return (_isPointInsidePolygon({x: point.x - 0.01, y: point.y - 0.01}, polygon)) ||
                (_isPointInsidePolygon({x: point.x + 0.01, y: point.y - 0.01}, polygon)) ||
                (_isPointInsidePolygon({x: point.x - 0.01, y: point.y + 0.01}, polygon)) ||
                (_isPointInsidePolygon({x: point.x + 0.01, y: point.y + 0.01}, polygon))
        }

        export function _isPointInsidePolygon(point, polygon) {

            // ray-casting algorithm based on
            // https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html/pnpoly.html

            var x = point.x, y = point.y;

            var inside = false;
            for (var i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
                var xi = polygon[i].x, yi = polygon[i].y;
                var xj = polygon[j].x, yj = polygon[j].y;

                var intersect = ((yi > y) != (yj > y))
                    && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
                if (intersect) inside = !inside;
            }

            return inside;
        }

This worke fine.

[Prozi]

hello @tmanninger

approximation of aInB and bInA

has been hopefully fixed/featured correctly since v6.8.0

please see https://codesandbox.io/s/detect-collisions-test3-forked-gxfjzp?file=/package.json

could you test this a bit on your cases?

[Prozi]

I have not thoroughly tested this and it seems it works unless polygon is crossing itself

this case does only partially work