Pixi.js: Graphics.drawPolygon -> containsPoint does not include specified points.

[Adamfsk]

Expected Behavior

When creating a triangular polygon shape in a Graphics object with the following points:
{ x: 20, y: 1 }, { x: 40, y: 20 }, { x: 1, y: 20 }

I would expect the points of the triangle (i.e. the points I have specifically declared) to return true when I call the containsPoint method.

i.e. I would expect the following to return true:

myPolygon.containsPoint(20, 1);
myPolygon.containsPoint(40, 20);
myPolygon.containsPoint(1, 20);

Similarly, when creating a rectangular polygon shape using drawPolygon, with the following points:

{ x: 1, y: 1 }, { x: 40, y: 1 }, { x: 40, y: 20 }, { x: 1, y: 20 }

I would expect the following to return true:

myRectangle.containsPoint(new Point(1, 1));
myRectangle.containsPoint(new Point(40, 1));
myRectangle.containsPoint(new Point(40, 20));
myRectangle.containsPoint(new Point(1, 20));

As is the case when using the drawRect method.

Current Behavior

The calls return false.

Steps to Reproduce

Stackblitz showing the issue:
https://js-9ejjnb.stackblitz.io

Environment

Pixi.js v5.0.4
Unit tests made in jest.

[ivanpopelyshev]

This is fun issue, i like it! Yeah, lets see what can be done. We use that ray-segment check same as everywhere, even in wikipedia. Is there any way to modify it to include the edges or at least vertices?

[Adamfsk]

@ivanpopelyshev I’ve taken a look and I’ve found a few options for further investigation that could solve/improve the issue:

1. Allow optional use of the winding number algorithm which would work in these cases, similarly to how svg graphics use “evenodd” and “nonzero” fill methods to switch between the two as needed. This would probably be the fastest solution, both in implementation and usage, but there would still be issues with some shapes, e.g. border points in polygons containing holes.

2. Look into what Shapely is using, as it appears to work correctly for these cases from comments I’ve seen while searching.

3. Adapt the boolean-point-in-polygon method from turf.js: https://github.com/Turfjs/turf/blob/master/packages/turf-boolean-point-in-polygon/index.ts I expect their solution is probably the slowest but most accurate option.

[Adamfsk]

Regarding Shapely, it looks like it probably also uses the ray casting method, and supplements this with an additional algorithm (the intersect predicate of de-9im) to do checks against points on the boundary lines of polygons. Doing similar might be enough to solve the issue.

However, I suspect there may actually be some issues with the ray casting algorithm you are using, as some of the checks for the polygon rectangle required changing by two pixels in order to get a result of true, where if it was working correctly I would expect to only need to reduce this by at most one pixel into the polygon. I believe it was the right hand side that was affected but unable to confirm until much later today.

[ivanpopelyshev]

Yo! Thanks for the information, that's definitely good description!

Well , at the least it can go into the plugin. I'll try to add it into pixi itself when I have time :) We'll have to cover it with tests too.

[Adamfsk]

Just checked and there wasn't actually any issues with the raycasting; the poly rectangle I created had a typo! :)

[ivanpopelyshev]

If you want, you can make a test where you check many integer points on edges. I still think that our implementation doesn't support testing on the edge.

[Adamfsk]

Sorry Ivan, I should have been clearer; I was referring to this that I said in the previous post:

I suspect there may actually be some issues with the ray casting algorithm you are using, as some of the checks for the polygon rectangle required changing by two pixels in order to get a result of true

Points on the boundary aren't working almost 100% of the time, because of the use of the ray-casting method.

[ivanpopelyshev]

Now imagine that in my fork I had to debug interaction not only with segments but also with quadratic curves ;)

[Adamfsk]

@ivanpopelyshev Is it enough just to add point-on-path checks, or could the ray casting method return false for a point just inside the boundary?

[Adamfsk]

@ivanpopelyshev How are you planning to solve it?

Maybe you can use distance from point to a line.

E.g. for curves:

https://math.stackexchange.com/questions/2264702/shortest-distance-from-point-to-curve

And straight lines:

https://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment

[ivanpopelyshev]

yeah, point-on-path checks with EPS=1e-8 i believe will do it.

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[Adamfsk]

@ivanpopelyshev What happened with this? Did you solve it?

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.