-
Notifications
You must be signed in to change notification settings - Fork 1.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Wrong hit result #819
Comments
Oh dear, that seems to be a side effect of the new boolean code. We probably get two intersections at the little horizontal line left to the point, which then results in a winding number of 1, which means we are inside the path. |
Hmm but we didn't change the winding code, did we? The |
You are correct @lehni, this also happens in older versions, but it is a bit difficult to compare, because in previous versions the curve values were totally wrong (including a few As I see it, there are a two strange things happening here:
var values = [0, 0, 0, 0, 0, 20, 0, 20];
var roots = [];
paper.Curve.solveCubic(values, 1, 20, roots, 0, 1);
console.log(roots[0]; // should be "1", but actually is "0.999999988079071" |
What causes the double counting of the winding is the condition in @lehni Do you know any cases where this condition is required? I commented it out and in my test suite it caused no new glitches. |
I think an easy solution would be the following, but it is a bit of a hack, because In } else if (winding === 0 && py === values[1]) {
prevCurve = curve;
} (we only have to check against Or maybe this~~, which I think is more correct~~: } else if (winding === 0 && prevT > tMax) {
prevCurve = curve;
} (Update: I think the second solution is not more correct, because the problem occurs only if there is an absolutely horizontal curve (v[1] === v[7]) AND the end point of the previous curve is exactly at py AND the start point of the next curve is exactly at py. This means that my first solution already covers all possible cases). |
@iconexperience the code in question was implemented to solve #736, so any changes to it should probably be tested against that case as well. Could you have a look? |
Yes, I will do. Also, I think the issue is a little bit more complicated than I thought and there could be other cases that still fail. It should be solveable, but it's a bit tricky. |
I found some inconsistencies with precision in |
I have created a small test case based on @aureole82's example that produces six wrong results. For the points outside the path I have set the winding rule to "evenodd", which causes the points inside the path to be counted as outside. I think I have found a solution, but I need to test it agains some edge cases. |
@lehni I have a question. What I need to do is to find out the first and the last curve that has Update: Maybe the "loops" are a relict from the old boolean code when paths could have self intersections? |
The reason why it's done this way is simply that the curves array of a CompoundPaths can contain more than one loop (all curves of the first child-path = loop 1, followed by all curves of the second child-path = loop 2, etc). |
@iconexperience your observation about |
@lehni I will try to do this. I think I understand the whole algorithm and I know where the problems are. Also, your information about the compound paths was very helpful. But I need some time, too. |
@iconexperience great, thanks! |
@iconexperience I've rewritten your sketch a bit to give visual feedback. |
@lehni I though I had a good solution, but then I found new cases that caused problems. Therefore I will present some intermediate results for discussion. The problem with the current implementation of The two red intersections should be merged, but this fails in the current implementation, because due to the horizontal curve the two vertical curves are not regarded as being neighbors. I have found a way that fixes merging of these intersections, but my apporach fails if the point is directly on a horizontal curve. Actually, I do not even know what the correct result should be. Below are four examples, red intersections indicate a winding contribution of -1, green ones indicate a winding contribution of 1. Here is a quick summary of our algorithm which should help to understand the examples: We calculate the sum of the winding contributions for all intersections right and left of the point ( A point is inside a path if the winding value is non-zero (when using the non-zero rule) or odd (when using he even-odd rule). The following four examples illustrate the problem. With the current implementation in examples 1, 2 and 4 the point will be counted as being inside the path, in example 3 the point is counted as being outside of the path. Example 1 Example 2 Example 3 Example 4 I am tempted to simply return |
For testing my first proposed solution, I have made the test case a little bit nastier. And this is how it looks: As you can see, the results look quite random. |
@lehni Do you have a proposal what the correct return value of For 1, 2 and 6 it is probably |
Here is another Sketch which shows the results if we switch x and y corrdinates in the example above. This is how it looks: I will try to get the same results for the original example. |
I have finished an implementation that seems to work well. After some testing and cleanup I hopefully can create a pull request next week. |
@iconexperience sounds great! Apologies for my silence on all fronts, I've been constantly absorbed, and will be for another two weeks until things are finally cooling down. Will be back more around here after that! |
No problem, I know that you are busy. I will just keep on working and see how far I can get. |
So I'm finally coming out of my work tunnel. What's the state of affairs here now? Is #852 fully solving this? And could you outline the approach you've settled for in the end? Just trying to understand it. |
The reason why I am asking: I wonder if a part of the work that you're doing in |
As far as I can see this issue is fixed with my proposed changes at #852. I have not found any negative side effects and performance should be about the same. But since the change is rather complex, I would like to do more testing. And I will add more details on my new implementation here. |
This is now merged in, but I am keeping this issue open until I've implemented unit tests for it too. |
I got the hit result
{ type: 'fill', item: Path@1 }
where definitely no hit result should be.http://jsfiddle.net/x5t1v10e/
The text was updated successfully, but these errors were encountered: