contains() returns false for interior point

[iconexperience]

In some cases path.contains() returns false for points that are actually inside a path. Here is an example:

var p = new Path({segments:[
    [410.6261524612045, 207.9735406405153],
    [410.6261525310172, 207.97354059345614, -0.0005059167983745283, -0.0007686158121771314]
], closed:true});

console.log("area: " + p.getArea());
console.log(p.contains(p.getInteriorPoint()));

Visual debuggind indicates that the point is inside the path:

The reason for this behaviour is probably that getWinding() uses a tolerance to exclude points directly on a curve. This should not be done when checking if a point is contained by a path.

Until recently there was a testContains parameter in the getWinding()function. Maybe the purpose of this was to distinguish between winding calculations for 'contains' tests and 'winding propagation'?

[lehni]

No, the removal of testContains is not the cause of it. I went back to the commit before it was removed (92904e9), and it returns false there too...

[iconexperience]

The reason why it fails is fairly simple.

In getWinding() we do not count the intersection of the horizontal ray if the x value of the point is within a certain tolerance of the intersection's x value. If a point is in the light blue regions in the image below, the intersection with the vertical curve at that point is not counted. This way we make sure that these points are inside the path. Of course the width of the blue area is vastly exaggerated.

This works quite well, but it fails if two curves are too close together. For any point in the darker blue area below no intersection of the horizontal ray is counted, therefore winding is zero, which means the point is outside the path.

I do not have a solution, but at least we understand now why the problem occurs.

[lehni]

Yes that makes a lot of sense! We could calculate a path's area in _getMonoCurves() and decide on an epsilon value based on that, then store it along with the first curves in the array.

[iconexperience]

This si difficult. And it seems like it is not very important, because although we have a problem in theory, we have not encountered a real world scenario where this has any consequences.

Of course the most simple solution would be to have getWinding() always return 1 if we find any non-horizontal curve that contains the point. But this may cause problems with multiple overlapping paths within a compund path. Really, not easy.

[lehni]

That's a good thought! And that would be easy to add to your code?

[iconexperience]

if (x >= xBefore && x <= xAfter) return 1

It's quite a hack, although it should work. Actually, I do not like this, it's a really dirty hack.

[lehni]

Right after if (x != null) { ?

[lehni]

I was thinking the same just now about compound paths... didn't see that before. Yeah, I'm reluctant as well :)

[iconexperience]

Here is a test case that currently works, but any solution that solves the initial example in this issue should be tested agains this test case. The difference to the initial test case is that the two close curves are inside the rest of the path, which means the horizontal ray starting from the point crosses the path one more time in each direction.

var path = new Path({segments: [
    [100, 100],
    [150, 100],
    [150, 150],
    [150.000000005, 150],
    [150.000000005, 100],
    [200, 100],
    [200, 200],
    [100, 200]
    ], closed: true, strokeColor: "OliveDrab"});

var point = new Point(150.000000003, 120);
new Path.Circle({center: point, radius: 2, fillColor: "FireBrick"});
console.log("contains = " + path.contains(point));

Here is the Sketch

[lehni]

Yes that makes perfect sense. I guess one would have to compare the x coordinates of the intercepts to distinguish the two?

[iconexperience]

That could work, but it requires to compare each intersection of the ray with each other intersection.

I just had another idea. We could have a flag isOnCurve, which will be set if we encounter if (x >= xBefore && x <= xAfter). Then, if at the end our winding is even and isOnCurveis true, we simply increase the winding by one. I have to think this through with all kinds of scenarios, especially with compound paths.

[iconexperience]

In order to solve this issue we should first decide when contains() should return true. Currently for all points in the following example false is returned. I though this would be correct, because the linese there have a discance of exactly zero, so there is no "content" between the lines. Could you live with contains() returning truefor all these points? I think then I would have a nice solution.

[lehni]

That's a good question. I tend to think yes, it should be false (e.g. since we're also discarding such parts in the boolean ops), except for one doubt: We do consider the line as part of the inside of the paths, don't we? So wouldn't we have to do the same here then?

[iconexperience]

I would make things much easier to have these points part of the path. And there is another weirdness in the way we currently handle these points: If they are on a vertical tip of two vertical lines, contains() returns true, but if we are somewhere in the middle of the lines it returns false.

The Sketch

[iconexperience]

@lehni Actually my proposal is very simple. If the point at getWinding() is on a curve, we ignore that intersection but set the flag onCurve to true. At the end, if the point was on a curve, we make sure that the winding is odd through return onCurve ? absWinding | 1 : absWinding;

I will check how this works in theory with compound paths and if I am confident enough, I will create a pull request. No action from your side required.

[iconexperience]

My proposals fails with intersect boolean operations. Unfortunately it's not as easy as expected.

[iconexperience]

Here is another promising approach.

The first time we encounter an intersection very close to the point (x >= xBefore && x <= xAfter), we ignore the intersection. But after that if we find more intersections close to the point, the winding left and right get incremented for each additional intersection.

This seems to work quite well so far.

[lehni]

Sounds promising! Define "quite"? : )

[iconexperience]

"quite" means it looks good at the start, but eventually fails. This one fails if we have two intersections inside the path, like in this example:

This is hard.

[lehni]

Maybe not worth fixing?

[iconexperience]

Maybe you are right, but I will try a little more.

Here is another approach that so far passes all tests:

• If there is an intersection very close to the point, we return at the end Math.max(1, absWinding).

That's all. I need to test this with some compound paths.

[lehni]

I had a hunch that by telling you to give up, you'd dig in deeper and find a solution :P

[iconexperience]

My weak spot :)

[lehni]

Do you still want to tackle this or shall we close the issue?

[iconexperience]

If you accept my pull request, you can close the issue 😄

[lehni]

Very cool! I'm on a train in Germany with very spotty reception, but am trying my best at pulling : )

[iconexperience]

This can finally be closed after the fix-windingbranch has been merged into the develop branch in 5a46620

[lehni]

👍